分苹果算法「建议收藏」

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？M, N为自然数。说明：如有7个苹果，2个盘子，则(5, 1, 1)和(1, 5, 1)和(1, 1, 5)都是同一种分法。

第一行一个整数表示数据的组数（多组数据），对于每组数据第一行是苹果个数M (1 ≤ m ≤ 100) ，第二行是盘子个数N(1 ≤ n ≤ 100)。

每组数据输出一行,放苹果的方法个数。

1 3 2

/*思路1： 122 212 221是同种方法,则取代表 221123 .321 是同种方法,则取代表 321能当“代表”的组合的特点是,前面的不小于后面的.这是一个限制条件.想来想去用递归最好.比如10个放入3个篮子,变成：第一个放10,再把0个放入剩余2个篮子第一个放9,再把1个放入剩余2个篮子第一个放8,再把2个放入剩余2个篮子第一个放7,再把3个放入剩余2个篮子.总之,M个苹果,N个篮子,第一个放a个,a的范围是从M减小到0,而再将(M-a)个苹果放入N-1个篮子.但是放的时候要一定满足“前面的不小于后面的”.思路2：f(m, n)表示将m个苹果放入n个盘子 f(10,3) = f(10, 2) + f(7, 3) 10个苹果放入3个盘子 = 10个苹果放入2个盘子（有空盘子，有一个盘子不放）+ 7个苹果放入3个盘子（没有空盘子，每一个盘子里面先各放一个苹果，就只剩下7个苹果） 

然后递归 ，下面算法按思路2解 */ #include<stdio.h>  int fun(int m,int n){       if(m==0||n==1)            return 1;         if(n>m)          return fun(m,m);  //如果前面的小于后面的，则一定会有空盘子，则等于m个苹果放入m个盘子     else          return fun(m,n-1)+fun(m-n,n);  //有空盘子的情况 +　没有空盘子的情况 }  int main(){      int t,m,n;      scanf("%d",&t);      while(t--){             scanf("%d%d",&m,&n);          printf("%d\n",fun(m,n));      }      return 0;  }