自然数n的分解

输入自然数n（n<100），输出所有和的形式。不能重复。

如：4=1+1+2；4=1+2+1;4=2+1+1 属于一种分解形式。

样例：

输入：

输出：

7=1+6

7=1+1+5

7=1+1+1+4

7=1+1+1+1+3

7=1+1+1+1+1+2

7=1+1+1+1+1+1+1

7=1+1+1+2+2

7=1+1+2+3

7=1+2+4

7=1+2+2+2

7=1+3+3

7=2+5

7=2+2+3

7=3+4

分析：

假设n=a[1]+a[2]+...+a[n],为了避免分解重复，可以约定a[1]≤a[2]≤...≤a[n],

假设当前已经分解出cur项，待分解的数字为m(m=n-a[1]-a[2]...-a[cur]);

则 a[1],a[2],...,a[cur],m即是一种分解方案(cur>0)

如何继续分解呢，a[cur+1]=？

a[cur+1]的取值范围：a[cur]~m/2 (因为 m-a[cur+1]>=a[cur+1],则a[cur+1]/2<=m才能继续分解)

代码：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int a[100],b[100];
 5 int s=0, n;
 6 void dfs(int cur,int m){
 7     if (cur>0){
 8         s++;
 9         cout<<n<<"=";
10         for (int i=1;i<=cur;i++) cout<<a[i]<<"+";
11         cout<<m<<endl;
12     }
13      for (int i=a[cur];i<=m/2;i++){
14          a[cur+1]=i; 
15         dfs(cur+1,m-i);         
16         }
17      }      
18 int main(){ 
19     memset(a,0,sizeof(a));
20     memset(b,0,sizeof(b));
21     cin>>n;
22     a[0]=1;
23     dfs(0,n);
24     cout<<s<<endl;
25     return 0;
26 }

View Code