母函数与递推关系ppt课件

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)是序列a0,a1,a2,的母函数(生成函数 generating funct

2、ion)。 (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( )!()!()!()!()!()!()!()!()!()!nnnnn kkknknn kk llklnklnn kk ll mmklmaanababknknabcabcl kl

3、nknabcdabcdm lmklnk.1)1 (21xxx42.2 2.2 递推关系递推关系 利用递推关系进展计数这个方法在算法分析中经常用到 例一.Hanoi问题：N个圆盘依其半径大小，从下而上套在A柱上。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。假设要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要挪动几个盘次。如今只需A、B、C三根柱子可用。设计算法;估计它的复杂性，即估计任务量.52.2 2.2 递推关系递推关系算法：算法：N=2时第一步先把最上面的一个圆盘套在B上第二步把下面的一个圆盘移到C上 最后把B上的圆盘移到C上 到此转移终了A B C62.2 2.2

4、 递推关系递推关系 假定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个圆盘的问题,先把上面的n-1个圆盘经过C转移到B: h(n-1)次第二步把A下面一个圆盘移到C上: 1次最后再把B上的n-1个圆盘经过A转移到C上： h(n-1)次算法复杂度为：构造母函数为：求得了母函数，对应的序列也就求得h(n)1)-2-(2

5、 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()()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 (21xxx91

6、12()ABHxxx xxBABA)2()( 如何从母函数得到序列 ？化为部分分数的算法。),2(),1 (hh 由上式可得：12BA0 BAg(x)=1+x+x2+x3+x4+. = x11. 1 , 1BA 即：11121()Hxxx )21)(1()()(1xxxxkhxHkk12)( kkh121112()()()()AxBxxx 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

7、(: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()(xxxxH112.2 2.2 递推关系递推关系例例2. 2. 求求n n位十进制数中出现偶数个位十进制数中出现偶数个5 5的数的个数。的数的个数。 先从分析n位十进制数出现偶数个5的数的构造入手 设p1p2pn-1是n-1位十进制数，假设含有偶数个5，那么pn取5以外的0，1

8、，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)。 119nnnbaa119nnnabb122212212321)( )99)(9 )( xbxbxxBxaxaxxAxaxaaxA_8)()()91 (1axxBxAx119nnnbaa119nnnabb )9 : 9 : 9 : 33432232112baaxbaaxbaax_)()(98)(

9、xxBxxAxA8)()()91( xxBxAx_1)()()91(xxAxBx2123212212999 ( )( )( )B xbbx bxxB xbxbxxA xax a x a1=8, b1=1132.2 2.2 递推关系递推关系故得关于母函数A(x)和B(x)得连立方程组：1)()91()(8)()()91(xBxxxAxxBxAxxxxxD91 91 22)91 (xx280181xx)101)(81 (xx)101)(81(87191 18801811)(2xxxxxxxxA)101)(81 (118 91)101)(81 (1)(xxxxxxxxB0)10987(21)1019

10、817(21)( kkkkxxxxA111029827 kkka2123 ( )A xaa x a x 142.2 2.2 递推关系递推关系解法二：解法二：n-1n-1位的十进制数的全体共位的十进制数的全体共9 910n-110n-1个个( (最高位不为最高位不为0)0)，设所求数为设所求数为an,an,设设A(x)= a1x+a2x2+,A(x)= a1x+a2x2+,按照尾数能否为按照尾数能否为5 5分类分类：尾数不是为尾数不是为5 5的：的：9an-19an-1尾数为尾数为5 5的，前的，前n-1n-1位有奇数个位有奇数个5 5：1211099nnnnaaa8 ,1098 121aaan

11、nn121109nnnab )9008 : 908 : 98 : 344233122aaxaaxaax_.)10101(9)(8)(2221xxxxxAxaxA152.2 2.2 递推关系递推关系xxxxAx10198)()81( 2111)10987(21 )1019817(21)101)(81 ()718()( kkkkxxxxxxxxxxA111029827 kkka验证：a1=8,a2=7316 1不出现某特定元素设为a1，其组合数为 ，相当于排除a1后从a2,.an 中取r个做允许反复的组合。2.2 2.2 递推关系递推关系例三：从例三：从n个元素个元素a1,a2,.an中取中取r个

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

13、 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)( xGxGxxGxxGnnn18nx)-(11)( xGn 由二项式定理32! 3)2)(1(! 2) 1(1)1 (xnnnxnnnxxn 可得1111 1()()()!( , )!()! !(, )n nnrnrC n rrnrC nrr 200(1)(1)(1)(1)12!()(1)(1)!kkk

14、nkkkxxxxkkxxRkk母函数 递推关系 递推运算 初始值 代数运算： 化为部分分数的算法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 2.3 2.3 母函数的性质母函数的性质 一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。 为了求满足某种递推关系的序列，可把它转换为求对应的母

15、函数G(x)，G(x)能够满足一代数方程，或代数方程组，甚至于是微分方程。 最后求逆变换，即从已求得的母函数 G(x)得到序列an。关键在于要搭起从序列到母函数，从母函数到序列这两座桥。212.3 2.3 母函数的性质母函数的性质)(xA)(xB对应的母函数分别为对应的母函数分别为、kakb不特别阐明不特别阐明, ,下面假设下面假设、两个序列两个序列iikiikxbxBbxaxAa)()(的母函数为序列的母函数为记序列,.2 , 1, )()( )(ibaiffxBxAaii,.3 , 2 , 1 , 0 , .)()( )(2210ibacxcxccxBxAbiii则若22性质性质1：)(

16、000)(11011xAxxaxaxbxbxBlllllllkblk 0lkalk )()(xAxxBl假设那么 例. 知 xexxxxA!321132那么xmmmmmexxxxxxB!)(32132123 例. 知 132132xexxxxA!那么）（1321121xmmmmexxxxxB!)(11111231110 00 1123:,.!:, ., ,.!ab11101231110 00123:,.!:, .,.!abmmm-1 性质2：lkkab那么llkkkxxaxAxB/)()( 10假设llkkklllllllllllllxxaxAxxaxaxaaxAxaxaxaxxaxaaxB/

17、 )(/ )()()( 101122102211221 1 证：证： 2210 xbxbbxB)( 例例.35( )sin3!5!xxA xxx 33561111( ) sin/7!9!3!5!B xxxxxxxx 241110 1 0003571007ab:, ,.!:,.! 性质3：证：证：0kkiibaxxAxB1)()(假设那么 ): : : : 1 2102102210100nnaaaabnxaaabxaabxab_)1/()()1/( )1/()1/()1/()(22102210 xxAxxaxaaxxaxxaxaxB25 例. 知xxxxxAn111)(2232)1 (14321

18、)(xxxxxB20)1 (1) 1(xxkkk 类似可得：232323k3k 0C(x)(12x3x4x) (1xxx) 13x6x10 x11 (k1)(k2)x2(1x) 0kkiibaxxAxB1)()(假设那么26kiiakb收敛 若 0kkaxxxAAxB1)()1()(性质性质4那么 ) 00121120222011:(1):(1):(1)baaaAxbaaAaxbaAaa _)1( )1(1)1()(221202xxxaxxxaxxAxB证xxxAAxxxaaxAxB1)()1 ( )1/()(1)1 ()( 1027 A(x)=a0+a1x+a2x2+, A(x)=a1+2a

19、2x+3a3x2+. 例例. xxxxA1112 23211132xxxxxxx 那么性质性质5 5kkkab xxAxB假设假设那么那么性质性质6 6kabkk1 xdxxAxxB01假设假设那么那么求导积分.)( 32210032xaxaxaxAx28性质性质7 7022110babababackkkkkkiikiba0假设假设 xBxAxcxccxC2210那么那么 证证 22100 xbxbbaxC22101xbxbbxa 221022xbxbbxa22102210 xbxbbxaxaa xBxAxC),:1000bac,:201101babac,:30211202bababac_29

