母函数与递推关系课件

1、母函数与递推关系Project I 全排列生成算法的研究和实现 5分 选作 C/C+ or Java 11月20日前网络学堂提交 目标 Research and Novelty（非命题作文，以下内容任选） 在实现和研究4种全排列生成算法基础上进行创新 算法效率和复杂度分析 新的算法 任何相关内容的创新点 3-6页 评分标准 Paper (80%) 代码以及可执行文件 (20%)选题分析完善母函数与递推关系2内容回顾 组合的生成和组合意义模型转换一一对应 定义：对于序列定义：对于序列a0,a1,a2,构造一函数：构造一函数： G(x)=a0+a1x+a2x2+, 称函数称函数G(x)是序列是序列

2、a0,a1,a2,的母函数的母函数(生成函数生成函数 generating function)。 (1+x)n是序列是序列C(n,0),C(n,1),C(n,n)的母函数的母函数 g(x)=1+x+x2+x3+x4+.=1/(1-x)是是f(n)=1的母函数的母函数 设级数收敛，设级数收敛， -1x1生成函数的生成函数的x没有实际意义没有实际意义母函数与递推关系二项式定理12(1)1( 1)kkxxxx 2(1)(1)(1)(1)12!nkn nn nnkxnxxxk 200(1)(1)(1)(1)12!( )(1)(1)!kkknkkkxxxxkkxxRkk 000000( )!()!()!

