P2404 自然数的拆分问题

admin

https://www.luogu.org/problemnew/show/P2404

题目背景
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

题目描述
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

输入输出格式
输入格式：
输入：待拆分的自然数n。

输出格式：
输出：若干数的加法式子。

输入输出样例
输入样例#1：
7
输出样例#1：
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4
说明
用回溯做。。。。

n≤8

YTC

#include<iostream>
using namespace std;
int a[10];
int n;
int ans;
void dfs(int k)
{
    if(ans==n&&k!=2){for(int i=1;i<=k-2;i++)cout<<a[i]<<'+';cout<<a[k-1]<<endl;}
    for(int i=(k==1?1:a[k-1]);i<=n-ans;i++)
    {
        ans+=i;
        a[k]=i;
        dfs(k+1);
        ans-=i;
    }
}
int main()
{
    cin>>n;
    dfs(1);
    return 0;
}

李思矿

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int n;
   
5. void dfs(int last,int now,int tot,string out)
   
6. {
   
7.     if(now==tot)
   
8.     {
   
9.         cout<<out<<endl;
   
10.         return ;
    
11.     }
    
12.     for(int i=last;i<=tot-now;i++)
    
13.     {
    
14.         string str=out;
    
15.         str+='+';
    
16.         str+=i+'0';
    
17.         dfs(i,now+i,tot,str);
    
18.     }
    
19. }
    
20. int main()
    
21. {
    
22.     cin>>n;
    
23.     for(int i=1;i<=n/2;i++)
    
24.     {
    
25.         string str="";
    
26.         str+=i+'0';
    
27.         dfs(i,i,n,str);
    
28.     }
    
29.     return 0;
    
30. }
    

复制代码

admin

李思旷同学的那个string out真是别出心裁！

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int n,a[20];
    
14. void dfs(int left,int last,int w)
    
15. {
    
16.         if(left==0&&w!=1)
    
17.         {
    
18.                 for(int i=1;i<w;i++)
    
19.                         printf("%d+",a[i]);
    
20.                 printf("%d\n",a[w]);
    
21.                 return ;
    
22.         }
    
23.         for(int i=last;i<=left;i++)
    
24.                 a[w+1]=i,dfs(left-i,i,w+1);
    
25. }
    
26. int main()
    
27. {
    
28.     scanf("%d",&n);
    
29.     dfs(n,1,0);
    
30.     return 0;
    
31. }

复制代码

冯文韬

1. #include<iostream>
   
2. using namespace std;
   
3. int n, a[10001], total;
   
4. void print() {
   
5.     int count = 1;
   
6.     while (a[count]) {
   
7.         if (!a[count + 1]) cout << a[count];
   
8.         else cout << a[count] << "+";
   
9.         count++;
   
10.     }
    
11.     cout << endl;
    
12.     return ;
    
13. }
    
14. void search(int x) {
    
15.     int i;
    
16.     if (total == n) {
    
17.         print();
    
18.         return ;
    
19.     }
    
20.     for (i = 1; i < n; i++) {
    
21.         if (i >= a[x - 1]) {
    
22.             a[x] = i;
    
23.             total += a[x];
    
24.             if (total > n) {
    
25.                total -= a[x];
    
26.                a[x] = 0;
    
27.                break;
    
28.             }
    
29.             search(x + 1);
    
30.             total -= a[x];
    
31.             a[x] = 0;   
    
32.         }
    
33.     }
    
34. }
    
35. int main() {
    
36.     cin >> n;
    
37.     search(1);
    
38.     return 0;
    
39. }

复制代码

Scorpio

1. #include<iostream>
   
2. using namespace std;
   
3. int a[9];
   
4. int n;
   
5. void hhh(int i,int s)
   
6. {
   
7.     int j,k;
   
8.     if(s>=n)
   
9.     {
   
10.         for(j=1;j<=i-1;j++)
    
11.             if(j==1)
    
12.                 cout<<a[j];
    
13.             else
    
14.                 cout<<"+"<<a[j];
    
15.         cout<<endl;
    
16.     }
    
17.     else for(k=1;k<=n-s;k++)
    
18.     {
    
19.         if(k>=a[i-1]&&k!=n)
    
20.         {
    
21.             a[i]=k;
    
22.             hhh(i+1,s+a[i]);
    
23.         }
    
24.     }
    
25. }
    
26. int main()
    
27. {
    
28.     cin>>n;
    
29.     hhh(1,0);
    
30.     return 0;
    
31. }
    

复制代码

t20020125

#include<iostream>
#include<cstdio>
using namespace std;
const int mm=100;
int n;
int a[mm];
void dfs(int f,int m,int l)
{
    if(l==0&&f!=2)
    {
        //cout<<f<<"====";
        for(int i=1;i<=f-2;i++)
        {
            cout<<a[i]<<'+';
        }
        cout<<a[f-1];
        cout<<endl;
    }
    else if(l<m)return;
    else
    {
        for(int i=m;i<=l;i++)
        {
            a[f]=i;
            dfs(f+1,i,l-i);
        }
    }
}
int main()
{
    cin>>n;
    dfs(1,1,n);
    return 0;
}

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. int n,a[10001]={1},t=1;
   
4. void dfs(int x,int y)
   
5. {
   
6.     int i,k;
   
7.     if(y==0)
   
8.     {
   
9.         for(k=1; k<x-1; k++)
   
10.             cout<<a[k]<<"+";
    
11.         cout<<a[x-1]<<endl;
    
12.         return;
    
13.     }
    
14.     else
    
15.         for(i=a[x-1]; i<=y; i++)
    
16.         {
    
17.             if(i<n)
    
18.             {
    
19.                 a[x]=i;y-=i;
    
20.                 dfs(x+1,y);
    
21.                 y+=i;
    
22.             }
    
23.         }
    
24. 
    
25. }
    
26. int main()
    
27. {
    
28.     cin>>n;
    
29.     dfs(1,n);
    
30.     return 0;
    
31. }

复制代码

universehyf

1. #include<iostream>
   
2. using namespace std;
   
3. int s[9];
   
4. int n,c,t;
   
5. void dfs(int x)
   
6. {
   
7.     for(int i=s[x-1];i<n;i++)
   
8.         if(c+i<=n)
   
9.         {
   
10.             c+=i;s[x]=i;
    
11.             if(c==n)
    
12.             {
    
13.                 cout<<s[1];
    
14.                 for(int j=2;j<=x;j++)
    
15.                     cout<<"+"<<s[j];
    
16.                 cout<<endl;
    
17.             }
    
18.             else dfs(x+1);
    
19.             c-=i;
    
20.         }
    
21.         else return;
    
22. }
    
23. int main()
    
24. {
    
25.     cin>>n;s[0]=1;
    
26.     dfs(1);return 0;
    
27. }

复制代码