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}

*/