题目

小蒜想知道把 MM 个同样的苹果放在 NN 个同样的盘子里,允许有的盘子空着不放,共有多少种不同的分法?(用 KK 表示)55,11,11 和 11,55,11 是同一种分法。

输入格式

第一行是测试数据的数目 t(0 \le t \le 20)t(0≤t≤20)。
以下每行均包含两个整数 MM 和 NN,以空格分开。1 \le M, N \le 101≤M,N≤10。

输出格式

对输入的每组数据 MM 和 NN,用一行输出相应的 KK。

样例输入

1
7 3

样例输出

8

解题思路

该题目主要运用了递推的思维方式,解决的关键在于找出
```递推关系```和```递推出口```。
m个苹果放在n个盘子中,设递推函数为apple(m,n):
**情况1:**
m=0,没有一个苹果,则apple(0,n)=1;
**情况2:**
n=1,只有一个盘子,则apple(m,1)=1
**情况3:**
n>m,与m个苹果放在m个盘子中情况一样,则apple(m,n)=m
**情况4:**
n<=m,按是否有空盘子,又可以分为两种情况: 1. 不是所有盘子都有苹果(至少有一个盘子没有苹果),则apple(m,n-1) 2. 所有盘子都有苹果(至少每个盘子都有一个苹果),m个苹果中有n个放在n个盘子里,剩下m-1个苹果,这种情况和m-n个苹果放在n个盘子中是一样的,即apple(m-n,n),则有以下递推关系: $apple(m,n)=apple(m-n,n)+ apple(m,n-1)$ 综上所述:可以将情况1和情况2视为一种临界条件,即为n=1时,所有苹果都在一个盘子中;m=0时,没有苹果可放!这种临界条件通常可以视为
```递归出口```。

解题源码

#include <iostream>
using namespace std;
int apple(int m,int n) {
    if(m<=1||n==1)        return 1; 
    if(n>m) 
        return apple(m,m);  
    else 
        return(apple(m-n,n)+apple(m,n-1));
}
int main() {
    int n,a[20],b[20],i; 
    cin>>n;   
    for(i=0;i<n;i++) 
        cin>>a[i]>>b[i];  
    for(i=0;i<n;i++)   {
          cout<<apple(a[i],b[i])<<endl;
      } 
    return 0;
}