拿苹果

描述

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

输入

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

输出

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

样例输入

1

7 3

样例输出

8

分析：

设i个苹果放在k个盘子里放法总数是 f(i,k)，则： k > i 时， f(i,k) = f(i,i) k <= i 时，总放法 =
有盘子为空的放法+没盘子为空的放法 f(i,k) = f(i,k-1) + f(i-k,k)

注意：

这个没盘子为空的算法，首先做一步，往每个盘子放一个苹果。然后苹果剩下i-k，把他们放到k个盘子里面

#include <iostream>
using namespace std;

int f(int m, int n)
{
    if(m < n)
       return f(m, m);
    if(m == 0)
        return 1;
    if(n == 0)
        return 0;
    return f(m, n-1)+f(m-n, n);
}
int main()
{
    int T;
    int m, n;
    cin >> T;
    while(T--)
    {
       cin >> m >> n;
       cout << f(m, n) << endl;
    }
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
 

文章来源: recclay.blog.csdn.net，作者：ReCclay，版权归原作者所有，如需转载，请联系作者。

原文链接：recclay.blog.csdn.net/article/details/60865505