3、()!()!()!()!()!()!()!nnnnn kkknknn kk llklnklnn kk ll mmklmaanababknknabcabcl klnknabcdabcdm lmklnk.1)1 (21xxx母函数与递推关系42.2 2.2 递推关系递推关系 利用递推关系进行计数这个方法在算法分析中经常用到 例一.Hanoi问题：N个圆盘依其半径大小，从下而上套在A柱上。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。 设计算法; 估计它的复杂性，即估计工作量.母函数

4、与递推关系52.2 2.2 递推关系递推关系算法：算法：N=2时第一步先把最上面的一个圆盘套在B上第二步把下面的一个圆盘移到C上 最后把B上的圆盘移到C上 到此转移完毕A B C母函数与递推关系62.2 2.2 递推关系递推关系 假定n-1个盘子的转移算法已经确定。 对于一般n个圆盘的问题,先把上面的n-1个圆盘经过C转移到B; 第二步把A下面一个圆盘移到C上 最后再把B上的n-1个圆盘经过A转移到C上 n=2时，算法是对的，因此，n=3是算法是对的。以此类推。A B C 母函数与递推关系72.2 2.2 递推关系递推关系令h(n)表示n个圆盘所需要的转移盘次。 对于一般n个圆盘的问题,先把上

5、面的n-1个圆盘经过C转移到B: h(n-1)次 第二步把A下面一个圆盘移到C上: 1次 最后再把B上的n-1个圆盘经过A转移到C上： h(n-1)次算法复杂度为：构造母函数为：求得了母函数，对应的序列也就求得h(n)1)-2-(2 1) 1 ( , 1) 1(2)(hnhnh,)3()2()1()(32xhxhxhxHA B C 母函数与递推关系82.2 2.2 递推关系递推关系所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。,)3()2()1()(32xhxhxhxH,)2(2) 1 (2- )(2 )32xhxhxxH_32)2(2)3( )1(2)2()1()(

6、)21(xhhxhhxhxHx1)-2-(2 1) 1 ( , 1) 1(2)(hnhnh,1)2(2)3(,1)1(2)2(,1)1( hhhhh)1/()()21( 32xxxxxxHx)1)(21()( xxxxH.1)1 (21xxx母函数与递推关系9112()ABHxxx xxBABA)2()( 如何从母函数得到序列 ？化为部分分数的算法。),2(),1 (hh 由上式可得：12BA0 BAg(x)=1+x+x2+x3+x4+. = x11. 1 , 1BA 即：11121()Hxxx )21)(1()()(1xxxxkhxHkk12)( kkh121112()()()()AxBxx

7、x 2112()()(AB) - (AB)xxx 2233212221()()xxxxx 22331 2 12121 21()()()()kkkxxxx 母函数与递推关系102.2 2.2 递推关系递推关系 或利用递推关系(2-2-1)有1)1(2)2(:2hhx1)2(2)3(:3hhx )_)1/()(2)( 2xxxxHxxH 上式左端为：xxHxhxHxhxh)()1()()3()2(32 右端第一项为：)(2x )2()1(2)2(2)1(2232xHxhxhxxhxh 右端第二项为：)1/(232xxxx1)-2-(2 1) 1 ( , 1) 1(2)(hnhnh)21)(1()(

8、xxxxH母函数与递推关系112.2 2.2 递推关系递推关系例例2. 2. 求n位十进制数中出现偶数个5的数的个数。 先从分析n位十进制数出现偶数个5的数的结构入手 设p1p2pn-1是n-1位十进制数，若含有偶数个5，则pn取5以外的0，1，2，3，4，6，7，8，9九个数中的一个，若p1p2pn-1 只有奇数个5，则pn取5，使p1p2pn-1pn 成为出现偶数个5的十进制数。解法1：令an为n位十进制数中出现偶数个5的数的个数， bn为n位十进制数中出现奇数个5的数的个数。设序列an的母函数为A(x)，序列bn的母函数为B(x)。 119nnnbaa119nnnabb母函数与递推关系1

9、22212212321)( )99)(9 )( xbxbxxBxaxaxxAxaxaaxA_8)()()91 (1axxBxAx119nnnbaa119nnnabb )9 : 9 : 9 : 33432232112baaxbaaxbaax_)()(98)(xxBxxAxA8)()()91( xxBxAx_1)()()91(xxAxBx2123212212999 ( )( )( )B xbbx bxxB xbxbxxA xax a x a1=8, b1=1母函数与递推关系132.2 2.2 递推关系递推关系故得关于母函数A(x)和B(x)得连立方程组：1)()91()(8)()()91(xBxx

10、xAxxBxAxxxxxD91 91 22)91 (xx280181xx )101)(81 (xx)101)(81(87191 18801811)(2xxxxxxxxA)101)(81 (118 91)101)(81 (1)(xxxxxxxxB0)10987(21)1019817(21)( kkkkxxxxA111029827 kkka2123 ( )A xaa x ax 母函数与递推关系142.2 2.2 递推关系递推关系解法二：解法二：n-1位的十进制数的全体共910n-1个(最高位不为0)，设所求数为an,设A(x)= a1x+a2x2+,按照尾数是否为5分类：尾数不是为5的：9an-1

11、尾数为5的，前n-1位有奇数个5：1211099nnnnaaa8 ,1098 121aaannn121109nnnab )9008 : 908 : 98 : 344233122aaxaaxaax_.)10101(9)(8)(2221xxxxxAxaxA母函数与递推关系152.2 2.2 递推关系递推关系xxxxAx10198)()81( 2111)10987(21 )1019817(21)101)(81 ()718()( kkkkxxxxxxxxxxA111029827 kkka验证：a1=8,a2=73母函数与递推关系16 1）不出现某特定元素设为a1，其组合数为 ，相当于排除a1后从a2,

12、.an 中取r个做允许重复的组合。2.2 2.2 递推关系递推关系例三：例三：从n个元素a1,a2,.an中取r个进行允许重复的组合。假定允许重复的组合数用 表示，其结果可能有以下两种情况。 ),(rnC), 1(rnC 2）至少出现一个a1，取组合数为 相当于从a1,a2,.an中取r-1个做允许重复的组合，然后再加上一个a1得从n个元素中取r个允许重复的组合。) 1,(rnC), 1() 1,(),(rnCrnCrnC母函数与递推关系172.2 2.2 递推关系递推关系), 1() 1,(),(rnCrnCrnC 因 ，故令1)1 , 1(,)1 ,(nnCnnC1)0,(nCxnCxnC

13、xGxnCxnCxxGxnCxnCnCxGnnn)1 , 1()0, 1()( )1 ,()0,( )()2,()1 ,()0,()(122_ 0)()()1(1xGxGxnnxxxxCxCCxG111 )2, 1()1 , 1()0, 1()( 221系数(1-x)不是常数。但n11 -n221x)-(11)(x)-(11 )()1(1)(11)( xGxGxxGxxGnnn母函数与递推关系18nx)-(11)( xGn 由二项式定理32! 3)2)(1(! 2) 1(1)1 (xnnnxnnnxxn 可得1111 1()()()!( , )!()! !(, )n nnrnrC n rrnr

14、C nrr 200(1)(1)(1)(1)12!()(1)(1)!kkknkkkxxxxkkxxRkk母函数与递推关系母函数与递推关系母函数 递推关系 递推运算 初始值 代数运算： 化为部分分数的算法1)-2-(2 1) 1 ( , 1) 1(2)(hnhnh,)3()2()1()(32xhxhxhxH,)2(2)1(2- )(2 )xhxhxxH_32)2(2)3( )1(2)2()1()()21(xhhxhhxhxHx)1)(21()( xxxxH22331 2 12121 21()()()()kkkxxxx 母函数与递推关系212.3 2.3 母函数的性质母函数的性质 一个序列和它的母函

15、数一一对应。给了序列便一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随得知它的母函数；反之，求得母函数序列也随之而定。之而定。 为了求满足某种递推关系的序列，可把它转换为了求满足某种递推关系的序列，可把它转换为求对应的母函数为求对应的母函数G(x)，G(x)可能满足一代数可能满足一代数方程，或代数方程组，甚至于是微分方程。方程，或代数方程组，甚至于是微分方程。 最后求逆变换，即从已求得的母函数最后求逆变换，即从已求得的母函数 G(x)得到序列得到序列 an 。关键在于要搭起从序列到母函数，从母函数到序列这两座桥。关键在于要搭起从序列到母函数，从母函数到序列这两座

16、桥。母函数与递推关系222.3 2.3 母函数的性质母函数的性质)(xA)(xB对应的母函数分别为对应的母函数分别为、kakb不特别说明不特别说明, ,下面假设下面假设、两个序列两个序列iikiikxbxBbxaxAa)()(的母函数为序列的母函数为记序列,.2 , 1, )()( )(ibaiffxBxAaii,.3 , 2 , 1 , 0 , .)()( )(2210ibacxcxccxBxAbiii则若母函数与递推关系23性质性质1：)( 000)(11011xAxxaxaxbxbxBlllllllkblk 0lkalk )()(xAxxBl若则 例例. 已知 xexxxxA!32113

17、2则xmmmmmexxxxxxB!)(321321 例例. 已知 132132xexxxxA!则）（1321121xmmmmexxxxxB!)(11111231110 00 1123:,.!:, ., ,.!ab11101231110 00123:,.!:, .,.!abmmm-1母函数与递推关系24 性质性质2：lkkab则llkkkxxaxAxB/)()( 10若llkkklllllllllllllxxaxAxxaxaxaaxAxaxaxaxxaxaaxB/ )(/ )()()( 101122102211221 1 证：证： 2210 xbxbbxB)( 例例.35( )sin3!5!xx

18、A xxx 33561111( ) sin/7!9!3!5!B xxxxxxxx 1110 1 0003571007ab:, ,.!:,.! 母函数与递推关系25 性质性质3：证：证：0kkiibaxxAxB1)()(若则 ): : : : 1 2102102210100nnaaaabnxaaabxaabxab_)1/()()1/( )1/()1/()1/()(22102210 xxAxxaxaaxxaxxaxaxB母函数与递推关系26 例例. 已知已知xxxxxAn111)(2232)1 (14321)(xxxxxB20)1 (1) 1(xxkkk 类似可得：类似可得：232323k3k 0

19、C(x)(12x3x4x) (1xxx) 13x6x10 x11 (k1)(k2)x2(1x) 0kkiibaxxAxB1)()(若则母函数与递推关系27kiiakb收敛 若 0kkaxxxAAxB1)()1()(性质性质4则 ) 00121120222011:(1):(1):(1)baaaAxbaaAaxbaAaa _)1( )1(1)1()(221202xxxaxxxaxxAxB证xxxAAxxxaaxAxB1)()1 ( )1/()(1)1 ()( 10母函数与递推关系28 A(x)=a0+a1x+a2x2+, A(x)=a1+2a2x+3a3x2+. 例例. xxxxA1112 232

20、11132xxxxxxx 则性质性质5 5kkkab xxAxB若若则则性质性质6 6kabkk1 xdxxAxxB01若若则则求导积分.)( 32210032xaxaxaxAx母函数与递推关系29性质性质7 7022110babababackkkkkkiikiba0若若 xBxAxcxccxC2210则则 证证 22100 xbxbbaxC22101xbxbbxa 221022xbxbbxa22102210 xbxbbxaxaa xBxAxC),:1000bac,:201101babac,:30211202bababac_母函数与递推关系302.32.3母函数的性质母函数的性质 例例. 已知

