整数拆分有关问题详解
整数拆分问题详解
4=1+3 12=2*6
4=2+2 12=3*4
4=1+1+2 12=2*2*3
方法2：
方法3：
http://blog.****.net/pipisorry/article/details/37879761
问题：
给定一个整数n，要找出n能拆分成多少种不同的若干个数的和与乘积的形式。比如：
4=4 12=1*124=1+3 12=2*6
4=2+2 12=3*4
4=1+1+2 12=2*2*3
4=1+1+1+1
加法形式：
方法1：
可以构造一个母函数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 ~ MAXN
for(k=0;k+j<=MAXN;k+=i) //乘上右边的次数k
c2[j+k]+=c1[j]; //次方数为j + k的系数加1
for(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, 最大拆分出来的数是max
if(num == 0 || max == 1) //num == 0 || max == 1时不可继续拆分
return 1;
if(num <= max){ //需要拆分的数num < 最大拆分出来的数max,则只能从num大小继续拆分num
int count = 0;
for(int i = num; i >= 1; i--)
count += integerDivide(num - i, i);
return count;
}else{ //需要拆分的数num > 最大拆分出来的数max,则继续从max大小拆分num
int 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;
}
乘积的形式
设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.****.net/pipisorry/article/details/37879761
ref:http://www.cppblog.com/mythit/archive/2009/05/06/82088.html
整数分割组合总数并打印出所有情况http://blog.****.net/yysdsyl/article/details/192157
算法练习之整数分割问题java实现：http://www.cnblogs.com/yjiyjige/archive/2013/04/18/3029583.html（有拆分形式输出）
整数拆分的两种解法（有输出和非递归算法）http://blog.****.net/lawrencesgj/article/details/8034216