一個正整數拆分成n個數的和，整數拆分問題詳解

http://blog.csdn.net/pipisorry/article/details/37879761

問題：?

給定一個整數n，要找出n能拆分成多少種不同的若干個數的和與乘積的形式。比如：

??? 4=4?????????????????? 12=1*12
??? 4=1+3?????????????? 12=2*6
??? 4=2+2?????????????? 12=3*4
??? 4=1+1+2?????????? 12=2*2*3

一個正整數拆分成n個數的和，??? 4=1+1+1+1

加法形式：

方法1：

100的整數拆分有多少種？可以構造一個母函數F(x)=(1+x+x^2+...+x^n)(1+x^2+x^4+...+x^n)...(1+x^n)，將這個母函數展開后，求出每一個x^k前面的系數Ck，就是對應的整數K有多少種拆分的形式。

（母函數：詳見電子科大出版社 - 組合數學p56、p69)

/****************************************************************************/
/*	 POJ讀書筆記9.5 —— 放蘋果1664&整數拆分問題	皮皮 2014-7-16	*/
/****************************************************************************/
#include <stdio.h>/*	整數拆分非遞歸算法(母函數方法)(不能用于m > n的放蘋果問題中)	*/
const int MAXN = 120;
int c1[MAXN+1],c2[MAXN+1];				//c2數組表示每一輪乘法后得到系數，c1數組表示到現在為止乘法得到的系數總和
static void integerDivide3(){int i,j,k,q;for(i=0;i<=MAXN;i++)c1[i]=1,c2[i]=0;for(i=2;i<=MAXN;i++){				//i表示第i - 1輪乘法x次方變化數（從2開始計算，第一個），即拆分成i的個數（母函數性質）for(j=0;j<=MAXN;j++)			//當前*左邊次方數j,為0 ~ MAXNfor(k=0;k+j<=MAXN;k+=i)		//乘上右邊的次數kc2[j+k]+=c1[j];			//次方數為j + k的系數加1for(q=0;q<=MAXN;q++)c1[q]=c2[q],c2[q]=0;}int m;scanf("%d", &m);printf("算法3	整數%d 共有 %d 種拆分方式\n", m, c1[m]);
}int main(){while(1)integerDivide3();return 0;
}

方法2：

整數的裂項與拆分、

/****************************************************************************/
/*	 POJ讀書筆記9.5 —— 放蘋果&整數拆分問題	皮皮 2014-7-16	*/
/****************************************************************************/
#include <stdio.h>/*	拆分算法,最多劃分n份，而不是剛好劃分n份	*/
static int divide(int m, int n){if( m == 0 || n == 1 )						// || m == 1 可加可不加return 1;if(m < n)		return divide(m, m);/*	m >= n時，m拆分為<=n份，則拆分情況 = 拆分了n份 + 拆分了<n份m放到n個盒子都有，則<=>m-n放到n個盒子；m放到<n個盒子，則<=>m放到n-1個盒子的情況	*/return divide(m - n, n) + divide(m, n - 1);	
}/*	整數劃分遞歸算法1(從放蘋果問題引出)		*/
static void integerDivide(){int m;scanf("%d", &m);printf("算法1	整數%d 共有 %d 種拆分方式\n", m, divide(m, m));
}int main(){while(1)integerDivide();return 0;
}

方法3：

/****************************************************************************/
/*	 POJ讀書筆記9.5 —— 放蘋果&整數拆分問題	皮皮 2014-7-16	*/
/****************************************************************************/
#include <stdio.h>/*	整數劃分	*/
static int integerDivide(int num, int max){	//需要拆分的數是num, 最大拆分出來的數是maxif(num == 0 || max == 1)				//num == 0 || max == 1時不可繼續拆分return 1;if(num <= max){							//需要拆分的數num < 最大拆分出來的數max,則只能從num大小繼續拆分numint count = 0;for(int i = num; i >= 1; i--)count += integerDivide(num - i, i);return count;}else{									//需要拆分的數num > 最大拆分出來的數max,則繼續從max大小拆分numint count = 0;for(int i = max; i >= 1; i--)count += integerDivide(num - i, i);	//注意是num - i!!!return count;}
}
/*	整數拆分遞歸算法2		*/
static void integerDivide2(){int m;scanf("%d", &m);printf("算法2	整數%d 共有 %d 種拆分方式\n", m, integerDivide(m, m));
}int main(){while(1)integerDivide2();return 0;
}

10能拆分成幾個非零整數的和。

乘積的形式

設n=i*j，dp[n]為整數n拆分成乘積形式的個數，dp[n]=∑dp[i]=∑dp[j] (i∈{i : i*j=n}，j∈{j : i*j=n})，這就是這個問題的狀態轉移方程，具有動態規劃問題的最有子結構性質。

 #include <iostream>using namespace std;const int MAXN = 200000;int dp[MAXN+1];int main(){int i,j,n;for(dp[1]=1,i=2;i<=MAXN;i++)for(j=1;i*j<=MAXN;j++)dp[i*j]+=dp[j];while(cin>>n) cout<<dp[n]<<endl;return 0;}

from:http://blog.csdn.net/pipisorry/article/details/37879761

ref:http://www.cppblog.com/mythit/archive/2009/05/06/82088.html

整數分割組合總數并打印出所有情況http://blog.csdn.net/yysdsyl/article/details/192157

算法練習之整數分割問題java實現：http://www.cnblogs.com/yjiyjige/archive/2013/04/18/3029583.html（有拆分形式輸出）

整數拆分的兩種解法（有輸出和非遞歸算法）http://blog.csdn.net/lawrencesgj/article/details/8034216