题目描述

　　把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 }