首页 > 代码库 > 摆鸡腿(递归)

摆鸡腿(递归)

Description
鸡腿具有无穷魅力,每个经历军训的人都对他有特别的感情。当无数鸡腿摆在我们面前时,我们该何去何从。
现在嘴馋的KG就面临着这种问题。现在他的面前有M个鸡腿,N个盘子。他要将这些鸡腿放在这N个盘子中。他一共有多少种不同分法。(如5,2和2,5是相同分法)

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

Output
对输入的每组数据M和N,用一行输出相应的K。

Sample Input
1
7 3

Sample Output
8

解题思路:

运用递归的思想,设f(m, n)为把m个鸡腿放入n个盘子的放法数,当盘子比鸡腿多时,即n>m时,放法数就是f(m,m)。
放的方案可分为两大类:盘子都不空或者至少一个盘子空着。
前者相当于先在每个盘子里放一个鸡腿,再求剩下鸡腿的放法,即f(m, n)可转化为f(m - n, n)。
后者相当于把m个鸡腿放入n - 1个盘子中,即f(m, n)可转化为f(m, n - 1)。
所以f(m, n) = f(m - n, n) + f(m, n - 1)。
n = 1时,只有一种放法,m = 0时也认为只有一种放法(相当于m个鸡腿放入m个盘子时,盘子不空,这时f(m - n,n) = f(0,n) = 1)

AC代码:

#include <stdio.h>
#include <math.h>
int Func(int m, int n)
{
    if(n == 1)
        return 1;
    if(m == 0)
        return 1;
    if(n > m)
        return Func(m, m);
    return Func(m, n-1) + Func(m - n, n);
}
int main()
{
    int M, N, t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &M, &N);
        printf("%d\n",Func(M, N));
    }
    return 0;
}