母函数与递推关系

1、母函数与递推关系第1页，共53页，2022年，5月20日，7点11分，星期四2内容回顾组合的生成和组合意义模型转换一一对应定义：对于序列a0,a1,a2,构造一函数：G(x)=a0+a1x+a2x2+,称函数G(x)是序列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没有实际意义第2页，共53页，2022年，5月20日，7点11分，星期四二项式定理第3页，共53页，2022年，5月20日

2、，7点11分，星期四42.2 递推关系 利用递推关系进行计数这个方法在算法分析中经常用到 例一.Hanoi问题：N个圆盘依其半径大小，从下而上套在A柱上。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。设计算法;估计它的复杂性，即估计工作量.第4页，共53页，2022年，5月20日，7点11分，星期四52.2 递推关系算法：N=2时第一步先把最上面的一个圆盘套在B上第二步把下面的一个圆盘移到C上 最后把B上的圆盘移到C上 到此转移完毕A B C第5页，共53页，2022年，5月2

3、0日，7点11分，星期四62.2 递推关系 假定n-1个盘子的转移算法已经确定。对于一般n个圆盘的问题,先把上面的n-1个圆盘经过C转移到B;第二步把A下面一个圆盘移到C上最后再把B上的n-1个圆盘经过A转移到C上n=2时，算法是对的，因此，n=3是算法是对的。以此类推。A B C第6页，共53页，2022年，5月20日，7点11分，星期四72.2 递推关系令h(n)表示n个圆盘所需要的转移盘次。对于一般n个圆盘的问题,先把上面的n-1个圆盘经过C转移到B: h(n-1)次第二步把A下面一个圆盘移到C上: 1次最后再把B上的n-1个圆盘经过A转移到C上： h(n-1)次算法复杂度为：构造母函数

4、为：求得了母函数，对应的序列也就求得h(n)A B C第7页，共53页，2022年，5月20日，7点11分，星期四82.2 递推关系所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。第8页，共53页，2022年，5月20日，7点11分，星期四9如何从母函数得到序列 ？化为部分分数的算法。 由上式可得：g(x)=1+x+x2+x3+x4+. = 即：第9页，共53页，2022年，5月20日，7点11分，星期四102.2 递推关系 或利用递推关系(2-2-1)有 上式左端为： 右端第一项为： 右端第二项为：第10页，共53页，2022年，5月20日，7点11分，星期四112.

5、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)。 第11页，共53页，2022年，5月20日，7点11分，星期四12a1=8, b1=1第12页，共53页，202

6、2年，5月20日，7点11分，星期四132.2 递推关系故得关于母函数A(x)和B(x)得连立方程组：第13页，共53页，2022年，5月20日，7点11分，星期四142.2 递推关系解法二：n-1位的十进制数的全体共910n-1个(最高位不为0)，设所求数为an,设A(x)= a1x+a2x2+,按照尾数是否为5分类：尾数不是为5的：9an-1尾数为5的，前n-1位有奇数个5：第14页，共53页，2022年，5月20日，7点11分，星期四152.2 递推关系验证：a1=8,a2=73第15页，共53页，2022年，5月20日，7点11分，星期四16 1）不出现某特定元素设为a1，其组合数为

7、，相当于排除a1后从a2,.an 中取r个做允许重复的组合。2.2 递推关系例三：从n个元素a1,a2,.an中取r个进行允许重复的组合。假定允许重复的组合数用 表示，其结果可能有以下两种情况。 2）至少出现一个a1，取组合数为 相当于从a1,a2,.an中取r-1个做允许重复的组合，然后再加上一个a1得从n个元素中取r个允许重复的组合。第16页，共53页，2022年，5月20日，7点11分，星期四172.2 递推关系 因 ，故令系数(1-x)不是常数。但第17页，共53页，2022年，5月20日，7点11分，星期四18 由二项式定理 可得第18页，共53页，2022年，5月20日，7点11分

