随笔档案(496)

如
15 = 15
15 = 7 + 8
15 = 4 + 5 + 6
15 = 1 + 2 + 3 + 4 + 5

首先考虑一般的形式，设n为被划分的正整数，x为划分后最小的整数，如果n有一种划分，那么

结果就是x,如果有两种划分，就是x和x x + 1， 如果有m种划分，就是 x 、x x + 1 、 x x + 1 x + 2 、... 、x x + 1 x + 2 ... x + m - 1

将每一个结果相加得到一个公式(i * x + i * (i - 1) / 2) = n，i为当前划分后相加的正整数个数。

满足条件的划分就是使x为正整数的所有情况。

如上例，当i = 1时，即划分成一个正整数时，x = 15， 当i = 2时， x = 7。

当x = 3时，x = 4， 当x = 4时，4/9，不是正整数，因此，15不可能划分成4个正整数相加。

当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;
}