20、2.32.3母函数的性质母函数的性质 例. 知 2232111231,A xxxxxB xxxxx 31xxxC30 11232,kk kCk kc 0kikiia b xBxAxC2.4 Fibonacci2.4 Fibonacci数列数列 Fibonacci数列是递推关系的又一个典型问题。Fibonacci数列是以递归的方法來定义：F0 = 0， F1 = 1 ， Fn = Fn - 1 + Fn - 2 1斐波那契数列由0和1開始，之后的斐波那契数就由之前的两数相加。0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,

21、987, 1597, 2584, 4181, 6765, 10946，0不是第一项，而是第0项。31 1150年印度数学家研讨箱子包裝物件长宽刚好年印度数学家研讨箱子包裝物件长宽刚好 为为1和和2的可行方法数目时，首先描画这个数列。的可行方法数目时，首先描画这个数列。 在西方，在西方，1202年，意大利数学家斐波那契出版了他的年，意大利数学家斐波那契出版了他的。他在书中提出了一个关于兔子繁衍的问题：。他在书中提出了一个关于兔子繁衍的问题： 第一个月有一对刚诞生的兔子；第一个月有一对刚诞生的兔子； 假设一对兔子每月能生一对小兔一雄一雌；假设一对兔子每月能生一对小兔一雄一雌； 而每对小兔在它出生后

22、的第三个月里，又能开场生一对小而每对小兔在它出生后的第三个月里，又能开场生一对小兔，兔， 兔子永不死去；兔子永不死去； 由一对出生的小兔开场，由一对出生的小兔开场，50个月后会有多少对兔子？个月后会有多少对兔子？ 第第n个月相比个月相比n-1个月多出的兔子数是个月多出的兔子数是n-2个月的兔子生出个月的兔子生出来的，即来的，即 Fn=Fn-1+Fn-2 32Leonardo of PisaSon of Bonaccio 221)(xFxFxG ): : 23441233FFFxFFFx_)()()(22xGxxxGxxxxGxxGxx)()1 ( 2 设2.4.12.4.1递推关系递推关系xB

23、xAxxxxxxxG25112511)2511)(2511 (1)( 21)(250BABA520BABA51 , 51BA2.4.12.4.1递推关系递推关系111 515151122( )G xxx 251512 ,251512)()( 22251 xx nnnnn111515F()()() ) (2)2255 618.12511nnFF34 1 12nn 2FFFF1 (3) 证明：证明：1211342231 )nnnnnnFFFFFFFFFFFF_ 122221nnnFFFFFF2.4.12.4.1递推关系递推关系Fn=Fn-1+Fn-235 21352n 12nFFFFF (4) 证

