解题思路: 数学模型:看成 有n个球要放到k个盒子里,变化的是(盒子)k的数目。 1。如果盒子数为1或者n,都只有1种方法 2.如果球数小于盒子数,必定有n-k个盒子为0,去掉这些盒子也没影响,即fun(n,n) 所以可直接返回0 3.最重要的地方!! 如果球数大于盒子数 分为两种情况! 第一:所有盒子都放了球,则可以相当于把所有盒子都取出一个球,方案数不变 即为fun(n-k,k) 第二:至少有一个盒子为空格 fun(n-1,k-1)
注意事项:
参考代码:
#include<iostream> using namespace std; int count=0,n; const int N=105; long long book[N][N];//用于标记 long long fun(int m,int k){ if(book[m][k]!=0) return book[m][k]; //如果是已经标记过的情况,直接返回 if(m<k) return 0; if(k==1||m==k) return 1;//k=1即分一组,就只有n。 m==k表示每个组为1 return book[m][k]=fun(m-k,k)+fun(m-1,k-1); } //两种情况 int main(){ cin>>n; int i; for(i=1;i<=n;i++) count+=fun(n,i); cout<<count; return 0;}
0.0分
6 人评分
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:529 |
C二级辅导-等差数列 (C语言代码)浏览:575 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:928 |
C语言程序设计教程(第三版)课后习题10.1 (Java代码)浏览:1436 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:539 |
WU-图形输出 (C++代码)浏览:802 |
【偶数求和】 (C语言代码)浏览:556 |
printf基础练习2 (C语言代码)浏览:746 |
【计算球体积】 (C语言代码)浏览:1101 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:467 |