整數劃分算法原理與實作

 整數劃分問題是将一個正整數n拆成一組數連加并等于n的形式，且這組數中的最大加數不大于n。

    如6的整數劃分為

    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種。下面介紹一種通過遞歸方法得到一個正整數的劃分數。

    遞歸函數的聲明為 int split(int n, int m);其中n為要劃分的正整數，m是劃分中的最大加數(當m > n時，最大加數為n)，

    1 當n = 1或m = 1時，split的值為1，可根據上例看出，隻有一個劃分1 或 1 + 1 + 1 + 1 + 1 + 1

    可用程式表示為if(n == 1 || m == 1) return 1;

    2 下面看一看m 和 n的關系。它們有三種關系

    (1) m > n

    在整數劃分中實際上最大加數不能大于n，是以在這種情況可以等價為split(n, n);

    可用程式表示為if(m > n) return split(n, n);    

    (2) m = n

    這種情況可用遞歸表示為split(n, m - 1) + 1，從以上例子中可以看出，就是最大加

    數為6和小于6的劃分之和

    用程式表示為if(m == n) return (split(n, m - 1) + 1);

    (3) m < n

    這是最一般的情況，在劃分的大多數時都是這種情況。

    從上例可以看出，設m = 4，那split(6, 4)的值是最大加數小于4劃分數和整數2的劃分數的和。

    是以，split(n, m)可表示為split(n, m - 1) + split(n - m, m)

    根據以上描述，可得源程式如下：

#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的劃分數: %d", split(12, 12));

    return 0;

}

将正整數劃分成連續的正整數之和

如15可以劃分成4種連續整數相加的形式：

15

7 8

4 5 6

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。

    這裡還有一個問題，這個i的最大值是多少？不過有一點可以肯定，它一定比n小。我們可以做一個假設，

假設n可以拆成最小值為1的劃分，如上例中的1 2 3 4 5。這是n的最大數目的劃分。如果不滿足這個假設，

那麼 i 一定比這個劃分中的正整數個數小。是以可以得到這樣一個公式i * (i + 1) / 2 <= n，即當i滿足

這個公式時n才可能被劃分。

綜合上述，源程式如下

int split1(int n)

    int i, j, m = 0, x, t1, t2;

   // 在這裡i + 1之是以變為i - 1，是因為i * (i - 1) / 2這個式子在下面多次用到，

  // 為了避免重複計算，是以将這個值計算完後儲存在t1中。并且将<= 号變為了<号。

    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;

 本文轉自 androidguy 51CTO部落格，原文連結：http://blog.51cto.com/androidguy/215393，如需轉載請自行聯系原作者