递推方程与生成函数精选文档.ppt
《递推方程与生成函数精选文档.ppt》由会员分享,可在线阅读,更多相关《递推方程与生成函数精选文档.ppt(87页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、递推方程与生成函数递推方程与生成函数1本讲稿第一页,共八十七页13.1递推方程的定义及实例递推方程的定义及实例定义定义13.1 设序列设序列 a0,a1,an,简记为简记为 an.一个把一个把 an 与与某些个某些个ai(in)联系起来的等式叫做关于序列联系起来的等式叫做关于序列 an 的的递推方递推方程程.当给定递推方程和适当的初值就唯一确定了序列当给定递推方程和适当的初值就唯一确定了序列.Fibonacci数列数列:1,1,2,3,5,8,记作,记作 fn.递推方程递推方程 fn=fn 1+fn 2 初值初值 f0=1,f1=1 阶乘计算数列:阶乘计算数列:1,2,6,24,5!,!,,记
2、作记作 F(n)递推方程递推方程 F(n)=nF(n 1)初值初值 F(1)=1 2本讲稿第二页,共八十七页例例1 从从A柱将这些圆盘移到柱将这些圆盘移到C柱上去柱上去.如果把一个圆盘从如果把一个圆盘从一个柱子移到另一个柱子称作一次移动,在移动和放置一个柱子移到另一个柱子称作一次移动,在移动和放置时允许使用时允许使用B柱,但不允许大圆盘放到小圆盘的上面柱,但不允许大圆盘放到小圆盘的上面.问问把所有的圆盘的从把所有的圆盘的从A移到移到C总计需要多少次移动?总计需要多少次移动?初值是初值是 T(1)=1 可证明解是可证明解是 T(n)=2n 1 移动移动n个盘子的总次数为个盘子的总次数为T(n).
3、因此得到递推方程因此得到递推方程 T(n)=2T(n 1)+1.递推方程的实例递推方程的实例:Hanoi塔塔3本讲稿第三页,共八十七页两个排序算法两个排序算法归并算法归并算法 Mergesort(A,p,r)/对对A的下标的下标p到到r之间数排序之间数排序1.if p 0 and Ai key5.do Ai+1 Ai;i i 17.Ai+1 key 4本讲稿第四页,共八十七页递推方程的实例递推方程的实例:算法分析算法分析例例2 哪种排序算法在最坏情况下复杂度比较低?哪种排序算法在最坏情况下复杂度比较低?插入排序,归并排序插入排序,归并排序 插入排序插入排序 W(n)=W(n 1)+n 1 W(
4、1)=0解得解得 W(n)=O(n2).归并排序,不妨设归并排序,不妨设 n=2k.W(n)=2W(n/2)+n1 W(1)=0解得解得 W(n)=O(nlogn)5本讲稿第五页,共八十七页13.2 递推方程的公式解法递推方程的公式解法l特征方程、特征根特征方程、特征根l递推方程的解与特征根的关系递推方程的解与特征根的关系l无重根下通解的结构无重根下通解的结构l求解实例求解实例l有重根下通解的结构有重根下通解的结构l求解实例求解实例6本讲稿第六页,共八十七页其中其中 a1,a2,ak为为常数,常数,ak 0 称称为为 k 阶阶常系数常系数线线性性齐齐次次递递推方程推方程 b0,b1,bk 1
5、为为 k 个个初初值值定义定义13.2 常系数线性齐次递推方程的标准形:常系数线性齐次递推方程的标准形:常系数线性齐次递推方程常系数线性齐次递推方程实例:实例:Fibonacci 数列的递推方程数列的递推方程7本讲稿第七页,共八十七页特征方程与特征根特征方程与特征根 定定义义13.3 特征方程特征方程 xk a1xk 1 ak=0,特征方程的根称特征方程的根称为递为递推方程的推方程的 特征根特征根 实实例:例:递递推方程推方程 fn=fn 1+fn 2 特征方程特征方程 x2 x 1=0 特征根特征根8本讲稿第八页,共八十七页递推方程解与特征根的关系递推方程解与特征根的关系定理定理13.1 设
6、设 q 是非零复数,则是非零复数,则 qn 是递推方程的解当且仅当是递推方程的解当且仅当q 是它的特征根是它的特征根.qn是递推方程的解是递推方程的解 qn a1qn 1 a2qn 2 akqn k=0 qn k(qk a1qk 1 a2qk 2 ak)=0 qk a1qk 1 a2qk 2 ak=0 (因为(因为q 0)q 是它的特征根是它的特征根 定理定理13.2 设设 h1(n)和和 h2(n)是递推方程的解,是递推方程的解,c1,c2为任意常数为任意常数,则则 c1h1(n)+c2h2(n)也是这个递推方程的解也是这个递推方程的解.推论推论 若若 q1,q2,qk 是递推方程的特征根,
7、则是递推方程的特征根,则 c1q1n+c2q2n+ckqkn 是该递推方程的解,其中是该递推方程的解,其中c1,c2,ck 是任意常数是任意常数.9本讲稿第九页,共八十七页无重根下通解的结构无重根下通解的结构定义定义13.4 若对常系数线性齐次递推方程的每个解若对常系数线性齐次递推方程的每个解 h(n)都都存在一组常数存在一组常数c1,c2,ck 使得使得 h(n)=c1 q1n+c2 q2n+ck qkn 成立,则称成立,则称 c1q1n+c2q2n+ckqkn 为该递推方程的为该递推方程的通解通解 定理定理13.3 设设q1,q2,qk 是是常系数线性齐次常系数线性齐次递推方程不等递推方程
8、不等的特征根,则的特征根,则 H(n)=c1q1n+c2q2n+ckqkn为该递推方程的通解为该递推方程的通解.10本讲稿第十页,共八十七页例例3 Fibonacci 数列:数列:fn=fn 1+fn 2,特征根,特征根为为 通解通解为为 代入初代入初值值 f0=1,f1=1,得得 解得解得 解是解是实例实例11本讲稿第十一页,共八十七页有重根下求解中的问题有重根下求解中的问题例例4 4解解 特征方程特征方程 x2 4x+4=0 通解通解 H(n)=c12n+c22n=c2n 代入初值得:代入初值得:c 无解无解.问题:两个解线性相关问题:两个解线性相关 12本讲稿第十二页,共八十七页有重根下
9、的通解结构有重根下的通解结构定理定理13.4 设设 q1,q2,qt 是是递递推方程的不相等的特征根,推方程的不相等的特征根,且且 qi 的重数的重数为为 ei,i=1,2,t,令,令那么通解那么通解 13本讲稿第十三页,共八十七页例例5 求解以下求解以下递递推方程推方程其中待定常数其中待定常数满满足以下方程足以下方程组组 原方程的解原方程的解为为 解解 特征方程特征方程 x4+x3 3x2 5x 2=0,特征根特征根 1,1,1,2通解为通解为求解实例求解实例14本讲稿第十四页,共八十七页l递推方程的标准型递推方程的标准型l通解结构通解结构l特解的求法特解的求法 多项式函数多项式函数 指数函
10、数指数函数 组合形式组合形式常系数线性非齐次递推方程求解常系数线性非齐次递推方程求解15本讲稿第十五页,共八十七页证证 代入代入验证验证,H(n)是解是解.下面下面证证明任意解明任意解 h(n)为为某个某个齐齐次解次解与特解与特解H*(n)之和之和.设设 h(n)为递为递推方程的解,推方程的解,则则h(n)H*(n)是是齐齐次解,即次解,即 h(n)是一个是一个齐齐次解与次解与H*(n)之和之和.定理定理13.5 设设是是对应齐对应齐次方程的通解,次方程的通解,H*(n)是一个特解,是一个特解,则则 是递推方程的通解是递推方程的通解.递推方程的标准型及通解递推方程的标准型及通解16本讲稿第十六
11、页,共八十七页解解 设设 an*=P1n2+P2n+P3,代入代入递递推方程得推方程得 P1n2+P2n+P3 2P1(n 1)2+P2(n 1)+P3=2n2 整理得整理得 P1n2+(4P1 P2)n+(2P1+2P2 P3)=2n2 解得解得 P1=2,P2=8,P3=12,原方程的通解原方程的通解为为 an=c2n 2(n2+4n+6)例例6 找出递推方程找出递推方程 an 2an 1=2n2 的通解的通解如果如果 f(n)为为n次多项式,则特解一般也是次多项式,则特解一般也是 n 次多项式次多项式特解的形式:多项式特解的形式:多项式17本讲稿第十七页,共八十七页例例7 Hanoi塔塔
12、 T(n)=2T(n 1)+1 T(1)=1 实例实例解解 令令 T*(n)=P代入方程代入方程 P=2P+1解得解得 P=1 T(n)=c 2n1,代入初值得代入初值得 c=1,解为解为 T(n)=2n 1.18本讲稿第十八页,共八十七页例例8 求解关于求解关于顺顺序插入排序算法的序插入排序算法的递递推方程推方程解解 设设特解特解为为W*(n)=P1n+P2,代入,代入递递推方程,得推方程,得 P1n+P2 (P1(n 1)+P2)=n 1无解无解.设设特解特解W*(n)=P1n2+P2n,代入代入递递推方程得推方程得 (P1n2+P2n)(P1(n 1)2+P2(n 1)=n 1 解得解得
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 方程 生成 函数 精选 文档
限制150内