21、 2232111231,A xxxxxB xxxxx 31xxxC 11232,kk kCk kc 0kikiia b xBxAxC母函数与递推关系312.4 2.4 FibonacciFibonacci数列数列 Fibonacci数列是递推关系的又一个典型问题。数列是递推关系的又一个典型问题。 Fibonacci数列是以递归的方法來定义：数列是以递归的方法來定义： F0 = 0， F1 = 1 ， Fn = Fn - 1 + Fn - 2 （1） 斐波那契数列由斐波那契数列由0和和1開始，之后的斐波那契数就由開始，之后的斐波那契数就由之前的两数相加。之前的两数相加。 0, 1, 1, 2,

22、3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946， 0不是第一项，而是第不是第一项，而是第0项。项。母函数与递推关系32 1150年印度数学家研究箱子包裝物件长宽刚好年印度数学家研究箱子包裝物件长宽刚好 为为1和和2的可行方法数目时，首先描述这个数列。的可行方法数目时，首先描述这个数列。 在西方，在西方，1202年，意大利数学家斐波那契出版了他的年，意大利数学家斐波那契出版了他的算算盘全书盘全书。他在书中提出了一个关于兔子繁殖的问题：。他在书中提出了一个关于兔子繁殖的问题： 第

23、一个月有一对刚诞生的兔子；第一个月有一对刚诞生的兔子； 如果一对兔子每月能生一对小兔（一雄一雌）；如果一对兔子每月能生一对小兔（一雄一雌）； 而每对小兔在它出生后的第三个月里，又能开始生一而每对小兔在它出生后的第三个月里，又能开始生一对小兔，对小兔， 兔子永不死去；兔子永不死去； 由一对出生的小兔开始，由一对出生的小兔开始，50个月后会有多少对兔子？个月后会有多少对兔子？ 第第n个月相比个月相比n-1个月多出的兔子数是个月多出的兔子数是n-2个月的兔子生个月的兔子生出来的，即出来的，即 Fn=Fn-1+Fn-2 Leonardo of PisaSon of Bonaccio 母函数与递推关系2