8、，星期四第19页，共53页，2022年，5月20日，7点11分，星期四母函数递推关系递推运算初始值代数运算：化为部分分数的算法第20页，共53页，2022年，5月20日，7点11分，星期四2.3 母函数的性质 一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。 为了求满足某种递推关系的序列，可把它转换为求对应的母函数G(x)，G(x)可能满足一代数方程，或代数方程组，甚至于是微分方程。 最后求逆变换，即从已求得的母函数 G(x)得到序列an。关键在于要搭起从序列到母函数，从母函数到序列这两座桥。21第21页，共53页，2022年，5月20日，7点11分，星

9、期四2.3 母函数的性质对应的母函数分别为、不特别说明,下面假设、两个序列22第22页，共53页，2022年，5月20日，7点11分，星期四性质1：若则 例. 已知则23 例. 已知则mmm-1第23页，共53页，2022年，5月20日，7点11分，星期四 性质2：则若证： 例.24第24页，共53页，2022年，5月20日，7点11分，星期四 性质3：证：若则 ): : : :1 2102102210100LLLLLLLLLLLLLLLL+=+=+=nnaaaabnxaaabxaabxab25第25页，共53页，2022年，5月20日，7点11分，星期四 例. 已知 类似可得：若则26第26

10、页，共53页，2022年，5月20日，7点11分，星期四性质4则证27第27页，共53页，2022年，5月20日，7点11分，星期四 A(x)=a0+a1x+a2x2+, A(x)=a1+2a2x+3a3x2+. 例. 则性质5若则性质6若则求导积分28第28页，共53页，2022年，5月20日，7点11分，星期四性质7若则证29第29页，共53页，2022年，5月20日，7点11分，星期四2.3母函数的性质 例. 已知 30第30页，共53页，2022年，5月20日，7点11分，星期四2.4 Fibonacci数列 Fibonacci数列是递推关系的又一个典型问题。Fibonacci数列是以

11、递归的方法來定义：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, 987, 1597, 2584, 4181, 6765, 10946，0不是第一项，而是第0项。31第31页，共53页，2022年，5月20日，7点11分，星期四1150年印度数学家研究箱子包裝物件长宽刚好 为1和2的可行方法数目时，首先描述这个数列。在西方，1202年，意大利数学家斐波那契出版了他的算盘全书。他在

12、书中提出了一个关于兔子繁殖的问题：第一个月有一对刚诞生的兔子；如果一对兔子每月能生一对小兔（一雄一雌）；而每对小兔在它出生后的第三个月里，又能开始生一对小兔，兔子永不死去；由一对出生的小兔开始，50个月后会有多少对兔子？第n个月相比n-1个月多出的兔子数是n-2个月的兔子生出来的，即Fn=Fn-1+Fn-2 32Leonardo of PisaSon of Bonaccio 第32页，共53页，2022年，5月20日，7点11分，星期四 设2.4.1递推关系第33页，共53页，2022年，5月20日，7点11分，星期四2.4.1递推关系34第34页，共53页，2022年，5月20日，7点11分

13、，星期四 1） 证明：2.4.1递推关系Fn=Fn-1+Fn-235第35页，共53页，2022年，5月20日，7点11分，星期四 2） 证明：2.4.1递推关系Fn=Fn-1+Fn-236第36页，共53页，2022年，5月20日，7点11分，星期四 3） 证明：2.4.1递推关系37第37页，共53页，2022年，5月20日，7点11分，星期四一位魔术师拿着一块边长为8英尺的正方形地毯，对他的地毯匠朋友说：“请您把这块地毯分成四小块，再把它们缝成一块长13英尺，宽5英尺的长方 ” 魔术881350, 1, 1, 2, 3, 5, 8, 13, 21,.35F(n)*F(n) F(n-1)F

