问题描述

把 M 个同样的苹果放在N 个同样的盘子里，允许有的盘子空着不放，问共有多少

种不同的分法？（用K 表示）注意：5，1，1 和1，5，1 是同一种分法。

输入数据

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含两个整数M 和N，以

空格分开。1<=M，N<=10。

输出要求

对输入的每组数据M 和N，用一行输出相应的K。

输入样例

1

7 3

输出样例

8

我的思路：因为题目是用递归做的。我就想如何可以原来问题分解了一个更小的问题，又因为盘子都一样的。先考虑第一个盘子放苹果的情况，然后递归的考虑后面的各种情况，为了必要重复，我还设定了他们放苹果的数量是递减的。同时还要考虑N>M的情况其实和N=M的情况是一样的。于是我就写出了这个四不像的算法。我也不知道是什么东西，但是能出结果，还能AC。。。哈哈。 

后来想想，我的方法有点像是搜索的方式，DFS(Depth first search)。即我先把前面我说的那些条件（按苹果数递减放）设定好，然后DFS去搜索每个盘放苹果的情况，当剩下最后一个盘的时候，就能得到一种情况。

#include 
     
      int M,N,nSum;void recursion(int nCount,int left,int prio){    int i;    if (nCount == N-1 )    {        if (left <= prio)          {            nSum++;        }    }    else    {        for (i =prio; i >= 0; i--)        {            if (i <= left)  //当前的值必须小于剩下的苹果数            {                recursion(nCount+1,left-i,i);            }        }    }}int main(){    int t;    scanf("%d",&t);    while (t)    {        t--;        nSum=0;        scanf("%d%d",&M,&N);        if(N > M) N=M;        recursion(0,M,M);        printf("%d\n",nSum);    }    return 0;} 2013/5/15 22:18
     

 其实真正的递归是这样的，考虑两种情况：

• 每个盘都放有苹果。即每个盘已经放有苹果，这时的情况和把剩下m-n个苹果放到n个盘的情况是一样的，f(m-n,n);
• 至少有一个盘不放苹果。即把m个苹果放到n-1个盘子。f(m,n-1);

　当然必须考虑m<n时，此时和f(m,m)的情况是一样的。

最后判断程序的出口：当苹果数量为0或者盘数只剩1那么就表明找到一种情况。

#include 
     
      int recursion(int m, int n){    if (m == 0 || n == 1) return 1;    if (m < n) return recursion(m,m);    return recursion(m,n-1) + recursion(m-n,n);}int main(){    int m,n,t;    scanf("%d",&t);    while (t)    {        t--;        scanf("%d%d",&m,&n);        printf("%d\n",recursion(m,n));    }    return 0;} 2013/5/15 22:18