问题描述:m个苹果放置在n个盘子中,允许有的盘子为空,共多少种放法? 【注】1、如5,1,1和1,5,1 属于同一种放法 2、m,n均小于10
【示例】 m=7 n=3 有8种放法
【思想】 0、当n=1时,所有苹果都必须放在一个盘子里,所以返回1;当m==0(没有苹果可放)时,定义为1种放法; 【递归出口】
1、当n>m:则必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响。即 if(n>m) f(m,n) = f(m,m)
2、当n <= m:不同的放法可以分成两类:含有0的方案数,不含有0的方案数
(1) 含有0的方案数,即有至少一个盘子空着,即相当于 f(m,n)=f(m,n-1);
(2) 不含有0的方案数,即所有的盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即 f(m,n)=f(m-n,n
总的放苹果的放法数目等于两者的和,即 f(m,n)=f(m,n-1)+f(m-n,n)
【代码示例】
1 #include2 int fun(int m, int n) { //m个苹果放在n个盘子中共有几种方法(如 m=7 n=3 ) 3 if(m==0 || n==1) //如果有0个苹果(m==0),定义为1种放法 或 只有1个盘子(即 n==1),无论如何只有1种放法 4 return 1; 5 if(n>m) //当n>m(盘子数>苹果数):则必定有n-m个盘子永远空着(即每个盘子只放1个,占最多的盘子共m个,剩下n-m个), 6 return fun(m,m); //去掉它们对摆放苹果方法数目不产生影响。即 if(n>m) f(m,n) = f(m,m) 7 else 8 return fun(m,n-1)+fun(m-n,n); // 当n <= m:不同的放法可以分成两类:含有0的方案数,不含有0的方案数 9 /* 1、含有0的方案数【去盘子】:即有至少一个盘子空着,去掉这个盘子,不影响总结果 即 f(m,n)=f(m,n-1)10 2、不含有0的方案数【去苹果】:即所有的盘子都有苹果,若从每个盘子中拿掉一个苹果,不影响总结果,即 f(m,n)=f(m-n,n)11 */12 }13 14 int main(){15 int m,n;//m个苹果 n个盘子16 printf("input m,n:");17 scanf("%d%d",&m,&n);18 if( (m>=0&&m<10) && (n>0&&n<10) ){19 printf("count= %d",fun(m,n));20 }else{21 printf("你输入的数字不符合要求,请重新输入!");22 }23 24 return 0;25 }
【结果示例】