在此不深究母函数在数学中的具体原理,只知道母函数在解决问题时候的使用情况和代码实现即可。
母函数:就是把一个已知的序列和x的多项式合并起来,新产生的多项式就叫原来序列的母函数
普通母函数:
对于序列:a0,a1,a2,a3……an,母函数为:
f(x)=a0*x^0+a1*x^1+a2*x^2+a3*x^3……an^n
即:
序列{0,1,2,3,4,5,……,n}的母函数为:
f(x)=0*x^0+1*x^1+2*x^2+3*x^3+4*x^4+5*x^5+……+n*x^n
因为:0*x^0=1,那么可以写成:
f(x)=1+1*x^1+2*x^2+3*x^3+4*x^4+5*x^5+……+n*x^n ——x是无意义的数
序列{0,1,1,1,1,0,0,0,0}的母函数为:
f(x)=x^1+x^2+x^3+x^4
序列{0,1,4,8,6,9,0}的母函数为:
f(x)=1*x^1+4*x^2+8*x^3+6*x^4+9*x^5
对于母函数的使用问题,在计算以下问题可以用到:
假如x的幂次数表示几克的砝码,那么
1克的砝码表示为1+x^1
2克的砝码表示为1+x^2
3克的砝码表示为1+x^3
4克的砝码表示为1+x^4
每个砝码都可以选择取或不取,所以这里的1可以认为1*x^0,表示不取这颗砝码。
那么把这些乘起来
(1+x^1)(1+x^2)(1+x^3)(1+x^4)
=1+(x^1)+(x^2)+2(x^3)+2(x^4)+2(x^5)+2(x^6)+2(x^7)+(x^8)+(x^9)+(x^10)
根据指数来看,我们可以称出0~10这么多的重量,其中3~7的系数为2,说明有2种称的方法
那么我们来细看一遍
0:(什么砝码都不放).......................(1种)
1:1.............................................(1种)
2:2.............................................(1种)
3:3或1+2.....................................(2种)
4:4或1+3.....................................(2种)
5:1+4或2+3.................................(2种)
6:2+4或1+2+3..............................(2种)
7:3+4或1+2+4..............................(2种)
8:1+3+4......................................(1种)
9:2+3+4......................................(1种)
10:1+2+3+4.................................(1种)
系数表示数量,指数表示结果,那么2(x^4)则表示结果为4的方法共有2种。
以上为母函数的效果,那么,在具体问题的解答中,母函数应如何实现并解决问题呢?
求用1分、2分、3分的邮票贴出不同数值的方案数:(每张邮票的数量是无限的)
那么
1分:(1+x^1+x^2+x^3+x^4+......)
2分:(1+x^2+x^4+x^6+x^8+......)
3分:(1+x^3+x^6+x^9+x^12+......)
然后这3个乘起来
对于这种无限的,题目肯定会给你他询问的数值的范围,计算到最大的范围就可以了
以下上代码:
指数母函数:
对于序列a0,a1,a2,a3……an,母函数为:
由此可知,母函数和指数母函数的区别在于系数的不同。