將一個整數劃分為多個正整數之和

整數劃分問題是將一個正整數n拆分成一組數連加并等于n的形式，顯然這組數中最大加數不大于n。 令n為需要劃分的整數，m為劃分后的最大整數。例如將6劃分為最大加數為6的劃分形式如下： 65 + 14 + 2, 4 + 1 + 13 + 3, 3 + 2 +1, 3 + 1 + 1 + 12 + 2 + 2, 2 + 2

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

令n為需要劃分的整數，m為劃分后的最大整數。例如將6劃分為最大加數為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中劃分方法。若劃分后最大整數為2，則劃分形式為最后兩行，共4種劃分方法。易得可利用遞歸方式求解，設劃分函數split(int n,int m)，其中n為需要劃分的整數，m為劃分后的最大加數。

(1) m < 1 或者n < 1時，劃分方式共0種。

(2) m = 1或者n = 1時，劃分方式共1中。

(3) n < m時，因為整數劃分中最大加數不可能大于n，因此此種情況等價為split(n, n)。

(4) m=n時，劃分分為兩種：一種是最大加數為m-1的，共split(n, m-1)中劃分方式；一種是其中一個加數為m的（當然不存在另一個加數，或者說另一個加數為0）。因此，m=n時共split(n, m-1) + 1種劃分方式。

(5) m < n時，同樣存在兩種劃分：一種是最大加數m-1的，共split(n, m-1)；另外一種是其中一個加數為m的，緊接著只需要對n-m進行劃分即可且最大加數為m，因此共split(n - m，m)種劃分方式。因此，m < n時共split(n, m-1) + split(n-m, m)中劃分。

源代碼如下：

#include 
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));
}

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com