递归--练习4--noi666放苹果
一、心得
写出状态后勇敢假设
二、题目
666:放苹果
总时间限制:
1000ms 内存限制:
65536kB
描述
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
输入
第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。
输出
对输入的每组数据M和N,用一行输出相应的K。
样例输入
1
7 3
样例输出
8
三、AC代码
1 /*
2 noi666放苹果
3 这m个苹果一定要放
4 相当于在m这个队列里面分0-n-1刀
5 对实例
6 0刀:1一种
7 1刀:
8
9 递推关系式是什么样的呢
10 f(m,n)表示不同的放法
11 有篮子空:
12 f(m,n)=f(m,n-1)
13 一个篮子都不空:
14 f(m,n)=f(m-n,n)
15 故 f(m,n)= f(m,n-1)+ f(m-n,n)
16 边界条件:
17 n==1 1
18 m==1 1
19 m<n f(m,m)
20
21 */
22 #include <iostream>
23 using namespace std;
24 int f(int m,int n){
25 if(n<=1||m<=1) return 1;
26 if(m<n) return f(m,m);
27 else return f(m,n-1)+ f(m-n,n);
28 }
29 int main(){
30 int a,m,n;
31 cin>>a;
32 for(int i=1;i<=a;i++){
33 cin>>m>>n;
34 int ans=f(m,n);
35 cout<<ans<<endl;
36 }
37 return 0;
38 }