天天看点

pku 1664 分苹果(整数划分)

#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}

*/

继续阅读