ε≡٩(๑>₃<)۶ 先来读题啊啊啊
题目背景
题目描述
把个同样的苹果放在个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分发
输入格式
第一行是测试数据的数目，以下每行均包括二个整数M和N，以空格分开。。
输出格式
对输入的每组数据和，用一行输出相应的。
输入输出样例
输入 #1
1
7 3
输出 #1
8
输入 #2
3
3 2
4 3
2 7
输出 #2
2
4
2
具体实现
这道题目要使用递归的思想，所谓递归，就是函数自己调用自己，并把问题的规模不断缩小。
别急，一步步教你！我们先假设有一个函数可以完成这道题，命名为rank，有apple和plate两个参数，分别表示有apple个苹果和plate个盘子。那改有哪些代码呢？别急先看看样例。
- 7和3，苹果数大于盘子数，此时就有两种情况，第一种是不存在空盘子，也就是每个盘子里先放上一个，就变为了苹果数减盘子数个苹果放到原来的盘子里，再加上第二种，存在空盘子，也就是原来的苹果放到盘子数减一个盘子里，然后一直循环就可以了。
- 再看2和7，盘子数大于苹果数，也就必定有空盘子，相当于把apple个苹果放到apple个盘子里，依次循环。
先把这些补上(づ｡◕ᴗᴗ◕｡)づ
if(apple>=plate){
// 1.用上所有盘子 2. 存在空盘子
return rank(apple-plate,plate) + rank(apple,plate-1);
}else{
return rank(apple,apple);
}
但是只有这些是不够的，这样函数就会陷入死循环（｀へ´），但如果加上中止条件，就不会发生这种事，那有什么中止条件呢？
- 当苹果没有了或只有一个时，只有一种放法，返回1.
- 当盘子只有一个时，只有一种放法，也返回1.
- 当没有盘子时，放不了，返回0.
把这些写在函数的开头( • ̀ω•́ )✧
if(apple == 1||apple==0) return 1;
if(plate==1)return 1;
if(plate==0) return 0;
这只是准备工作咳咳，函数写完了❥(ゝω・✿ฺ)
函数代码：
int rank(int apple,int plate){
if(apple == 1||apple==0) return 1;
if(plate==1)return 1;
if(plate==0) return 0;
if(apple>=plate){
// 1.用上所有盘子 2. 存在空盘子
return rank(apple-plate,plate) + rank(apple,plate-1);
}else{
return rank(apple,apple);
}
}
接下来就是主函数啦
定义变量，数组，分别是次判断，苹果和盘子的数量。
接下来循环输入，循环调用并输出。
代码ㄟ(≧◇≦)ㄏ
int main(int argc, char** argv) {
int n,a[20],p[20];
cin >> n;
for(int i = 0; i < n; i++){
cin>>a[i]>>p[i];
}
for(int i = 0; i < n; i++){
cout<<rank(a[i],p[i])<<endl;
}
return 0;
}
完整代码
请勿抄袭o(｀ω´*)o
#include<bits/stdc++.h>//万能头文件
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int rank(int apple,int plate){
if(apple == 1||apple==0) return 1;
if(plate==1)return 1;
if(plate==0) return 0;
if(apple>=plate){
// 1.用上所有盘子 2. 存在空盘子
return rank(apple-plate,plate) + rank(apple,plate-1);
}else{
return rank(apple,apple);
}
}
int main(int argc, char** argv) {
int n,a[20],p[20];
cin >> n;
for(int i = 0; i < n; i++){
cin>>a[i]>>p[i];
}
for(int i = 0; i < n; i++){
cout<<rank(a[i],p[i])<<endl;
}
return 0;
}
