整数分拆--中文百科全书

原理

整数分拆问题是一个古老而又十分有趣的问题。所谓整数的分拆，指将一个正整数表示为若干个正整数的和。

分类

根据是否考虑分拆部分之间的排列顺序，我们可以将整数分拆问题分为有序分拆（composition）和无序分拆（partition）。两者之间的区别如下：

在有序分拆中，考虑分拆部分求和之间的顺序。假定

，

之间不同的排序记为不同的方案，称之为n的有序k拆分，如3的有序2拆分为：3=1+2=2+1。我们可以将这个问题建模为排列组合中的“隔板”问题，即n个无区别的球分为r份且每份至少有一个球，则需要用r-1个隔板插入到球之间的n-1个空隙，因此总共的方案数为C(n-1,r-1)。

在无序拆分中，不考虑其求和的顺序。一般假定

，

，我们称之为n的无序k拆分，如3的无序k拆分为：3=1+2。这种拆分可以理解为将n个无区别的球分为r份且每份至少有一个球。

一般情况下，无序拆分的个数用 p(n) 表示，则 p(2)=1，p(3)=2，p(4)=4。

在通常情况下，整数分拆是指整数的无序分拆。

例子

例1 有1克、2克、3克、4克的砝码各一枚，问能称出多少重量，并各有几种称法。

该问题可以看成n拆分成1,2,3,4之和且不允许重複的拆分数，利用母函式计算如下：

表示称出4克有2种方案，是1+3和2+2，以此类推，超出10克便无法称出。

例2 将14分拆成两个自然数的和，并使这两个自然数的积最大，应该如何分拆？分析与解不考虑加数顺序，将14分拆成两个自然数的和，有1+13，2+12，3+11，4+10，5+9，6+8，7+7共七种方法。经计算，容易得知，将14分拆成7+ 7时，有最大积7×7=49。

例3 将15分拆成两个自然数的和，并使这两个自然数的积最大，如何分拆？

分析与解不考虑加数顺序，可将15分拆成下列形式的两个自然数的和：1+14，2+13，3+12，4+11，5+10，6+9，7+8。显见，将15分拆成7+8时，有最大积7×8=56。

注：从上述两例可见，将一个自然数分拆成两个自然数的和时，如果这个自然数是偶数2m，当分拆成m+m时，有最大积m×m=m2；如果这个自然数是奇数2m+1，当分拆成m+（m+1）时，有最大积m×（m+1）。

例4 将14分拆成3个自然数的和，并使这三个自然数的积最大，如何分拆？

分析与解显然，只有使分拆成的数之间的差儘可能地小（比如是0或1），这样得到的积才最大。这样不难想到将14分拆成4+5+5时，有最大积4×5×5=100。

拆分数估计

历史上，有很多关于整数拆分的研究，其中包括英国剑桥大学的G.E哈代和印度学者拉马努金，拉马努拉和哈代通过自己的研究，找到了一个相关的渐进的公式，描述如下。

正整数n拆分成若干个正整数之和，其不同的拆分数用p(n)表示，{p(n)}的母函式为：

则拆分数估计可以表示为：

拆分数估计定理证明

令

根据马克罗林级数：

所以：

而

又由于

所以

故

所以

但

所以

设

有

曲线 y = lnx 是向上凸的，所以曲线 y = lnx 在（1,0）的切线为 y = x-1 ，即有

所以

对于

求极小值：

令其一阶导

，方程的解为

又因为y的二阶导

，所以y的极小值为

所以

拆分数性质

性质一

整数n拆分成最大数为k的拆分数，和数n拆分成k个数的和的拆分数相等。

性质二

整数n拆分成最多不超过m个数的和的拆分数，和n拆分成最大不超过m的拆分数相等。

性质三

整数n拆分成互不相同的若干奇数的和的拆分数,和n拆分成自共轭的Ferrers图像的拆分数相等。

拆分数计算方法

整数拆分可以利用渐进公式计算，随着N的无限大，整数拆分估算值接近实际值，现代还可以利用计算机的方法进行求解。在这里，主要介绍4中计算方法。

递推法

根据n和m的关係，考虑下面几种情况：

（1）当n=1时，不论m的值为多少（m>0），只有一种划分，即{1}；

（2）当m=1时，不论

的值为多少（n>0），只有一种划分，即{1,1,....1,1,1}；

（3）当n=m时，根据划分中是否包含n，可以分为两种情况：

（a）划分中包含n的情况，只有一个，即{n}；

（b）划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有（n-1）划分；

因此，f(n,n) = 1 + f(n, n - 1)。

（4）当n

（5）当n>m时，根据划分中是否包含m，可以分为两种情况：

（a）划分中包含

