100分成6个数字的和的方案

admin

1. //100分成6个数字的和
   
2. #include <iostream>
   
3. #include <cstdio>
   
4. #include <iomanip>
   
5. using namespace std;
   
6. const int maxm=20;  //100太大了 20 来验证
   
7. const int maxn=7;//0位作废
   
8. int ss;
   
9. int a[maxn];
   
10. int d[maxm+1][maxn];
    
11. int z[7]={0,maxm/6,maxm/5,maxm/4,maxm/3,maxm/2,maxm};  //每个数字的最大值  显然第一个数字不可能超过100/6
    
12. void mysearch(int i)  //递归的做法
    
13. {
    
14. 
    
15.     int j,k,s;
    
16.     if (i>=maxn-1)
    
17.     {
    
18.         s=a[1]+a[2]+a[3]+a[4]+a[5];
    
19.         a[6]=maxm-s;  //计算出A[6]而不是枚举出a[6]，减少一次递归，
    
20.         if (a[6]>=a[5])
    
21.         {cout<<setw(5)<<++ss<<':';for (j=1; j<=maxn-1; j++) cout<<a[j]<<' ';
    
22.         cout<<endl;}
    
23.     }
    
24.     else for (k=a[i-1]; k<=z[i]; k++)   {a[i]=k;mysearch(i+1);}
    
25. 
    
26. }
    
27. void pp()
    
28. {
    
29.     int i,j;
    
30.     cout<<"=====================\n";
    
31.     for (j=0;j<=6;j++)
    
32.     {for (i=0;i<=21;i++) cout<<setw(4)<<d[i][j];cout<<endl;}
    
33. }
    
34. int dp(int m,int n) //动态规划的做法
    
35. {   int i,j,k;
    
36.     for(i=1;i<=maxm;i++) {d[i][1]=1; //任何数字分成1个数字有一种做法；
    
37.     d[i][2]=i/2;}//任何数字分成2个数字有i/2种做法；
    
38.     for(i=2;i<=maxm;i++)
    
39.         for(j=2;j<=maxn-1;j++)
    
40.            if (i>=j) d[i][j]=d[i-1][j-1]+d[i-j][j];  //这个公式要认真思考！！！
    
41.     /*把100分成6份等价于两种分法的和
    
42.     1、99分成5份，最后加一份1
    
43.     2、95分成6份，每份加上1
    
44.     这两种分法之间没有重复，并且加起来覆盖了全部  */
    
45. 
    
46.     return d[m][n];
    
47. }
    
48. int main()
    
49. {
    
50.     //freopen("1.txt","w",stdout);
    
51.     a[0]=1;mysearch(1);
    
52.     cout<<dp(maxm,6);
    
53.     pp();
    
54. }
    
55. 
    

复制代码

admin

张溯源 发表于 2020-3-4 21:16
为啥我一直没有结果

因为你好几个地方b[k]=0 和 b[k]=1 写错了！请看36行  44行。

张溯源

为啥我一直没有结果

张溯源

1. #include<iostream>
   
2. using namespace std;
   
3. int a[7];
   
4. bool b[110];
   
5. int sum;
   
6. void ish()
   
7. {
   
8.         sum=0;
   
9.         for(int i=1;i<=6;i++)
   
10.                 sum=sum+a[i];
    
11. }
    
12. void pr()
    
13. {
    
14.         for(int i=1;i<=5;i++)
    
15.                 cout<<a[i]<<"+";
    
16.         cout<<a[6]<<"=100";
    
17.         cout<<endl;
    
18. }
    
19. void pmn(int i)
    
20. {
    
21.         if(i>6)
    
22.         {
    
23.                 ish();
    
24.                 if(sum==100)
    
25.                         pr();
    
26.         }
    
27.         else
    
28.         {
    
29.                 for(int k=1;k<=100;k++)
    
30.                 {
    
31.                         if(b[k]==1)
    
32.                         {
    
33.                                 a[i]=k;
    
34.                                 b[k]=0;
    
35.                                 pmn(i+1);
    
36.                                 b[k]=0;
    
37.                         }
    
38.                 }
    
39.         }
    
40. }
    
41. int main()
    
42. {
    
43.         for(int i=0;i<110;i++)
    
44.                 b[i]=0;
    
45.         pmn(1);
    
46.         return 0;
    
47. }

复制代码

(简单的)dfs，请大佬们过目（满足o(*￣︶￣*)o）
只不过为什么一直没有结果……
~~~知识新手，别鄙视我~~~

universehyf

1. #include<iostream>
   
2. using namespace std;
   
3. int i,j;
   
4. int s[101][7];
   
5. int main()
   
6. {
   
7.     for(i=1;i<=100;i++)
   
8.         s[i][1]=1;
   
9.     for(i=2;i<=6;i++) s[1][i]=0;
   
10.     for(i=2;i<=100;i++)
    
11.         for(j=2;j<=6;j++)
    
12.             s[i][j]=i-j>=0?s[i-1][j-1]+s[i-j][j]:s[i-1][j-1];
    
13.     cout<<s[100][6];
    
14.     return 0;
    
15. }

复制代码

universehyf

1. <blockquote>#include<iostream>

复制代码

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. int i,j,m,n;
   
4. int main()
   
5. {
   
6.     cin>>m>>n;
   
7.     int a[m][n];
   
8.     for(i=0;i<=m;i++)
   
9.         for(j=0;j<=n;j++)
   
10.             a[i][j]=0;
    
11.     for(i=0;i<=m;i++)a[i][1]=1;
    
12.     for(i=1;i<=m;i++)
    
13.         for(j=2;j<=n;j++)
    
14.     {
    
15.         a[i][j]=a[i-1][j-1]+a[i-j][j];
    
16.         if(j>i)a[i][j]=0;
    
17.     }
    
18.     cout<<a[m][n];
    
19.     return 0;
    
20. }
    

复制代码

吴语林

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. long long f[1000][10]={0};
    
14. int main()
    
15. {
    
16.         f[1][1]=f[2][1]=f[2][2]=1;
    
17.     for(int i=2;i<=101;i++)
    
18.     {
    
19.             f[i][1]=1;
    
20.             for(int j=2;j<=6&&i>=j;j++)
    
21.                     f[i][j]=f[i-1][j-1]+f[i-j][j];
    
22.     }
    
23.     printf("%d",f[100][6]);
    
24.     return 0;
    
25. }

复制代码

hr567

/wjr/ 发表于 2014-10-29 14:39
.......自动忽视。。。用Dev-cpp4.9.9.2写的

我本来也想用dev-c++的，可惜win8.1已经完美不兼容了……所以一直没用过。

/wjr/

hr567 发表于 2014-10-28 21:49
……
不需要吧？

.......自动忽视。。。用Dev-cpp4.9.9.2写的

/wjr/

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

复制代码

输入10,3即可。。。。