7-37 整数分解为若干项之和（20 分）
将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如$17=6+1, \quad 7=5+2, \quad 7=5+1+1, \dots$。编程求出正整数N的所有整数分解式子。
输入格式：
每个输入包含一个测试用例，即正整数$N (0\lt N\leq 30)$。
输出格式：
按递增顺序输出N的所有整数分解式子。递增顺序是指：对于两个分解序列N1={n1,n2,⋯}和N2={m1,m2,⋯}，若存在i使得n1=m1,⋯,ni=mi，但是ni+1<mi+1,则N1序列必定在N2序列之前输出。每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。
输入样例：
输出样例：
1
2
3
4
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <stdio.h>
#include <stdlib.h>
int item[31];
int top=0;
int sum=0;
int n;
int k;
void dfs(int number)
{
if(sum==n){
k++;
printf("%d=%d",n,item[0]);
for(int i=1;i<=top-1;i++)
printf("+%d",item[i]);
if(k%4==0||top==1)
printf("\n");
else
printf(";");
}
if(sum>n){
return;
}
for(int i=number;i<=n;i++){
sum=sum+i;
item[top++]=i;
dfs(i);
sum=sum-i;
top--;
}
}
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
}
|
