将正整数n表示成一系列正整数之和，n=n1+n2+…+nk,其中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所有不同的划分中，将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递推关系。(1)q(n,1)=1,n>=1;(2)q(n,m)=q(n,n),m>=n;最大加数n1不能大于n。(3)q(n,n)=1+q(n,m-1);n的划分由n1=n的划分和n1<=n-1的划分组成。(4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整数n的最大加n1不大于m的划分由n1=m的划分和n1<=m-1的划分组成。其算法可以写成：int q(int n,int m){    if((n<1)||(m<1))return 0;    if((n==1)||(m==1))return 1;    if(n<m)return q(n,n);    if(n==m)return q(n,m-1)+1;    return q(n,m-1)+q(n-m,m);}

评论