例如：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). 我們可以建立如下遞歸關系: (1) q(n, 1) = 1, n>=1 最大加數不大於1,則只有一種劃分，n=1+1+1+...+1 (2) q(n, m) = q(n, n), m>=n 最大加數n1實際上不能大於n.因此q(1, m)=1 (3) q(n, n) = 1 + q(n, n-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的劃分組成. 於是計算q(n, m)的遞歸函數如下.顯然p(n)=q(n,n) 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)); } 為求n的所有劃分,需要在上面求n的劃分數的過程中將劃分元素保存起來並輸出. [cpp] #include <iostream> using namespace std; 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); // return 0; } int main() { //cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!! cout << q(10,10); return 0; }
