#include <iostream>
using namespace std;
int f(int m, int n)
{
if(m < 0)
return 0;
if(m == 0 || n == 1)
return 1;
return f(m, n-1) + f(m-n, n);
}
int main()
{
int n;
scanf("%d", &n);
int M, N;
while(n--)
{
scanf("%d%d", &M, &N);
printf("%d/n", f(M,N));
}
return 0;
}
//本题是很简单的递推:
//①最少的盘子放了一个,这样每个盘子至少一个,n个盘子先放上n个,剩下的m-n个可以随便放
//②最少的盘子没有放,这样剩下的n-1个盘子还是随便放m个
/*
引用大牛的话:
看到这道题立即想到了递归的经典案例:整数划分问题。
将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,
其中n1≥n2≥…≥nk≥1,k≥1。
正整数n的这种表示称为正整数n的划分。求正整数n的不
同划分个数。
例如正整数6有如下11种不同的划分:
6;
5+1;
4+2,4+1+1;
3+3,3+2+1,3+1+1+1;
2+2+2,2+2+1+1,2+1+1+1+1;
1+1+1+1+1+1。
将最大加数x不大于m的划分个数记作q(n,m)
有
1 n=1 || m=1
q(n,m) = { q(n,n) n<m
1+q(n,n-1) n=m
q(n,m-1)+q(n-m,m) n>m>1
重点在n>m>1的情况。
呵呵,当时我还花了好些功夫才理解到哦,真是精妙。有了这一点经验,放苹果的问题就容易了,我们也有递归式
将在m个盘中放n个苹果记作fun(m,n),且不能有空盘。(题目中的可以有空盘 不方便递归,我们循环累加)
对于fun(m,n)
1 n=1||m=n
resulut = 0 n<m
∑ fun(n-m,i) n>=m , i=1..n
当n>=m时,是不是方法和整数划分问题的n>m>1时很像呢?呵呵
于是我们得到代码
1#include "stdio.h"
2int fun(int m,int n)
3{
4int i,result;
5if(n==1||m==n) return 1;
6 else if(n<m) return 0;
7 else
8 {
9 result=0;
10 for(i=1;i<=n;i++)
11 result+=fun(n-m,i);
12 return result;
13 }
14}
15void main()
16{
17int T,m,n,k,i;
18int result=0;
19scanf("%d",&T);
20while(T--)
21{
22 scanf("%d %d",&m,&n);
23 for(i=1;i<=n;i++)
24 result=result+fun(m,i);
25 printf("%d/n",result);
26}
27}
*/