《母函数与递推关系》PPT课件.ppt

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 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没有实际意义,二项式定理,4,2.2 递推关系,利用递推关系进行计数这个方法在算法分析中经常用到,例一.Hanoi问题： N个圆盘依其半径大小，从下而上套在A柱上。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。 设计算法; 估计它的复杂性，即估计工作量.,5,2.2 递推关系,算法：,N=2时,第一步先把最上面的一个圆盘套在B上,第二步把下面的一个圆盘移到C上,最后把B上的圆盘移到C上,到此转移完毕,6,2.2 递推关系,假定n-1个盘子的转移算法已经确定。 对于一般n个圆盘的问题,先把上面的n-1个圆盘经过C转移到B; 第二步把A下面一个圆盘移到C上 最后再把B上的n-1个圆盘经过A转移到C上 n=2时，算法是对的，因此，n=3是算法是对的。以此类推。,7,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),8,2.2 递推关系,所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。,9,如何从母函数得到序列 ？ 化为部分分数的算法。,由上式可得：,g(x)=1+x+x2+x3+x4+. =,即：,10,2.2 递推关系,或利用递推关系(2-2-1)有,上式左端为：,右端第一项为：,右端第二项为：,11,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)。,12,a1=8, b1=1,13,2.2 递推关系,故得关于母函数A(x)和B(x)得连立方程组：,14,2.2 递推关系,解法二：n-1位的十进制数的全体共910n-1个(最高位不为0)，设所求数为an,设A(x)= a1x+a2x2+,按照尾数是否为5分类： 尾数不是为5的：9an-1 尾数为5的，前n-1位有奇数个5：,15,2.2 递推关系,验证：a1=8,a2=73,16,1）不出现某特定元素设为a1，其组合数为 ，相当于排除a1后从a2,.an 中取r个做允许重复的组合。,2.2 递推关系,例三：从n个元素a1,a2,.an中取r个进行允许重复的组合。假定允许重复的组合数用 表示，其结果可能有以下两种情况。,2）至少出现一个a1，取组合数为 相当于从a1,a2,.an中取r-1个做允许重复的组合，然后再加上一个a1得从n个元素中取r个允许重复的组合。,17,2.2 递推关系,因 ，故令,系数(1-x)不是常数。但,18,由二项式定理,可得,母函数,递推关系 递推运算 初始值 代数运算： 化为部分分数的算法,2.3 母函数的性质,一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。 为了求满足某种递推关系的序列，可把它转换为求对应的母函数G(x)，G(x)可能满足一代数方程，或代数方程组，甚至于是微分方程。 最后求逆变换，即从已求得的母函数 G(x)得到序列an。 关键在于要搭起从序列到母函数，从母函数到序列这两座桥。,21,2.3 母函数的性质,22,性质1：,例. 已知,则,23,例. 已知,则,m,m,m-1,性质2：,则,若,证：,例.,24,性质3：,证：,25,例. 已知,类似可得：,若,则,26,性质4,则,证,27,A(x)=a0+a1x+a2x2+, A(x)=a1+2a2x+3a3x2+,例.,则,性质5,性质6,求导,积分,28,性质7,若,则,证,29,2.3 母函数的性质,例. 已知,30,2.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, 987, 1597, 2584, 4181, 6765, 10946， 0不是第一项，而是第0项。,31,1150年印度数学家研究箱子包裝物件长宽刚好 为1和2的可行方法数目时，首先描述这个数列。 在西方，1202年，意大利数学家斐波那契出版了他的算盘全书。他在书中提出了一个关于兔子繁殖的问题： 第一个月有一对刚诞生的兔子； 如果一对兔子每月能生一对小兔（一雄一雌）； 而每对小兔在它出生后的第三个月里，又能开始生一对小兔， 兔子永不死去； 由一对出生的小兔开始，50个月后会有多少对兔子？ 第n个月相比n-1个月多出的兔子数是n-2个月的兔子生出来的，即 Fn=Fn-1+Fn-2,32,Leonardo of Pisa Son of Bonaccio,设,2.4.1 递推关系,2.4.1 递推关系,34,1）,证明：,2.4.1 递推关系,Fn=Fn-1+Fn-2,35,2）,证明：,2.4.1 递推关系,Fn=Fn-1+Fn-2,36,3）,证明：,2.4.1 递推关系,37,一位魔术师拿着一块边长为8英尺的正方形地毯，对他的地毯匠朋友说：“请您把这块地毯分成四小块，再把它们缝成一块长13英尺，宽5英尺的长方 ”,魔术,8,8,13,5,0, 1, 1, 2, 3, 5, 8, 13, 21,.,3,5,F(n)*F(n) F(n-1)F(n+1) = (-1)n n=0,1,2,斐波那契螺旋,39,2.4.4 在选优法上的应用,设函数 在 点取得极大值。要求用若干次试验找到 点准确到一定的程度。最简单的方法，把 三等分，令：,如下图：,40,2.4.4 在选优法上的应用,设函数y=f(x)在区间(a,b)上有一单峰极值点，假定为极大点。,所谓单峰极值，即只有一个极值点，而且当x与偏离越大，偏差|f(x)-f() | 也越大。如下图：,41,2.4.4 在选优法上的应用,依据 的大小分别讨论如下：,当 ，则极大点 必在 区间上，区间 可以舍去。,42,2.4.4 在选优法上的应用,当 ，则极大点 必在 区间上，区间 可以舍去。,43,2.4.4 在选优法上的应用,当 ，则极大点 必在 区间上，区间 和 均可以舍去。,44,可见做两次试验，至少可把区间缩至原来区间的2/3，比如 ，进一步在 区间上找极值点。 若继续用三等分法，将面对着这一实事，即其中 点的试验没发挥其作用。为此设想在 区间的两个对称点 分别做试验。,45,设保留 区间，继续在 区间的下面两个点x2,(1-x)x 处做试验，若,则前一次 的点的试验，这一次可继续使用可节省一次试验。由(2-3-6)式有,0.382，0.618 0.236，0.382 0.146，0.236,46,2.4.4 在选优法上的应用,这就是所谓的0.618优选法。即若在 区间上找单峰极大值时，可在,点做试验。比如保留区间 ，由于 ，故只要在,点作一次试验。,47,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个分点，下一步Fn-2和Fn-3二试验点中，恰好Fn-2是刚才留下来的试验可以利用。 可见在Fn个可能试验中，最多用n-1次试验便可得到所求的极值点。,48,2.4.4 在选优法上的应用,(b)利用Fibonacci数列进行优选不同于 0.618法之点,还在于它适合于参数只能取整数数值的情况.如若可能试验的数目比 小,但比 大时,可以虚加几个点凑成 个点，但新增加的点的试验不必真做，可认定比其他点都差的点来处理。,49,2.4.4 在选优法上的应用,定理：测试n次可将包含单峰极值点的区间缩小到原区间的 ，其中 是任意小的正整数，,证：对n用数学归纳法。,n=2时，将区间(a.b)平分成F(2+1）=2 段。在分点（包括端点a，b）分别标上0，1，2。在1点的两侧取 ，在（1- ）与(1+ )两点上测试，无论哪一点较优，保留下来的区间长度均为(1+ )，命题成立。,50,a,b,0,1,2,1- ,1+,2.4.4 在选优法上的应用,假设对于n-1，命题成立,对于n，将(a,b)平分成Fn+1段，对分点（包括端点a，b）依次标上0,1,2。先在Fn点与Fn-1点测试 无论哪一点较优，保留下来的区间均为Fn段。 根据归纳假设，再做n-1次测试（内含前两次测试之一）可将含极值点的区间缩小到1+ 段，即原区间的1/Fn+1+ 。,51,Fn+1 Fn-1 = Fn,2.4.4 在选优法上的应用,因 , 当n较大时，可将相继的两个测试点取在待测区间的0.618及1-0.618处。由,可知，0.618法比 法最多多测试一次。0.618 法的优点是不必事先定测试次数。,52,2.4.4 在选优法上的应用,定理：设在给定区间内有单峰极值点。如果包含极值点在内的可测点为Fn+2-1个，则测试n次必可找