数学奥林匹克专题讲座第4讲：整数的分拆 标签：广州奥数题
<p><p> 整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都涉及到。 </p> <p> 所谓整数划分，是指把一个正整数n写成如下形式： </p> <p> n=m1+m2+m3+....+mi;(其中mi为正整数，并且1=n)，则{m1,m2,m3,....,mi}为n的一个划分。 </p> <p> 如果{m1,m2,m3,....,mi}中的最大值不超过m，即max{m1,m2,m3,....,mi} = m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m); </p> <p> 例如当n=4时，它有5个划分：{4}、{3,1}、{2,2}、{2,1,1}、{1,1,1,1}; </p> <p> 注意：4=1+3和4=3+1被认为是同一个划分。 </p> <p> 该问题是求出n的所有划分个数，即f(n,n)。下面我们考虑求f(n,m)的方法。 </p> <p> (一)方法一——递归法 </p> <p> 根据n和m的关系，考虑下面几种情况： </p> <p> (1)当n=1时，不论m的值为多少(m0)，只有一种划分，即{1}; </p> <p> (2)当m=1时，不论n的值为多少(n0)，只有一种划分，即{1,1,....1,1,1}; </p> <p> (3)当n=m时，根据划分中是否包含n，可以分为两种情况： </p> <p> (a)划分中包含n的情况，只有一个，即{n}; </p> <p> (b)划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分; </p> <p> 因此，f(n,n) = 1 + f(n, n - 1)。 </p> <p> (4)当n </p> <p> (5)当nm时，根据划分中是否包含m，可以分为两种情况： </p> <p> (a)划分中包含m的情况，即{m,{x1,x2,x3,...,xi}}，其中{x1,x2,x3,...,xi}的和为n-m，可能再次出现m，因此是(n-m)的m划分，因此这种划分个数为f(n-m, m); </p> <p> (b)划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为f(n, m - 1); </p> <p> 因此，f(n,m) = f(n - m,m) + f(n, m - 1)。 </p> <p> 综合以上各种情况，可以看出，上面的结论具有递归定义的特征，其中(1)和(2)属于回归条件，(3)和(4)属于特殊情况，而情况(5)为通用情况，属于递归的方法，其本质主要是通过减少n或m以达到回归条件，从而解决问题。 </p> <p> 其递归表达式如下所示。 </p><p> (二)方法二——母函数 </p> <p> 下面我们从另一个角度，即“母函数”的角度来考虑这个问题。 </p> <p> 所谓母函数，即为关于x的一个多项式G(x)： </p> <p> 有G(x) = a0 + a1*x + a2*x^2 + a3*x^3 + ...... </p> <p> 则我们称G(x)为序列(a0, a1, a2,.....)的母函数。关于母函数的思路我们不做更过分析。 </p> <p> 我们从整数划分考虑，假设n的某个划分中，1的出现个数记为a1，2的个数记为a2，.....，i的个数记为ai， </p> <p> 显然有：ak = n/k(0=n) </p> <p> 因此n的划分数f(n,n)，也就是从1到n这n个数字抽取这样的组合，每个数字理论上可以无限重复出现，即个数随意，使它们的综合为n。显然，数字i可以有如下可能，出现0次(即不出现)，1次，2次，......，k次等等。把数字i用(x^i)表示，出现k次的数字i用(x^(i*k))表示，不出现用1表示。 </p> <p> 例如，数字2用x^2表示，2个2用x^4表示，3个2用x^6表示，k个2用x^2k表示。 </p> <p> 则对于从1到N的所有可能组合结果我们可以表示为： </p> <p> G(x) = ( 1 + x + x^2 + x^3 + ... + x^n)*(1 + x^2 + x^4 + x^6 + ....)....(1 + x^n) </p> <p> = g(x,1)*g(x,2)*g(x,3)*....*g(x,n) </p> <p> = a0 + a1*x + a2*x^2 +...+ an*x^n + ....//展开式 </p> <p> 上面的表达式中，每个括号内的多项式代表了数字i的参与到划分中的所有可能情况。因此，该多项式展开后，由于x^a *x^b = x^(a+b)，因此x^i就代表了i的划分，展开后(x^i)项的系数也就是i的所有划分个数，即f(n,n) = an。 </p> <p> 由此我们找到了关于整数划分的母函数G(x);剩下的问题就是，我们需要求出G(x)的展开后的所有系数。 </p> <p> 为此，我们首先要做多项式乘法，对于我们来说，并不困难。我们把一个关于x的多项式用一个整数数组a[]表示，a代表x^i的系数，即： </p> <p> g(x) = a + ax + ax^2 + ... + ax^n; </p> <p> 则关于多项式乘法的代码如下，其中数组a和数组b表示两个要相乘的多项式，结果存储到数组c中。 </p></p>
页:
[1]