|
|
邀请回答
马上注册,享受更多特权
您需要 登录 才可以下载或查看，没有帐号？立即注册 
x
放苹果 
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问有多少种不同的分法？（用K表示）5,1,1,1和1,5,1是同一种分法。每个用例包含二个整数M和N。0<=M<=10,1<=N<=10。
解析：采取递归思想，分为两种情况，m为苹果数，n为盘子数
设f(m,n)为m个苹果，n个盘子的放法数目，则先对n进行讨论
一：
当n>m时，必定有n-m个盘子永远空着，去掉它们对摆放方法数目不产生影响，就是将m个苹果分到m个盘子的方法。即f(m,n)=f(m,m);
二：
当n<m时，那么
1、将至少其中一个盘子不放，就是将m个苹果放到n-1个盘子的方法，即：f(m,n)=f(m,n-1);
2、每个盘子放一个，然后将m-n个苹果放在n个盘子的方法，或者说，所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响放法的数目，即f(m,n)=f(m-n,n);
而总的放法数目等于两者之和。
递归出口条件说明：
当n=1时，所有苹果都放在一个盘子里，所以返回1；
当没有苹果可放时，定义为一种放法；
递归的两条路，第一条n会逐渐减少，最终会达到出口n=1;
第二条m会逐渐减少，因为n>m时，会返回f(m,m),所以最终会达到出口m=0。
- <p>#include<stdio.h>
- int fun(int m, int n)
- {
- if(m<0||m>10||n<1||n>10)
- return -1;
- if(m==0||n==1)
- return 1;
- if(m<n)
- return fun(m,n);
- else
- return fun(m,n-1)+fun(m-n,n);
- }
- int main(){
- int m,n; //m个苹果，n个盘子
- while(scanf("%d%d",&m,&n)！=E0F)
- {
- printf("%d\n",fun(m,n));
- }
- return 0;</p><p>}</p>
|
|