24、21)(xFxFxG ): : 23441233FFFxFFFx_)()()(22xGxxxGxxxxGxxGxx)()1 ( 2 设2.4.12.4.1 递推关系递推关系xBxAxxxxxxxG25112511)2511)(2511 (1)( 2母函数与递推关系341)(250BABA520BABA51 , 51BA2.4.12.4.1 递推关系递推关系111 515151122( )G xxx 251512 ,251512)()( 22251 xx nnnnn111515F()()() ) (2)2255 618.12511nnFF母函数与递推关系35 1） 12nn 2FFFF1 (3)

25、 证明：证明：1211342231 )nnnnnnFFFFFFFFFFFF_ 122221nnnFFFFFF2.4.12.4.1 递推关系递推关系Fn=Fn-1+Fn-2母函数与递推关系36 2）1352n 12nFFFFF (4) 证明：证明：2221246524321 )nnnFFFFFFFFFFF_nnFFFFF212531 2.4.12.4.1 递推关系递推关系Fn=Fn-1+Fn-2母函数与递推关系37 3）22212nnn 1FFFF F (5) 证明：证明： )( )()(111123243243231232132221221nnnnnnnnFFFFFFFFFFFFFFFFFFF

26、FFFFFFFF_122221 nnnFFFFF2.4.12.4.1 递推关系递推关系母函数与递推关系 一位魔术师拿着一块边长为8英尺的正方形地毯，对他的地毯匠朋友说：“请您把这块地毯分成四小块，再把它们缝成一块长13英尺，宽5英尺的长方 ” 魔术881350, 1, 1, 2, 3, 5, 8, 13, 21,.35F(n)*F(n) F(n-1)F(n+1) = (-1)nn=0,1,2母函数与递推关系39斐波那契螺旋斐波那契螺旋 母函数与递推关系402.4.42.4.4在选优法上的应用在选优法上的应用 设函数 在 点取得极大值。要求用若干次试验找到 点准确到一定的程度。最简单的方法，把

27、三等分，令：)(xfx),(ba)(32 ),(3121abaxabax如下图：yx0 ab1x2x)(1xf)(2xf)(xfy 母函数与递推关系412.4.42.4.4在选优法上的应用在选优法上的应用 设函数y=f(x)在区间(a,b)上有一单峰极值点，假定为极大点。 所谓单峰极值，即只有一个极值点，而且当x与偏离越大，偏差|f(x)-f() | 也越大。如下图：yx0ab母函数与递推关系422.4.42.4.4在选优法上的应用在选优法上的应用 依据 的大小分别讨论如下：)(),(21xfxf 当 ，则极大点 必在 区间上，区间 可以舍去。)()(21xfxf),(2xa),(2bxyx0

28、)(xfy ab1x2x)()(21xfxfyx0)(1xf)(2xfa2x1x母函数与递推关系432.4.42.4.4在选优法上的应用在选优法上的应用 当 ，则极大点 必在 区间上，区间 可以舍去。)()(21xfxf),(1bx),(1xayx0)(xfy ab1x2x)()(21xfxfyx0)(1xf)(2xf2x1xb母函数与递推关系442.4.42.4.4在选优法上的应用在选优法上的应用 当 ，则极大点 必在 区间上，区间 和 均可以舍去。)()(21xfxf),(21xx),(1xa),(2bxyx0)(xfy ab1x2x)()(21xfxfyx02x1x)(1xf)(2xf母

29、函数与递推关系45 可见做两次试验，至少可把区间缩至原来区间的2/3，比如 ，进一步在 区间上找极值点。若继续用三等分法，将面对着这一实事，即其中 点的试验没发挥其作用。为此设想在 区间的两个对称点 分别做试验。)()(21xfxf),(2xa1x) 1 , 0(xlx,x0)(xfy )(1xf)(2xf0 x1x1母函数与递推关系46 设保留 区间，继续在 区间的下面两个点x2,(1-x)x 处做试验，若), 0(x), 0(x6)-3-(2 12)(xx则前一次 的点的试验，这一次可继续使用可节省一次试验。由(2-3-6)式有x1012 xx618. 0251 x02)618. 0(38

30、2. 0618. 010 x1x10.382，0.6180.236，0.3820.146，0.236母函数与递推关系472.4.42.4.4在选优法上的应用在选优法上的应用 这就是所谓的0.618优选法。即若在 区间上找单峰极大值时，可在) 1 , 0(3832. 0618, 01 ,618. 021xx 点做试验。比如保留区间 ，由于 ，故只要在 )618. 0 , 0(328. 0)618. 0(2236. 0328. 0618. 0点作一次试验。母函数与递推关系482.4.42.4.4在选优法上的应用在选优法上的应用 优选法中可利用Fibonacci数列，和0.618法不同之点在于它预先

31、确定试验次数，分两种情况介绍其方法。 (a) 所有可能试验数正好是某个Fn。102nFnF1nFl这时两个试验点放在Fn-1和Fn-2两个分点上，l如果Fn-1分点比较好，则舍去小于Fn-2的部分；l留下的部分共Fn-Fn-2 = Fn-1个分点，其中第Fn-2和第Fn-3二试验点，对应的原标号是Fn-2+Fn-2=2Fn-2以及Fn-3+Fn-2=Fn-1,恰好Fn-1点是刚才留下来的试验可以利用。l如果Fn-2点更好，则舍去大于Fn-1的部分。l在留下的部分共Fn-1个分点，下一步Fn-2和Fn-3二试验点中，恰好Fn-2是刚才留下来的试验可以利用。可见在Fn个可能试验中，最多用n-1次试验便可得到所求的极值点。母函数与递推关系492.4.42.4.4在选优法上的应用在选优法上的应用 (b)利用Fibonacci数列进行优选不同于 0.618法之点,还在于它适合于参数只能取整数数值的情况.如若可能试验的数目比 小,但比 大时,可以虚加几个点凑成 个点，但新增加的点的试验不必真做，可认定比其他点都差的点来处理。nF1nFnF母函数与递推关系502.4.42.4.4在选优法上的应用在选优法上的应用 定理：定理：测试n次可将包含