[PTA]7-6 整数分解为若干项之和
将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。
输入格式:
每个输入包含一个测试用例,即正整数N (0<N≤30)。
输出格式:
输入样例:
7
输出样例:
7=1+1+1+1+1+1+1;7=1+1+1+1+1+2;7=1+1+1+1+3;7=1+1+1+2+2
7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2
7=1+2+4;7=1+3+3;7=1+6;7=2+2+3
7=2+5;7=3+4;7=7
代码
#include<stdio.h>
int sum=0;//sum用来统计输出次数每四次都要换行控制格式
int a[30];//a[i]是这一层循环决定的因子
void fenjieyinzi(int x,int n,int flag,int xiaxian){for(int i=xiaxian;i<=x;i++){if(x-i>0){//如果x-i>0说明还可以分解出因子a[flag]=i;//这一层循环决定的因子赋值为ifenjieyinzi(x-i,n,flag+1,i);//调用函数}else if(x-i==0){//如果等于0说明所有有的因子已经找到这是最后一个因子a[flag]=i;//得到最后一个因子for(int i=0;a[i]!=0;i++){//输出这一种分解方法if(i==0){printf("%d=%d",n,a[i]);}else{printf("+%d",a[i]);}}sum++;//分解次数加1a[flag]=0;//这一层的因子无用初始化为0上面以a[i]=0作为终止条件if(sum==4){printf("\n");sum=0;}else{if(flag!=0)//保证最后一种分解方法符合格式要求printf(";");}}}
}
int main(){int flag=0;int sum=0;int n;scanf("%d",&n);fenjieyinzi(n,n,flag,1);return 0;
}