离散数学-101递推方程与生成函数.ppt
课件,1,第10章 递推方程与生成函数,课件,2,第10章 递推方程与生成函数,10.1 递推方程及其应用10.2 生成函数及其应用10.3 指数生成函数及其应用10.4 Catalan数与Stirling数,课件,3,10.1 递推方程及其应用,10.1.1 递推方程的定义及实例10.1.2 常系数线性齐次递推方程的求解10.1.3 常系数线性非齐次递推方程的求解10.1.4 递推方程的其他解法10.1.5 递推方程与递归算法,课件,4,递推方程的定义,定义10.1 设序列 a0,a1,an,简记为 an.一个把 an 与某些个ai(in)联系起来的等式叫做关于序列 an 的递推方程.当给定递推方程和适当的初值就唯一确定了序列.例如，Fibonacci数列：1，1，2，3，5，8，记作 fn.递推方程 fn=fn1+fn2 初值 f0=1，f1=1 阶乘计算数列：1，2，6，24，5！，,记作 F(n)递推方程 F(n)=nF(n1)初值 F(1)=1,课件,5,化简得 an=6an1+8n1,可以解得 an=(6n+8n)/2,递推方程的实例计数编码,例1 一个编码系统用八进制数字对信息编码，一个码是有效的当且仅当含有偶数个7,求 n 位长的有效码字有多少个？解 设所求有效码字为 an个.分类处理、分步处理得到递推方程和初值如下：an=7an1+8n1 an1 a1=7,课件,6,递推方程的实例Hanoi塔,例2 从A柱将这些圆盘移到C柱上去.如果把一个圆盘从一个柱子移到另一个柱子称作一次移动，在移动和放置时允许使用B柱，但不允许大圆盘放到小圆盘的上面.问把所有的圆盘的从A移到C总计需要多少次移动？,初值是 T(1)=1 可证明解是 T(n)=2n1,移动n个盘子的总次数为T(n).因此得到递推方程 T(n)=2T(n1)+1.,课件,7,递推方程的实例算法分析,例3 哪种排序算法在最坏情况下复杂度比较低？插入排序，归并排序 插入排序 W(n)=W(n 1)+n 1 W(1)=0解得 W(n)=O(n2).归并排序，不妨设 n=2k.W(n)=2W(n/2)+n1 W(1)=0解得 W(n)=O(nlogn),课件,8,常系数线性齐次递推方程求解,其中 a1,a2,ak为常数，ak 0 称为 k 阶常系数线性齐次递推方程 b0,b1,bk1 为 k 个初值实例：Fibonacci 数列的递推方程,定义10.2 常系数线性齐次递推方程的标准形：,课件,9,常系数线性齐次递推方程的公式解法,特征方程、特征根递推方程的解与特征根的关系解的线性性质无重根下通解的结构求解实例有重根下通解的结构求解实例,课件,10,特征方程与特征根,课件,11,递推方程解与特征根的关系,定理10.1 设 q 是非零复数，则 qn 是递推方程的解当且仅当 q 是它的特征根.证 qn 是递推方程的解 qn a1qn1 a2qn2 ak qnk=0 qnk(qk a1qk1 a2qk2 ak)=0 qk a1qk1 a2qk2 ak=0 q 是它的特征根 注：这里递推方程指常系数线性齐次递推方程,课件,12,解的线性性质,定理10.2 设 h1(n)和 h2(n)是递推方程的解，c1,c2为任意常数，则 c1h1(n)+c2h2(n)也是这个递推方程的解.证 将 c1h1(n)+c2h2(n)代入该递推方程进行验证.推论 若 q1,q2,qk 是递推方程的特征根，则 c1q1n+c2q2n+ckqkn是该递推方程的解，其中c1,c2,ck 是任意常数.注：这里的递推方程指的是常系数线性齐次递推方程,课件,13,无重根下通解的结构,定义10.4 若对常系数线性齐次递推方程的每个解 h(n)都存在一组常数c1,c2,ck 使得 h(n)=c1q1n+c2q2n+ckqkn 成立，则称 c1q1n+c2q2n+ckqkn 为该递推方程的通解 定理10.3 设q1,q2,qk 是常系数线性齐次递推方程不等的特征根，则 H(n)=c1q1n+c2q2n+ckqkn为该递推方程的通解.,课件,14,定理的证明,证：H(n)是解.设 h(n)是递推方程的任意解，h(0),h(1),h(k1)由初 值 b0,b1,bk1唯一确定.代入方程得到方程组,系数行列式,当 qi qj 时，方程组有唯一解,课件,15,求解实例,例4 Fibonacci 数列：fn=fn1+fn2，特征根为,通解为,代入初值 f0=1,f1=1,得,解得,解是,课件,16,有重根下求解中的问题,例5,解 特征方程 x24x+4=0 通解 H(n)=c12n+c22n=c2n 代入初值得：c无解.问题：两个解线性相关,课件,17,有重根下的通解结构,定理10.4 设 q1,q2,qt 是递推方程的不相等的特征根，且 qi 的重数为 ei，i=1,2,t，令,那么通解,课件,18,求解实例,例6 求解以下递推方程,其中待定常数满足以下方程组,原方程的解为,解 特征方程 x4+x33x25x2=0,特征根21,1,2,通解为,课件,19,常系数线性非齐次递推方程求解,递推方程的标准型通解结构特解的求法多项式函数指数函数组合形式,课件,20,递推方程的标准型及通解,课件,21,特解的形式多项式,例7 找出递推方程 an 2an1=2n2 的通解,如果f(n)为n次多项式，则特解一般也是n次多项式,课件,22,实例,例8 Hanoi塔 T(n)=2T(n1)+1 T(1)=1 解 令 T*(n)=P代入方程 P=2P+1解得 P=1 T(n)=c 2n1,代入初值得 c=1,解为 T(n)=2n 1.,课件,23,例9 求解关于顺序插入排序算法的递推方程,解 设特解为W*(n)=P1n+P2，代入递推方程，得 P1n+P2(P1(n1)+P2)=n1无解.设特解W*(n)=P1n2+P2n,代入递推方程得(P1n2+P2n)(P1(n1)2+P2(n1)=n1 解得 P1=1/2,P2=1/2.通解为 W(n)=c 1n+n(n1)/2=c+n(n1)/2代入初值W(1)=0，得到W(n)=n(n1)/2=O(n2).,实例(续),课件,24,特解的形式指数,f(n)为指数函数 n，若 不是特征根，则特解为 H*(n)=P n 其中P为待定常数.例10 通信编码问题 解 an=6an1+8n1,a1=7 设 a*n=P 8n1,代入得 P=4 通解 an=c6n+48n1 代入初值得 an=(6n+8n)/2,课件,25,特解的形式指数(续),若是e重特征根，则特解为Pne n 例11 H(n)5H(n1)+6H(n2)=2n，解 令 H*(n)=Pn2n 代入得 Pn2n 5P(n1)2n1+6P(n2)2n2=2n 解得 P=2 特解 H*(n)=n2n+1,课件,26,特解的组合形式,例12 an 2an1=n+3n a0=0 解 设特解为 an*=P1n+P2+P33n 代入原方程得(P1n+P2+P33n)2P1(n1)+P2+P33n1=n+3n解得 P1=1,P2=2,P3=3 通解 an=c2n n 2+3n+1 代入初值得 c=1，an=2n n 2+3n+1,课件,27,换元法迭代归纳法递归树差消法尝试法应用实例,递推方程的其他解法,课件,28,换元法,思想：通过换元转化成常系数线性递推方程,解 令,代入得 bn=2 bn1+1，b0=4解得,例13,an0,课件,29,实例,解 H(k)=2 H(k1)+2k1 H(1)=1 令 H*(k)=P1k2k+P2,解得 P1=P2=1 H*(k)=k2k+1通解 H(k)=c 2k+k2k+1 代入初值得 c=1 H(k)=2k+k2k+1 W(n)=n log n n+1,例14 归并排序,课件,30,迭代归纳法归并排序,例15,课件,31,迭代归纳法错位排列,例16 Dn=(n1)(Dn1+Dn2),解：,课件,32,差消法化简递推方程,例17,课件,33,积分近似,课件,34,递归树二分归并排序,T(n),T(n/2)T(n/2),T(n/4)T(n/4)T(n/4)T(n/4),1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1,T(n)=nk(1+2+2k1)=nk(2k 1)=n log n n+1,课件,35,(1)T(n)=C,左边=O(1),尝试法,例18,(2)T(n)=cn,左边=cn,课件,36,尝试法(续),(3)T(n)=cn2,左边=cn2,(4)T(n)=cnlogn,左边=cnlogn,课件,37,积分近似,课件,38,分治策略与递归算法,n为输入规模，n/b为子问题输入规模，a为子问题个数，d(n)为分解及综合的代价,课件,39,分治策略与递归算法(续),(1)d(n)=c,实例：二分搜索 W(n)=W(n/2)+1 a=1,b=2,d(n)=c W(n)=O(logn),课件,40,分治策略与递归算法(续),(2)d(n)=cn,实例：归并排序 W(n)=2W(n/2)+n1 a=2,b=2,d(n)=O(n),W(n)=O(nlogn),课件,41,实例位乘问题,位乘问题：X,Y 为 n 位二进制数，n=2k,求 XY 一般方法：W(n)=O(n2)分治法：令X=A2n/2+B,Y=C2n/2+D,则 XY=AC 2n+(AD+BC)2n/2+BD W(n)=4 W(n/2)+cn W(1)=1 a=4，b=2,W(n)=O(nlog4)=O(n2)变换：AD+BC=(AB)(DC)+AC+BD W(n)=3 W(n/2)+cn W(1)=1 a=3，b=2,W(n)=O(nlog3)=O(n1.59),
