C語(yǔ)言之整數(shù)劃分問題（遞歸法）實(shí)例代碼
整數(shù)劃分問題是算法中的一個(gè)經(jīng)典命題之一，有關(guān)這個(gè)問題的講述在講解到遞歸時(shí)基本都將涉及。所謂整數(shù)劃分，是指把一個(gè)正整數(shù)n寫成如下形式：
n=m1+m2+...+mi; （其中mi為正整數(shù)，并且1 <= mi <= n），則{m1,m2,...,mi}為n的一個(gè)劃分。
如果{m1,m2,...,mi}中的最大值不超過m，即max(m1,m2,...,mi)<=m，則稱它屬于n的一個(gè)m劃分。這里我們記n的m劃分的個(gè)數(shù)為f(n,m);
例如但n=4時(shí)，他有5個(gè)劃分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};
注意4=1+3 和 4=3+1被認(rèn)為是同一個(gè)劃分。
該問題是求出n的所有劃分個(gè)數(shù)，即f(n, n)。下面我們考慮求f(n,m)的方法;
1.遞歸法：
根據(jù)n和m的關(guān)系，考慮以下幾種情況：
(1)當(dāng)n=1時(shí)，不論m的值為多少（m>0)，只有一種劃分即{1};
(2)當(dāng)m=1時(shí)，不論n的值為多少，只有一種劃分即n個(gè)1，{1,1,1,...,1};
(3)當(dāng)n=m時(shí)，根據(jù)劃分中是否包含n，可以分為兩種情況：
(a)劃分中包含n的情況，只有一個(gè)即{n}；
(b)劃分中不包含n的情況，這時(shí)劃分中最大的數(shù)字也一定比n小，即n的所有(n-1)劃分。
因此 f(n,n) =1 + f(n,n-1);
(4)當(dāng)n<m時(shí)，由于劃分中不可能出現(xiàn)負(fù)數(shù)，因此就相當(dāng)于f(n,n);
(5)但n>m時(shí)，根據(jù)劃分中是否包含最大值m，可以分為兩種情況：
(a)劃分中包含m的情況，即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和為n-m，因此這情況下
為f(n-m,m)
(b)劃分中不包含m的情況，則劃分中所有值都比m小，即n的(m-1)劃分，個(gè)數(shù)為f(n,m-1);
因此 f(n, m) = f(n-m, m)+f(n,m-1);
綜上所述：
|
1
2
3
4
5
6
7
|
f(n, m)= 1; (n=1 or m=1) f(n,m) = f(n, n); (n<m) 1+ f(n, m-1); (n=m) f(n-m,m)+f(n,m-1); (n>m) |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include<iostream>using namespace std;int equationCount(int n,int m){ if(n==1||m==1) return 1; else if(n<m) return equationCount(n,n); else if(n==m) return 1+equationCount(n,n-1); else return equationCount(n,m-1)+equationCount(n-m,m);}int main(void){ int n; while(scanf("%d",&n)!=EOF&&(n>=1&&n<=120)) { printf("%d\n",equationCount(n,n)); } return 0;} |
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
原文鏈接：http://www.cnblogs.com/dolphin0520/archive/2011/04/04/2005098.html
