母函数与递推关系优秀PPT.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《母函数与递推关系优秀PPT.ppt》由会员分享,可在线阅读,更多相关《母函数与递推关系优秀PPT.ppt(53页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、母函数与递推关系你现在浏览的是第一页,共53页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没有实际意义没有实际意义你现在浏览的是第二页,共53页
2、二项式定理你现在浏览的是第三页,共53页42.2 2.2 递推关系递推关系 利用递推关系进行计数这个方法在算法分析中经常用到 例一.Hanoi问题:N个圆盘依其半径大小,从下而上套在A柱上。每次只允许取一个移到柱B或C上,而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来,并估计要移动几个盘次。现在只有A、B、C三根柱子可用。设计算法;估计它的复杂性,即估计工作量.你现在浏览的是第四页,共53页52.2 2.2 递推关系递推关系算法:算法:N=2时第一步先把最上面的一个圆盘套在B上第二步把下面的一个圆盘移到C上 最后把B上的圆盘移到C上 到此转移完毕A B C你现在浏
3、览的是第五页,共53页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你现在浏览的是第六页,共53页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)次算法复杂度为:构造母函数为:求
4、得了母函数,对应的序列也就求得h(n)A B C你现在浏览的是第七页,共53页82.2 2.2 递推关系递推关系所谓形式算法说的是假定这些幂级数在作四则运算时,一如有限项的代数式一样。你现在浏览的是第八页,共53页9如何从母函数得到序列?化为部分分数的算法。由上式可得:g(x)=1+x+x2+x3+x4+.=即:你现在浏览的是第九页,共53页102.2 2.2 递推关系递推关系 或利用递推关系(2-2-1)有 上式左端为:右端第一项为:右端第二项为:你现在浏览的是第十页,共53页112.2 2.2 递推关系递推关系例例2.2.求n位十进制数中出现偶数个5的数的个数。先从分析n位十进制数出现偶数
5、个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)。你现在浏览的是第十一页,共53页12a1=8,b1=1你现在浏览的是第十二页,共53页132.2 2.2 递推关系递推关系故得关于母函数A(x)和B(x)得连立方程组:你现在浏览的是第十三页,共53页142
6、.2 2.2 递推关系递推关系解法二:解法二:n-1位的十进制数的全体共910n-1个(最高位不为0),设所求数为an,设A(x)=a1x+a2x2+,按照尾数是否为5分类:尾数不是为5的:9an-1尾数为5的,前n-1位有奇数个5:你现在浏览的是第十四页,共53页152.2 2.2 递推关系递推关系验证:a1=8,a2=73你现在浏览的是第十五页,共53页16 1)不出现某特定元素设为a1,其组合数为 ,相当于排除a1后从a2,.an 中取r个做允许重复的组合。2.2 2.2 递推关系递推关系例三:例三:从n个元素a1,a2,.an中取r个进行允许重复的组合。假定允许重复的组合数用 表示,其
7、结果可能有以下两种情况。2)至少出现一个a1,取组合数为 相当于从a1,a2,.an中取r-1个做允许重复的组合,然后再加上一个a1得从n个元素中取r个允许重复的组合。你现在浏览的是第十六页,共53页172.2 2.2 递推关系递推关系 因 ,故令系数(1-x)不是常数。但你现在浏览的是第十七页,共53页18 由二项式定理 可得你现在浏览的是第十八页,共53页你现在浏览的是第十九页,共53页母函数递推关系递推运算初始值代数运算:化为部分分数的算法你现在浏览的是第二十页,共53页2.3 2.3 母函数的性质母函数的性质 一个序列和它的母函数一一对应。给了序列便得知一个序列和它的母函数一一对应。给
8、了序列便得知它的母函数;反之,求得母函数序列也随之而定。它的母函数;反之,求得母函数序列也随之而定。为了求满足某种递推关系的序列,可把它转换为求为了求满足某种递推关系的序列,可把它转换为求对应的母函数对应的母函数G(x),G(x)可能满足一代数方程,或可能满足一代数方程,或代数方程组,甚至于是微分方程。代数方程组,甚至于是微分方程。最后求逆变换,即从已求得的母函数最后求逆变换,即从已求得的母函数 G(x)得到序列得到序列 an。关键在于要搭起从序列到母函数,从母函数到序列这两座桥。关键在于要搭起从序列到母函数,从母函数到序列这两座桥。21你现在浏览的是第二十一页,共53页2.3 2.3 母函数
9、的性质母函数的性质对应的母函数分别为对应的母函数分别为、不特别说明不特别说明,下面假设下面假设、两个序列两个序列22你现在浏览的是第二十二页,共53页性质性质1:若则 例例.已知则23 例例.已知则mmm-1你现在浏览的是第二十三页,共53页 性质性质2:则若证:证:例例.24你现在浏览的是第二十四页,共53页 性质性质3:证:证:若则 ):1 2102102210100LLLLLLLLLLLLLLLL+=+=+=nnaaaabnxaaabxaabxab25你现在浏览的是第二十五页,共53页 例例.已知已知 类似可得:类似可得:若则26你现在浏览的是第二十六页,共53页性质性质4则证27你现在
10、浏览的是第二十七页,共53页 A(x)=a0+a1x+a2x2+,A(x)=a1+2a2x+3a3x2+.例例.则性质性质5 5若若则则性质性质6 6若若则则求导积分28你现在浏览的是第二十八页,共53页性质性质7 7若若则则证证29你现在浏览的是第二十九页,共53页2.32.3母函数的性质母函数的性质 例例.已知 30你现在浏览的是第三十页,共53页2.4 2.4 FibonacciFibonacci数列数列 Fibonacci数列是递推关系的又一个典型问题。数列是递推关系的又一个典型问题。Fibonacci数列是以递归的方法來定义:数列是以递归的方法來定义:F0=0,F1=1,Fn=Fn-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 函数 关系 优秀 PPT
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内