问题：将以正整数n表示成一系列正整数之和.
n=n1+n2+n3+...+nk (n1>=n2>=n3>=nk>=1, k>=1)
这就是正整数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;
则求任意正整数的划分数p(n).
解决：在所有划分中，将最大加数n1不大于m的划分个数记作q(n, m).
so we have this relation:
(1) q(n, 1) = 1, n>=1
最大加数不大于1,则只有一种划分，n=1+1+1+...+1
(2) q(n, m) = q(n, n), m>=n
m larger n is impossinle. so q(1, m)==1
(3) q(n, n) = 1 + q(n, n-1)
n1=n and n1<=n-1
(4) q(n, m) = q(n, m-1) + q(n-m, m), n>m>1
n1=m and n1<=m-1
so the program is :
int q(int n, int m)
{
if((n<1) || (m<1)) return 0;
if((n==1)|| (m==1)) return 1;
if(n<m) returnq(n, n);
if(n==m) return(q(n, m-1)+1);
if(n>m) return(q(n,m-1) + q(n-m, m));
}
|