一、题目描述
把m个同样的苹果放在n个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?
注意:如果有7个苹果和3个盘子,(5,1,1)和(1,5,1)被视为是同一种分法。
数据范围:0≤m≤10 ,1≤n≤10 。
二、输入描述
输入两个int整数。
三、输出描述
输出结果,int型。
四、解题思路
- 读取输入的整数 m 和 n;
- 创建一个递归函数 count(m, n) 来计算当前持有 m 个苹果,有 n 个盘子可供存放时的摆放方案数;
- 定义递归函数的终止条件:
- 当苹果数 m 等于 0 时,表示什么都不做,返回 1 种方案;
- 当盘子数 n 等于 1 时,剩下的苹果 m 只能全部摆放在这个盘子中,返回 1 种方案;
- 当盘子数 n 大于苹果数 m 时,一定有 n - m 个盘子空着,而且每个盘子都一样,因此 count(m, n) 等于 count(m, n-1);
- 当盘子数 n 小于等于苹果数 m 时,有两种情况:
- 至少有一个盘子可以不放苹果,因此 count(m, n) 等于 count(m, n-1);
- 至少每个盘子都有一个苹果,摆放后剩下的苹果数为 m - n,因此 count(m, n) 等于 cou