隨筆檔案(496)

如
15 = 15
15 = 7 + 8
15 = 4 + 5 + 6
15 = 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。

Java代碼

public static int split(int n) {
?? int m = 0, x, t1, t2;
?? for (int i = 1; (t1 = i * (i - 1) / 2) < n; i++) {
??? t2 = (n - t1);
??? x = t2 / i;
??? if (x <= 0)
???? break;
??? if ((n - t1) % i == 0) {
???? System.out.print(x + " ");
???? for (int j = 1; j < i; j++) {
????? System.out.print(x + j + " ");
???? }
???? System.out.println();
???? m++;
??? }
?? }
?? return m;
}