指把一個正整數n寫成多個大於等於1且小於等於其本身的整數的和,則其中各加數所構成的集合為n的一個劃分。這是一個典型的遞歸算法。
基本介紹
- 中文名:整數劃分
概念,求劃分個數,分析,JAVA實現,利用計算機計算(C語言),求具體劃分集合,分析,利用計算機求解(C語言),
概念
所謂整數劃分,是指把一個正整數n寫成為
![](/img/1/479/81e40821a20899b2391f5918206d.jpg)
其中,
為正整數,並且
;
為n的一個劃分。
![](/img/a/399/a2ced6df2d66ec0c44f19b75119a.jpg)
![](/img/5/7d7/54f3f8fe83cd8784d1434629205b.jpg)
![](/img/0/5c5/a417518f4dfc50e78a425dcdb06f.jpg)
如果
中的最大值不超過m,即
,則稱它屬於n的一個m劃分。
![](/img/0/5c5/a417518f4dfc50e78a425dcdb06f.jpg)
![](/img/3/11a/8af56d46b91d9630417450822c04.jpg)
求劃分個數
分析
這裡我們記n的m劃分的個數為
。
![](/img/f/12f/9caddb5d4c5e6ad0060f9483911c.jpg)
例如,當n=4時,有5個劃分,即
,
,
,
,
。
![](/img/f/a2c/0f04cf2a1f1b17243191a1118991.jpg)
![](/img/3/e03/312f9c4f7b3ea3479787acd2afaa.jpg)
![](/img/a/b62/0a3f8d99a65e7f150f7eb33f58d4.jpg)
![](/img/9/ce9/637641e9464d860e0143a1fd7c66.jpg)
![](/img/2/30e/6bb868fc2b32a9e08818c36c8cad.jpg)
注意:
和
被認為是同一個劃分。
![](/img/8/64a/4b5f0a83c577893c883da41c3732.jpg)
![](/img/0/533/e7a6ba871b4cec6b6b2c8aee81f7.jpg)
根據n和m的關係,考慮一下幾種情況:
(一)當
時,無論m的值為多少
,只有一種劃分,即
。
![](/img/2/0b4/eeb25ec8443c585feb4ab2a71fa3.jpg)
![](/img/1/926/00e0c081731866ceaf07513489d6.jpg)
![](/img/1/a39/da41f194a60899935966647ca93a.jpg)
(二)當
時,無論n的值為多少,只有一種劃分,即n個1,
。
![](/img/f/df4/f053353625bdc65bc55da1d51917.jpg)
![](/img/a/cd5/a2b6de2fe8c1fa84d445aa49b478.jpg)
(三)當
時,根據劃分中是否包含n,可以分為以下兩種情況:
![](/img/2/a08/e2e1c7644c38dac75ff4ebf2d4b7.jpg)
(1)劃分中包含n的情況,只有一個,即
。
![](/img/a/551/a70697f58bc64334ae88b113b1c9.jpg)
(2)劃分中不包含n的情況,這時劃分中最大的數字也一定比n小,即n的所有
劃分。
![](/img/5/a6e/48fbb9fce1a105b83634f4489b02.jpg)
因此
。
![](/img/2/c6e/3e817500371bdfd6bae542d93c55.jpg)
(四)當
時,由於劃分中不可能出現負數,因此就相當於
。
![](/img/7/c6f/8dba13900a0977aa30107c3bdb21.jpg)
![](/img/1/1ee/2cdaf73d1d96f5cd3ae8a6c9cce5.jpg)
(五)當
時,根據劃分中是否包含最大值m,可以分為以下兩種情況:
![](/img/f/083/24f9df42c87edcdbb661d3d256c5.jpg)
(1)劃分中包含m的情況,即
,其中
的和為n-m,因此這種情況下為
。
![](/img/9/a10/a39f2e16b573729a46eb85308933.jpg)
![](/img/5/c47/72ca032da4cf7a24f669252019b3.jpg)
![](/img/5/df4/4e10fee5beb128755f045f7e9775.jpg)
(2)劃分中不包含m的情況,則劃分中所有值都比m小,即n的
劃分,個數為
。
![](/img/c/762/8a28fc90aec5012531a57f7f62b2.jpg)
![](/img/4/8c6/1e88f035141a0179d68b3976e9d9.jpg)
因此
。
![](/img/b/fc5/65917e85b99eb506d3c69fd8a38b.jpg)
綜上所述:
![](/img/d/27a/ed86bba381f230f11be0b7bfc5b4.jpg)
JAVA實現
/函式:q(int n,int m)//作用:用來得到正整數n,最大加數不大於m的劃分個數public static int q(int n,int m){ //若正整數或最大加數小於1,則返回0 if(n<1||m<1) return 0; //若正整數或最大加數等於1,則劃分個數為1(n個1相加) if(n==1||m==1) return 1; //若最大加數實際上不能大於正整數n,若大於則劃分個數等於最大加數為n的劃分個數 if(n<m) return q(n,n); //若正整數等於最大加數,則劃分個數等於 if (n==m) return 1+q(n,n-1); return q(n,m-1)+q(n-m,m);}
利用計算機計算(C語言)
#include<stdio.h>void main(){ int equation(int n,int m); int n,m; printf("Please input 'n'(0<n<100):"); scanf("%d",&n); printf("Please input 'm'(0<m<=n):"); scanf("%d",&m); printf("quantity:%d\n",equation(n,m));}int equation(int n,int m){ if(n==1||m==1) return (1); else if(n<m) return equation(n,n); else if(n==m) return 1+equation(n,n-1); else return equation(n-m,m)+equation(n,m-1);}
求具體劃分集合
分析
把一個正整數n分成
,若使
,可求出一種劃分,再使x遞減,令x是劃分好的數,按此方法繼續對y繼續進行分解,以此類推,直到
(不包含
)為止,這樣就求出了所有劃分。
![](/img/7/6a9/77c18ed80ff5148335ec883ebd35.jpg)
![](/img/9/3b0/5ca6128849ca257e22e9fd45181c.jpg)
![](/img/9/345/b3beffdc30cb7239b43901a9c99b.jpg)
![](/img/9/345/b3beffdc30cb7239b43901a9c99b.jpg)
在分解時應保證分解數x有序,即上一次的x要大於等於這一次的x,以避免求出元素相同但位置不同的結果。
例:當
時,部分過程如下圖所示:
![](/img/5/17d/2e5fbe9957b42531065c4f4c19c5.jpg)
![當n=6時的部分過程 當n=6時的部分過程](/img/b/585/nBnaukTNmBzNhJDN0IjZwMjYjBTYkNWMilTNyQ2Y2UWYmVzM3ADNkJmM2kzLptWa39yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
利用計算機求解(C語言)
#include<stdio.h>int x[50]={0};void main(){ void split(int n,int k); int n; printf("Please input 'n'(0<n<100):"); scanf("%d",&n); split(n,0);}void split(int n,int k)//k是數組中的位置,亦是遞歸層數{ void display(int k); int i; if(n==0)//分解完成,輸出結果 display(k); else for(i=n;i>0;i--) if(k==0||i<=x[k-1]) { x[k]=i;//寫入數組 split(n-i,k+1); }}//輸出數組前k項void display(int k){ int i; for(i=0;i<k;i++) printf("%d ",x[i]); printf("\n");}