拆分数公式

无序拆分

注意：拆分与n1,n2,…nk的顺序无关。

公式1：

三：公式2：

我们将一个自然数I划分为K份，为了避免重复，习惯于从小到大地划分。我们将数I分为K份的方法数记作F（I，K），

可知：F（I，K）=F（I-K，K）+F（I-1，K-1）

初始：F（I，I）=1；F（I，0）=0；F（0，I）=0；F（I，I+K）=0。

四：拆分总数计算：‘母函数’

例题：求整数N(N <= 100)的正整数拆分方法数?

分析当N = 5的时候有几种情况: 每个拆分的单位大小可能是1,2,3,4,5 （一般情况每个拆分的单位大小可能是1,2,3,4,5……N） 考虑这么一个多项式乘积: (1+x+x^2+x^3+x^4+x^5)*(1+x^2+x^4)*(1+x^3)*(1+x^4)*(1+x^5)

其中(1+x+x^2+x^3+x^4+x^5)表示要表示正整数N,可以选取1这个加数的个数为0,1,2,3,4,5个

(1+x^2+x^4)则表示正整数N的表示过程中可以选取0个2或1个2或2个2... (1+x^3) , (1+x^4) , (1+x^5)都是同样处理

这个多项式乘积打开化简以后会有Cn*(x^n),此系数Cn则为正整数n的拆分方法.

参考程序： 分析程序:

设定数组a[ ],b[ ],c[ ] -->

a[]表示被乘数系数,b[]表示乘数的系数,c[]表示积的系数

开始可以将a[],b[]全部置为1,然后进行多项式乘法(根据高精度乘以高精度的模式去写) 求出x^n (n <= 100) 的每一个系数,然后直接输出就可以

进一步分析: 对于这题目,b[]一直为1,所以可以不用考虑此数组的存在,因为a[ii] * b[jj] = a[ii](b[]==1)

程序如下:

设定数组a[],b[],c[] --> a[]表示被乘数系数,b[]表示乘数的系数,c[]表示积的系数 开始可以将a[],b[]全部置为1,然后进行多项式乘法(根据高精度乘以高精度的模式去写) 求出x^n (n <= 100) 的每一个系数,然后直接输出就可以

进一步分析: 对于这题目,b[]一直为1,所以可以不用考虑此数组的存在,因为a[ii] * b[jj] = a[ii](b[]==1) 程序如下:

#include #include const int max = 101; int a[max],c[max],n; int main() {

int ii,j,k;

for(ii = 0 ; ii < max ; ii++) a[ii] = 1; k = 2;

while(k < max) {

j = 0;

while(j < max) {

for(ii = 0 ; ii + j < max ; ii++) c[ii+j] += a[ii]; j += k; }

memcpy(a,c,max * sizeof(int)); memset(c,0,sizeof(c)); k++; }

while(scanf(\ return 0; }