题目描述

　　把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

输入描述

　　每个用例包含二个整数M和N。0<=m<=10，1<=n<=10。

输出描述

　　输出一个数字，表示放苹果方法总数。

输入样例

7 3

输出样例

8

解题分析

　　设f(m, n)为m个苹果，n个盘子的放法。

　　当n > m，有n - m个盘子永远空着，去掉他们对摆放苹果的数目不产生影响。即if(n > m)   f(m, n) = f(m, m);

　　当m >= n，不同的放法可分为两类：

　　1) 有至少一个盘子空着，即相当于f(m, n) = (m, n - 1);

　　2) 所有的盘子至少都有一个苹果，则还剩m - n个苹果放在n个盘子中，即f(m, n) = f(m - n, n);

　　结束递归的条件

　　1) n = 1时，只有一种放法，所有的苹果都放在一个盘子里，所以返回1。

　　2) m = 0时，说明所有苹果发放完毕，返回1。

测试代码

1 #include 
     
       2  3 int putApples(int m, int n) 4 { 5     if (m == 0 || n == 1) 6     { 7         return 1; 8     } 9     if (m < n)10     {11         return putApples(m, m);12     }13     return putApples(m, n - 1) + putApples(m - n, n);14 }15 16 int main(void)17 {18     int m, n;19     while (scanf("%d%d", &m, &n) != EOF)20     {21         printf("%d\n", putApples(m, n));22     }23     return 0;24 }