华师一附中OI组

标题: 100分成6个数字的和的方案 [打印本页]
作者: admin    时间: 2014-10-25 18:05
标题: 100分成6个数字的和的方案
  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. {

  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);}

  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.     这两种分法之间没有重复，并且加起来覆盖了全部  */

  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. }

复制代码


作者: /wjr/    时间: 2014-10-28 18:41
  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即可。。。。
作者: /wjr/    时间: 2014-10-29 14:39
hr567 发表于 2014-10-28 21:49
……
不需要吧？

.......自动忽视。。。用Dev-cpp4.9.9.2写的
作者: hr567    时间: 2014-10-29 21:01
/wjr/ 发表于 2014-10-29 14:39
.......自动忽视。。。用Dev-cpp4.9.9.2写的

我本来也想用dev-c++的，可惜win8.1已经完美不兼容了……所以一直没用过。
作者: 吴语林    时间: 2018-6-26 11:12
  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. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-6-26 16:39
  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. }
复制代码

作者: universehyf    时间: 2018-9-1 13:47
本帖最后由 universehyf 于 2018-9-1 13:48 编辑
  1. <blockquote>#include<iostream>
复制代码
作者: universehyf    时间: 2018-9-1 13:49
  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. }
复制代码
作者: 张溯源    时间: 2020-3-4 21:14
本帖最后由 张溯源 于 2020-3-4 21:15 编辑
  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）
只不过为什么一直没有结果……
~~~知识新手，别鄙视我~~~
作者: 张溯源    时间: 2020-3-4 21:16
为啥我一直没有结果
作者: admin    时间: 2020-3-5 09:02
张溯源 发表于 2020-3-4 21:16
为啥我一直没有结果

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



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2