整数划分问题

将正整数n表示成一系列正整数之和，

n=n₁+n₂+n₃+...+n_k (其中，n1≥n2≥...≥nk≥1,k≥1)

正整数n的这种表示称为正整数n的划分。正整数n的不同的划分个数称为正整数n的划分数，记作P(n)。

例如，正整数6有如下11种不同的划分，所以P(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;

在正整数n的所有不同的划分中，将最大加数N_max不大于m的划分个数记作Q(n,m)。

1. 首先我们能知道Q(n,1)=1,n≥1,就是N_max不大于1的时候，如Q(6,1)即为1+1+1+1+1+1这一种，所以Q(n,1)=1;
2. 当m大于n时，Q(n,m)=Q(n,n),因为最大加数Nmax不能大于n，所以有Q(1,m)=1，如Q(6,8)=Q(6,6);
3. Q(n,n)=1+Q(n,n-1),如Q(6,6)=1+Q(6,5)(其实6本身算不算做一种划分我不太确定……因为定义此问题的时候描述的是将正整数n表示成一系列正整数之和，而6本身并没有和其他正整数相加……但是书上是这么写的= =);
4. Q(n,m)=Q(n,m-1)+Q(n-m,m),n>m>1;

1 // 2 //  main.c 3 //  整数划分 4 // 5 //  Created by AslieLeo on 13-4-14. 6 //  Copyright (c) 2013年 AslieLeo. All rights reserved. 7 // 8  9 #include 
     
      10 11 int IntegerDivide(int n,int m){12     if((n<1)||(m<1)) {13         return 0;14     }15     if ((n==1)||(m==1)) {16         return 1;17     }18     if (n