24、明：证明：2221246524321 )nnnFFFFFFFFFFF_nnFFFFF212531 2.4.12.4.1递推关系递推关系Fn=Fn-1+Fn-236 322212nnn 1FFFF F (5) 证明：证明： )( )()(111123243243231232132221221nnnnnnnnFFFFFFFFFFFFFFFFFFFFFFFFFFF_122221 nnnFFFFF2.4.12.4.1递推关系递推关系37 一位魔术师拿着一块边长为8英尺的正方形地毯，对他的地毯匠朋友说：“请您把这块地毯分成四小块，再把它们缝成一块长13英尺，宽5英尺的长方 魔术881350, 1, 1,

25、 2, 3, 5, 8, 13, 21,.35F(n)*F(n) F(n-1)F(n+1) = (-1)nn=0,1,2斐波那契螺旋斐波那契螺旋 392.4.42.4.4在选优法上的运用在选优法上的运用 设函数 在 点获得极大值。要求用假设干次实验找到 点准确到一定的程度。最简单的方法，把 三等分，令：)(xfx),(ba)(32 ),(3121abaxabax如以下图：yx0 ab1x2x)(1xf)(2xf)(xfy 402.4.42.4.4在选优法上的运用在选优法上的运用 设函数y=f(x)在区间(a,b)上有一单峰极值点，假定为极大点。 所谓单峰极值，即只需一个极值点，而且当x与偏离越

26、大，偏向|f(x)-f() | 也越大。如以下图：yx0ab412.4.42.4.4在选优法上的运用在选优法上的运用 根据 的大小分别讨论如下：)(),(21xfxf 当 ，那么极大点 必在 区间上，区间 可以舍去。)()(21xfxf),(2xa),(2bxyx0)(xfy ab1x2x)()(21xfxfyx0)(1xf)(2xfa2x1x422.4.42.4.4在选优法上的运用在选优法上的运用 当 ，那么极大点 必在 区间上，区间 可以舍去。)()(21xfxf),(1bx),(1xayx0)(xfy ab1x2x)()(21xfxfyx0)(1xf)(2xf2x1xb432.4.42.

27、4.4在选优法上的运用在选优法上的运用 当 ，那么极大点 必在 区间上，区间 和 均可以舍去。)()(21xfxf),(21xx),(1xa),(2bxyx0)(xfy ab1x2x)()(21xfxfyx02x1x)(1xf)(2xf44 可见做两次实验，至少可把区间缩至原来区间的2/3，比如 ，进一步在 区间上找极值点。假设继续用三等分法，将面对着这一实事，即其中 点的实验没发扬其作用。为此想象在 区间的两个对称点 分别做实验。)()(21xfxf),(2xa1x) 1 , 0(xlx,x0)(xfy )(1xf)(2xf0 x1x145 设保管 区间，继续在 区间的下面两个点x2,(1-

28、x)x 处做实验，假设), 0(x), 0(x6)-3-(2 12)(xx那么前一次 的点的实验，这一次可继续运用可节省一次实验。由(2-3-6)式有x1012 xx618. 0251 x02)618. 0(382. 0618. 010 x1x10.382，0.6180.236，0.3820.146，0.236462.4.42.4.4在选优法上的运用在选优法上的运用 这就是所谓的0.618优选法。即假设在 区间上找单峰极大值时，可在) 1 , 0(3832. 0618, 01 ,618. 021xx 点做实验。比如保管区间 ，由于 ，故只需在 )618. 0 , 0(328. 0)618. 0

29、(2236. 0328. 0618. 0点作一次实验。472.4.42.4.4在选优法上的运用在选优法上的运用 优选法中可利用Fibonacci数列，和0.618法不同之点在于它预先确定实验次数，分两种情况引见其方法。 (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-

30、2点更好，那么舍去大于Fn-1的部分。l在留下的部分共Fn-1个分点，下一步Fn-2和Fn-3二实验点中，恰好Fn-2是刚刚留下来的实验可以利用。l可见在Fn个能够实验中，最多用n-1次实验便可得到所求的极值点。482.4.42.4.4在选优法上的运用在选优法上的运用 (b)利用Fibonacci数列进展优选不同于 0.618法之点,还在于它适宜于参数只能取整数数值的情况.如假设能够实验的数目比 小,但比 大时,可以虚加几个点凑成 个点，但新添加的点的实验不用真做，可认定比其他点都差的点来处置。nF1nFnF492.4.42.4.4在选优法上的运用在选优法上的运用 定理：测试定理：测试n次可将包含单峰极值点的区间次可将包含单峰极值点的区间减少到原区间的减少到原区间的 ，其中，其中 是恣意小的是恣意小的正整数，正整数