14、(n+1) = (-1)nn=0,1,2第38页，共53页，2022年，5月20日，7点11分，星期四斐波那契螺旋 39第39页，共53页，2022年，5月20日，7点11分，星期四2.4.4在选优法上的应用 设函数 在 点取得极大值。要求用若干次试验找到 点准确到一定的程度。最简单的方法，把 三等分，令：如下图：40第40页，共53页，2022年，5月20日，7点11分，星期四2.4.4在选优法上的应用 设函数y=f(x)在区间(a,b)上有一单峰极值点，假定为极大点。 所谓单峰极值，即只有一个极值点，而且当x与偏离越大，偏差|f(x)-f() | 也越大。如下图：41第41页，共53页，2

15、022年，5月20日，7点11分，星期四2.4.4在选优法上的应用 依据 的大小分别讨论如下： 当 ，则极大点 必在 区间上，区间 可以舍去。42第42页，共53页，2022年，5月20日，7点11分，星期四2.4.4在选优法上的应用 当 ，则极大点 必在 区间上，区间 可以舍去。43第43页，共53页，2022年，5月20日，7点11分，星期四2.4.4在选优法上的应用 当 ，则极大点 必在 区间上，区间 和 均可以舍去。44第44页，共53页，2022年，5月20日，7点11分，星期四 可见做两次试验，至少可把区间缩至原来区间的2/3，比如 ，进一步在 区间上找极值点。若继续用三等分法，将

16、面对着这一实事，即其中 点的试验没发挥其作用。为此设想在 区间的两个对称点 分别做试验。45第45页，共53页，2022年，5月20日，7点11分，星期四 设保留 区间，继续在 区间的下面两个点x2,(1-x)x 处做试验，若则前一次 的点的试验，这一次可继续使用可节省一次试验。由(2-3-6)式有0.382，0.6180.236，0.3820.146，0.23646第46页，共53页，2022年，5月20日，7点11分，星期四2.4.4在选优法上的应用 这就是所谓的0.618优选法。即若在 区间上找单峰极大值时，可在 点做试验。比如保留区间 ，由于 ，故只要在 点作一次试验。47第47页，共

17、53页，2022年，5月20日，7点11分，星期四2.4.4在选优法上的应用 优选法中可利用Fibonacci数列，和0.618法不同之点在于它预先确定试验次数，分两种情况介绍其方法。 (a) 所有可能试验数正好是某个Fn。这时两个试验点放在Fn-1和Fn-2两个分点上，如果Fn-1分点比较好，则舍去小于Fn-2的部分；留下的部分共Fn-Fn-2 = Fn-1个分点，其中第Fn-2和第Fn-3二试验点，对应的原标号是Fn-2+Fn-2=2Fn-2以及Fn-3+Fn-2=Fn-1,恰好Fn-1点是刚才留下来的试验可以利用。如果Fn-2点更好，则舍去大于Fn-1的部分。在留下的部分共Fn-1个分点

18、，下一步Fn-2和Fn-3二试验点中，恰好Fn-2是刚才留下来的试验可以利用。可见在Fn个可能试验中，最多用n-1次试验便可得到所求的极值点。48第48页，共53页，2022年，5月20日，7点11分，星期四2.4.4在选优法上的应用 (b)利用Fibonacci数列进行优选不同于 0.618法之点,还在于它适合于参数只能取整数数值的情况.如若可能试验的数目比 小,但比 大时,可以虚加几个点凑成 个点，但新增加的点的试验不必真做，可认定比其他点都差的点来处理。49第49页，共53页，2022年，5月20日，7点11分，星期四2.4.4在选优法上的应用 定理：测试n次可将包含单峰极值点的区间缩小到原区间的 ，其中 是任意小的正整数， 证：对n用数学归纳法。 n=2时，将区间(a.b)平分成F(2+1）=2 段。在分点（包括端点a，b）分别标上0，1，2。在1点的两侧取 ，在（1- ）与(1+ )两点上测试，无论哪一点较优，保留下来的区间长度均为(1+ )，命题成立。50ab0121- 1+第50页，共53页，2022年，5月20日，7点11分，星期四2.4.4在选优法上的应用 假设对于n-1，命题成立 对于n，将(a,b)平分成Fn+1段，对分点