poj_1664_放苹果_解题报告

题目出处

----------------------------------------题目----------------------------------------

Description

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

Input

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

Output

对输入的每组数据M和N，用一行输出相应的K。Sample Input
17 3Sample Output
8
----------------------------------------题目结束-----------------------------------

解法：递归思路（结合递归详述）：
递归的作用在于把问题的规模不断缩少，直到问题缩少到能简单地解决问：那么在这个问题上，如何减少问题规模呢？答：这个问题有 m 个苹果和 n 个盘子，明显地，分别减少 m 和 n 的个数。就能达到把整个问题规模减少。而 m 的减少需要以盘子的个数为最少单位进行缩少。
新问题与原问题有着相同的形式
当缩少规模后，产生的新问题与原问题的意思是一样。也即新问题具有相同的形式：同样是求 m 个苹果放到 n 个盘子上的放法
递归的结束需要简单情景问：这个问题的简单情景是什么？答：随着不断进行向下递归，会产生如下的几种简单情景：

n = 1，盘子剩下一个，即只有一种放法； m < 0，即存在空盘子。所以这种情况包含了在 n 不断减少的情况中； m = 0，即苹果已经全放完，没有多余。所以这属于一种放法；

递归跳跃的信任我们这里只需要思考：如何做能让问题规模减少、如何正确分析出简单情景即可。我们不需要去过多思考实现细节。
----------------------------------------代码----------------------------------------