POJ 1664 苹果放盘子（递归）

题目链接：http://poj.org/problem?id=1664

m个相同的苹果放在n个相同的盘子里，有多少种不一样的方法。

1. 例如，3个苹果放在4个盘子里有（3，0，0，0）（1，1，1，0）（2，1，0，0）3种方法。多出的1个盘子不影响结果。
2. 4个苹果放在3个盘子里（4，0，0）（3，1，0）（2，2，0）（2，1，1）
3. 4个苹果放在4个盘子里，{ 可以分解成全部盘子都摆上, 每个盘子里都至少有1个，f(m-n,n)，盘子有不摆的 f(m,n-1) }；f(4,4) = f(0,4) + f(4,3) = 1+4 = 5，（1，1，1，1）（4，0，0，0）（3，1，0，0）（2，2，0，0）（2，1，1，0）5种方法。f(0,n)表示每个盘子里都是一个苹果的情况。

当m < n 时，f(m,n) = f(m,m) 当m >= n 时，f(m,n) = f(m-n,n) + f(m,n-1)

终止条件： 苹果m = 1时，只有一种摆法 碟子n = 1时，只有一种摆法 m=n时，所有碟子都摆一个的摆法 f(m-n,n) = f(0,n) = 1

#include<iostream>
using namespace std;
unsigned long func(size_t apple, size_t disc)
{
    if(apple == 1 || apple == 0 || disc == 1)
        return 1;
    if(apple < disc)
        return func(apple, apple);
    else
        return func(apple, disc-1) + func(apple-disc, disc);
}
int main()
{
    size_t t, apple, disc;
    cin >> t;
    while(t--)
    {
        cin >> apple >> disc;
        cout << func(apple, disc) << endl;
    }
    return 0;
}