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
1
7 3
Sample Output
8

----------------------------------------------------------------------------题目结束-----------------------------------------------------------------------

解法：递归
思路（结合递归详述）：

递归的作用在于把问题的规模不断缩少，直到问题缩少到能简单地解决
问：那么在这个问题上，如何减少问题规模呢？
答：这个问题有 m 个苹果和 n 个盘子，明显地，分别减少 m 和 n 的个数。就能达到把整个问题规模减少。而 m 的减少需要以盘子的个数为最少单位进行缩少。

新问题与原问题有着相同的形式 www.zzzyk.com
当缩少规模后，产生的新问题与原问题的意思是一样。也即新问题具有相同的形式：同样是求 m 个苹果放到 n 个盘子上的放法

递归的结束需要简单情景
问：这个问题的简单情景是什么？
答：随着不断进行向下递归，会产生如下的几种简单情景：
n = 1，盘子剩下一个，即只有一种放法；
m < 0，即存在空盘子。所以这种情况包含了在 n 不断减少的情况中；
m = 0，即苹果已经全放完，没有多余。所以这属于一种放法；

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

----------------------------------------------------------------------------代码----------------------------------------------------------------------------

[cpp]
#include <iostream>
using namespace std;
int fun(int m, int n)
{
    //当苹果已全部放满时
    if (m == 0) return   1;
    //当盘子剩下一个时
    if (n == 1) return   1;
    //当m<0时候的放法包含在fun(m,n-1)中
    if (m < 0) return   0;

    return fun(m-n, n) + fun(m, n-1);
}
int main()
{
    int    t;
    int    m, n;
    cin >> t;
    while (t--)
    {
        cin >> m >> n;
        cout << fun(m, n) << endl;
    }
    return   0;
}

补充：软件开发 , C++ ,