把m个同样的苹果放在n个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
数据范围:0<=m<=10,1<=n<=10。
本题含有多组样例输入。
这个题本来想着用排列组合求解的,然后发现我算的不太对,就算去重也是有问题的,所以用了递归,后面想到方***再回来做一下。
#include<stdio.h>
int fun(int m,int n){
if(n==1||m==0){
return 1;
}else if(n>m){
return fun(m,m);
}else{
return fun(m,n-1)+fun(m-n,n);
}
}
//当只有一个盘子或没有苹果时,定义为一种方式
//盘子数大于苹果数
//必然有空的盘子,把空的盘子去掉后放法数目不变
//可能有一个盘子空着(拿走,总的放法数目不变),或者都不空(每个盘子拿走一个继续算)
int main(){
int n,m;
while(scanf("%d %d",&m,&n)!=EOF){
printf("%d\n",fun(m,n));
}
}