本文為原創(chuàng)，如需轉(zhuǎn)載，請注明作者和出處，謝謝！
整數(shù)劃分問題是將一個正整數(shù)n拆成一組數(shù)連加并等于n的形式，且這組數(shù)中的最大加數(shù)不大于n。
如6的整數(shù)劃分為
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
共11種。下面介紹一種通過遞歸方法得到一個正整數(shù)的劃分?jǐn)?shù)。
遞歸函數(shù)的聲明為 int split(int n, int m);其中n為要劃分的正整數(shù)，m是劃分中的最大加數(shù)(當(dāng)m > n時，最大加數(shù)為n)，
1 當(dāng)n = 1或m = 1時，split的值為1，可根據(jù)上例看出，只有一個劃分1 或 1 + 1 + 1 + 1 + 1 + 1
可用程序表示為if(n == 1 || m == 1) return 1;
2 下面看一看m 和 n的關(guān)系。它們有三種關(guān)系
(1) m > n
在整數(shù)劃分中實際上最大加數(shù)不能大于n，因此在這種情況可以等價為split(n, n);
可用程序表示為if(m > n) return split(n, n);
(2) m = n
這種情況可用遞歸表示為split(n, m - 1) + 1，從以上例子中可以看出，就是最大加
數(shù)為6和小于6的劃分之和
用程序表示為if(m == n) return (split(n, m - 1) + 1);
(3) m < n
這是最一般的情況，在劃分的大多數(shù)時都是這種情況。
從上例可以看出，設(shè)m = 4，那split(6, 4)的值是最大加數(shù)小于4劃分?jǐn)?shù)和整數(shù)2的劃分?jǐn)?shù)的和。
因此，split(n, m)可表示為split(n, m - 1) + split(n - m, m)
根據(jù)以上描述，可得源程序如下：
#include <stdio.h>
int split(int n, int m)
{
if(n < 1 || m < 1) return 0;
if(n == 1 || m == 1) return 1;
if(n < m) return split(n, n);
if(n == m) return (split(n, m - 1) + 1);
if(n > m) return (split(n, m - 1) + split((n - m), m));
}
int main()
{
printf("12的劃分?jǐn)?shù): %d", split(12, 12));
return 0;
}
將正整數(shù)劃分成連續(xù)的正整數(shù)之和
如15可以劃分成4種連續(xù)整數(shù)相加的形式：
15
7 8
4 5 6
1 2 3 4 5
首先考慮一般的形式，設(shè)n為被劃分的正整數(shù)，x為劃分后最小的整數(shù)，如果n有一種劃分，那么
結(jié)果就是x,如果有兩種劃分，就是x和x x + 1， 如果有m種劃分，就是 x 、x x + 1 、 x x + 1 x + 2 、... 、x x + 1 x + 2 ... x + m - 1
將每一個結(jié)果相加得到一個公式(i * x + i * (i - 1) / 2) = n，i為當(dāng)前劃分后相加的正整數(shù)個數(shù)。
滿足條件的劃分就是使x為正整數(shù)的所有情況。
如上例，當(dāng)i = 1時，即劃分成一個正整數(shù)時，x = 15， 當(dāng)i = 2時， x = 7。
當(dāng)x = 3時，x = 4， 當(dāng)x = 4時，4/9，不是正整數(shù)，因此，15不可能劃分成4個正整數(shù)相加。
當(dāng)x = 5時，x = 1。
這里還有一個問題，這個i的最大值是多少？不過有一點可以肯定，它一定比n小。我們可以做一個假設(shè)，
假設(shè)n可以拆成最小值為1的劃分，如上例中的1 2 3 4 5。這是n的最大數(shù)目的劃分。如果不滿足這個假設(shè)，
那么 i 一定比這個劃分中的正整數(shù)個數(shù)小。因此可以得到這樣一個公式i * (i + 1) / 2 <= n，即當(dāng)i滿足
這個公式時n才可能被劃分。
綜合上述，源程序如下
int split1(int n)
{
int i, j, m = 0, x, t1, t2;
// 在這里i + 1之所以變?yōu)閕 - 1，是因為i * (i - 1) / 2這個式子在下面多次用到，
// 為了避免重復(fù)計算，因此將這個值計算完后保存在t1中。并且將<= 號變?yōu)榱?lt;號。
for(i = 1; (t1 = i * (i - 1) / 2) < n; i++)
{
t2 = (n - t1);
x = t2 / i;
if(x <= 0) break;
if((n - t1) % i == 0)
{
printf("%d ", x);
for(j = 1; j < i; j++)
printf("%d ", x + j);
printf("\n");
m++;
}
}
return m;
}
新浪微博：http://t.sina.com.cn/androidguy 昵稱：李寧_Lining