题目相关
题目描述
把 m个同样的苹果放在 n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法。（5,1,1 和 1,1,5 是同一种方法）
输入格式
第一行是测试数据的数目 t，以下每行均包括二个整数 m和 n，以空格分开。
输出格式
对输入的每组数据 m和 n，用一行输出相应的结果。
输入输出样例
输入1
1
7 3
输出 1
8
输入 2
3 3 2 4 3 2 7
输出 2
2 4 2
说明/提示
对于所有数据，保证：(1leq m,nleq 10,0 leq t leq 20)。
原题链接
P2386 放苹果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
分析
首先阅读题目，发现这题特殊在有的盘子能够空着不放。那么，分类讨论下，对于摆放的情况，就有可能出现所有盘子都有苹果或者是有盘子空着不放两种情况。
我们先设计这样一个函数fun(m,n)他的作用就是返回m个苹果放n个盘子中的方法数。接着，继续来讨论苹果的分配情况。
首先，如果苹果的数量少于盘子的数量，那么最多也就用上和苹果数量相同的盘子，剩下的盘子就用不上了。那么就相等于，m个苹果放在m个盘子中的分法。
接着，如果苹果数量比盘子数量多，那么就会出现最开始讨论的两种情况，一是每个盘子都有苹果，二是有的盘子空着不放。那么只要分别求出这两种情况对应的放法数，两者相加就能得到答案了。
先考虑下，每个盘子都放有苹果的情况，这样的话，每个盘子中就至少会有一个苹果存在，那么剩下的苹果分配放法就是盘子放满的放法数。(fun(m,n)放满=fun(m-n,n))。
再来考虑。有盘子会空着不放的情况。他有可能是一个空盘，或两个空盘，或更多的空盘。而不论空几个盘子，他们都至少会空出一个盘子出来，那么这个空出来的盘子就没用了，也就相当于把苹果分配到n-1个盘子中。(fun(m,n)有空盘=fun(m,n-1))。
由此，总结下：
这样一分析，就能发现很明显的递归过程了。递归实现的两个要点1. 递归过程 2. 终止条件。递归过程有了，那么再来想想终止条件应该是什么，观察我们找到的解决方法，发现是苹果的数量和盘子的数量在不断减少，那么肯定是不可能无止境的少下去的，那么就想想少到什么时候会有显而易见的答案呢？盘子如果，只有一个，那么肯定就只有一种放法，苹果只有一个或者说零个，那么也只有一种放法。由此，就得到了递归的终止条件。再整合下：
代码实现
#include<iostream>
using namespace std;
int t,M,N;
int apple(int m,int n){
if(m==1||n==1||m==0){// 终止条件
return 1;
}
if(m>=n){//苹果比盘子多
return apple(m,n-1)+apple(m-n,n);
}else{//苹果比盘子少
return apple(m,m);
}
}
int main(){
cin>>t;
for(int i=0;i<t;i++){
cin>>M>>N;
cout<<apple(M,N)<<'
';
}
return 0;
}