的情况，即{m,{x1,x2,x3,...,xi}}，其中{x1,x2,x3,...,xi}的和为n-m，可能再次出现m，因此是（n-m）的m划分，因此这种划分个数为f(n-m,m；

（b）划分中不包含m的情况，则划分中所有值都比m小，即n的（m-1）划分，个数为f(n,m-1；

因此，f(n,m)=f(n-m,m)+f(n,m-1) 。

综合以上各种情况，可以看出，上面的结论具有递归定义的特徵，其中（1）和（2）属于回归条件，（3）和（4）属于特殊情况，而情况（5）为通用情况，属于递归的方法，其本质主要是通过减少n或m以达到回归条件，从而解决问题。

详细递推公式描述如下：

参考源码

#include#defineMYDATAlonglongconstMYDATAMOD=1000000007;#defineMAXNUM100005//最高次数//递归法求解整数划分unsignedlongGetPartitionCount(intn,intmax){if(n==1||max==1)return1;if(n
这个版本的时间複杂度较高，运行效率很低。
动态规划法
考虑到在上一节使用递归中，很多的子递归重複计算。如在计算 f (10,9)时，划分成为 f (1,9) + f (10,8)，进一步划分为 f (1,1)=f (2,8)+f (10,7)，接下来转换为f (1,1) +f (2,2)+ f (3,7)+ f (10,6) =3* f (1,1) +1+ f (3,7)+ f (10,6)，这样就产生了重複，然而，在递归的时候，每个都需要被计算一遍，因此可见，位于底层的状态，计算的次数也越来越多。这样在时间开销特别大，是造成运算慢的根本原因，比如算120的时候需要3秒中，计算130的时候需要27秒钟，在计算机200的时候....计算10分钟还没计算出来。
鑒于此，我们已经分析出了普通递推关係中存在大量的冗余造成了重複计算，最终导致了运行时间太长，一种自然地想法是能够用一种技巧，以避免重複计算？这里我们使用动态规划的思想进行程式设计。
在上一节中，已经分析了状态转移的方程，因此，我们在求解子问题时，利用标记的思想，首先检查产生的子问题是否在之前被计算过，这是因为对于相同的子问题，得到的结果肯定是一样的，因此利用这一步去掉冗余的操作，极大减少了计算的时间开销。对于没有标记的子问题来说，一定是没有被计算过，这样，在计算完成后，顺便标记一下子问题，以确保以后不用再重複计算。利用这个特性，可以确保所有的划分子问题都无重複，无遗漏的恰巧被计算一次。 
动态规划版主要是利用了标记思想进行加速。
参考源码如下：
#include#defineMYDATAlonglongconstMYDATAMOD=1000000007;#defineMAXNUM1005//最高次数unsignedlongww[MAXNUM*11][MAXNUM*11];unsignedlongdynamic_GetPartitionCount(intn,intmax);usingnamespacestd;intmain(intargc,char**argv){intn;intm;unsignedlongcount;while(1){cin>>n;cout<
这样的算法效率快了很多。
生成函式法
对于整数拆分问题，也可以从另一个角度，即“母函式”的角度来考虑这个问题。所谓母函式，即为关于x的一个多项式
 ，满足：
 则我们称为序列
 的母函式。我们从整数划分考虑，假设的某个划分中，1的出现个数记为
 ，2的个数记为
 ，…，
 的个数
 记为显然有：
因此
 的划分数，也就是从1到
 这
 个数字的组合，每个数字理论上可以无限重複出现，即个数随意，使它们的和为
 。显然，数字
 可以有如下可能，出现0次（即不出现），1次，2次，…，
 次等等。把数字用
 表示，出现
 次的数字用
 表示，不出现用1表示。例如，数字2用
 表示，2个2用
 表示，3个2用
 表示，k个2用
 表示。则对于从1到
 的所有可能组合结果我们可以表示为：
 上面的表达式中，每个括弧内的多项式代表了数字的参与到划分中的所有可能情况。因此，该多项式展开后，由于
 ，因此
 就代表了
 的划分，展开后项的係数也就是的所有划分个数，即
 。由此我们找到了关于整数划分的母函式
 ，剩下的问题就是，我们需要求出
 的展开后的所有係数。为此，我们首先要做多项式乘法，对于计算机编程来说，并不困难。我们把一个关于
 的多项式用一个整数数组
 表示，
 代表 的係数，然后卷积即可。 
参考源码：
#include#include#includeusingnamespacestd;#defineMYDATAlonglongconstMYDATAMOD=1000000007;constintN=100005;intc1[N],c2[N];intmain(intargc,char**argv){intn,i,j,k;while(cin>>n){if(n==0)break;for(i=0;i<=n;i++){c1[i]=1;c2[i]=0;}for(i=2;i<=n;i++){for(j=0;j<=n;j++)for(k=0;k+j<=n;k+=i)c2[k+j]=(c2[k+j]+c1[j])%MOD;for(j=0;j<=n;j++){c1[j]=c2[j];c2[j]=0;}}cout<
这样基于生成函式的方法实际上快了很多。
五边形数法
设第n个五边形数为
 ，那么
 ，即序列为：1, 5, 12, 22, 35, 51, 70, ...对应图形如下：
设五边形数的生成函式为，那么有：
以上是五边形数的情况。下面是关于五边形数定理的内容：
五边形数定理是一个由欧拉发现的数学定理，描述欧拉函式展开式的特性。欧拉函式的展开式如下：
即：
可见，欧拉函式展开后，有些次方项被消去，只留下次方项为1, 2, 5, 7, 12, ...的项次，留下来的次方恰为广义五边形数。
五边形数和分割函式的关係：欧拉函式的倒数是分割函式的母函式，亦即：
其中
 为
 的分割函式。上式配合五边形数定理，有：
在
 时，等式右侧的係数均为0，比较等式二侧的係数，可得
因此可得到分割函式的递归式：
所以，通过上面递归式，我们可以很快速地计算的整数划分方案数了。
参考代码：
#includeusingnamespacestd;#defineMYDATAlonglongconstMYDATAMOD=1000000007;#defineAMS100005MYDATApp[AMS];MYDATAasist[2*AMS];voidmyinit(){for(inti=0;i>n;cout< 
以上设计的代码是最高效的。
通过比较上述四种算法，可见整数拆分的划分方法比较多样，且不同的算法运行效率差距比较大，需要仔细理解和思考。