递推方程与生成函数.ppt

1,主要内容递推方程的定义及实例递推方程的公式解法递推方程的其他解法生成函数及其应用指数生成函数及其应用Catalan数与Stirling数,第十三章递推方程与生成函数,2,13.1递推方程的定义及实例,定义13.1设序列a0,a1,an,简记为an.一个把an与某些个ai(ikey5.doAi+1Ai;ii17.Ai+1key,5,递推方程的实例:算法分析,例2哪种排序算法在最坏情况下复杂度比较低？插入排序，归并排序插入排序W(n)=W(n1)+n1W(1)=0解得W(n)=O(n2).归并排序，不妨设n=2k.W(n)=2W(n/2)+n1W(1)=0解得W(n)=O(nlogn),6,13.2递推方程的公式解法,特征方程、特征根递推方程的解与特征根的关系无重根下通解的结构求解实例有重根下通解的结构求解实例,7,其中a1,a2,ak为常数，ak0称为k阶常系数线性齐次递推方程b0,b1,bk1为k个初值,定义13.2常系数线性齐次递推方程的标准形：,常系数线性齐次递推方程,实例：Fibonacci数列的递推方程,8,特征方程与特征根,9,递推方程解与特征根的关系,定理13.1设q是非零复数，则qn是递推方程的解当且仅当q是它的特征根.,qn是递推方程的解qna1qn1a2qn2akqnk=0qnk(qka1qk1a2qk2ak)=0qka1qk1a2qk2ak=0（因为q0）q是它的特征根,定理13.2设h1(n)和h2(n)是递推方程的解，c1,c2为任意常数,则c1h1(n)+c2h2(n)也是这个递推方程的解.推论若q1,q2,qk是递推方程的特征根，则c1q1n+c2q2n+ckqkn是该递推方程的解，其中c1,c2,ck是任意常数.,10,无重根下通解的结构,定义13.4若对常系数线性齐次递推方程的每个解h(n)都存在一组常数c1,c2,ck使得h(n)=c1q1n+c2q2n+ckqkn成立，则称c1q1n+c2q2n+ckqkn为该递推方程的通解,定理13.3设q1,q2,qk是常系数线性齐次递推方程不等的特征根，则H(n)=c1q1n+c2q2n+ckqkn为该递推方程的通解.,11,例3Fibonacci数列：fn=fn1+fn2，特征根为,通解为,代入初值f0=1,f1=1,得,解得,解是,实例,12,有重根下求解中的问题,例4,解特征方程x24x+4=0通解H(n)=c12n+c22n=c2n代入初值得：c无解.问题：两个解线性相关,13,有重根下的通解结构,定理13.4设q1,q2,qt是递推方程的不相等的特征根，且qi的重数为ei，i=1,2,t，令,那么通解,14,例5求解以下递推方程,其中待定常数满足以下方程组,原方程的解为,解特征方程x4+x33x25x2=0,特征根1,1,1,2,通解为,求解实例,15,递推方程的标准型通解结构特解的求法多项式函数指数函数组合形式,常系数线性非齐次递推方程求解,16,递推方程的标准型及通解,17,例6找出递推方程an2an1=2n2的通解,如果f(n)为n次多项式，则特解一般也是n次多项式,特解的形式：多项式,18,例7Hanoi塔T(n)=2T(n1)+1T(1)=1,实例,解令T*(n)=P代入方程P=2P+1解得P=1T(n)=c2n1,代入初值得c=1,解为T(n)=2n1.,19,例8求解关于顺序插入排序算法的递推方程,解设特解为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)=c1n+n(n1)/2=c+n(n1)/2代入初值W(1)=0，得到W(n)=n(n1)/2=O(n2).,实例(续),20,特解的形式:指数,f(n)为指数函数n，若是e重特征根(e可以等于0)，则特解为Pnen,其中P为待定常数.,例9通信编码问题解an=6an1+8n1,a1=7设a*n=P8n1,代入得P=4通解an=c6n+48n1代入初值得an=(6n+8n)/2,例10H(n)5H(n1)+6H(n2)=2n，解令H*(n)=Pn2n代入得Pn2n5P(n1)2n1+6P(n2)2n2=2n解得P=2,特解H*(n)=n2n+1,21,换元法迭代归纳法应用实例,13.3递推方程的其他解法,22,思想：通过换元转化成常系数线性递推方程,解令,代入得bn=2bn1+1，b0=4解得,例11,an0,换元法,23,解H(k)=2H(k1)+2k1H(1)=1令H*(k)=P1k2k+P2,解得P1=P2=1H*(k)=k2k+1通解H(k)=c2k+k2k+1代入初值得c=1H(k)=2k+k2k+1W(n)=nlognn+1,例12归并排序,换元法:实例,24,迭代归纳法：归并排序,例13,25,迭代归纳法：错位排列,例14Dn=(n1)(Dn1+Dn2),解：,26,快速排序算法,算法Quicksort(A,p,r)/p和r分别表示A首和末元素下标1.ifpr2.thenqPartition(A,p,r)/划分为Ap.q1和Aq+1.r3.ApAq4.Quicksort(A,p,q1)5.Quicksort(A,q+1,r),27,划分过程,算法Partition(A,p,r)1.xAp/选首元素作为划分标准x2.ip13.jr+14.whiletrue5.dorepeatjj16.untilAjx/Ai是从前找的第一个比x大的元素9.ifi0为常数.当p上涨时，r将增加.假设价格随需求量能做到即时变化，而商品生产和流通需要时间，因此供给量随价格的变化需要1个单位时间的延迟.假定每个时间的需求量都和供给量相等，考虑一个时间序列0,1,n,，设时间0的价格是p0，求时间n的价格pn.,练习6,83,设第n时间的价格为pn,需求量为qn，供给量为rn，那么有,练习6,代入得到,解得,84,7用三个1、两个2、五个3可以组成多少个不同的四位数？如果这个四位数是偶数，那么又有多少个？,练习7,其中x4的系数为,因此a4=71.,85,练习8,方法一.n个编号球恰放入k个相同盒子且不允许相邻编号在同一盒的方法数.选定球a1,进行变换：如果a1自己在一个盒子，将盒子拿走，得到n1个不同球恰放入k1个相同盒且相邻编号不落入同一盒子的方法.如果与a1在同一盒子的球有将球放入所在的盒子，然后拿走含a1的盒子，从而得到n1个不同球恰好放到k1个盒子且至少两个相邻标号球落入同一盒的方法.所求方法数等于n1个不同球恰好放入k1个相同盒子的方法数，即.再考虑盒子编号为,8用恰好k种可能的颜色做旗子，使得每面旗子由n条彩带构成（nk），且相邻两彩带的颜色都不相同，证明不同的旗子数是,86,方法二,数学归纳法.当n=1,必有k=1,这时有，命题为真.假设对一切n,k命题为真，考虑n+1条使用k种颜色的涂色方案.若用k种颜色涂色前n条，最后一条有k1种选择，方法数为.若用k1种颜色涂色前n条，选择颜色的方式数为k,涂色方法数为因此由乘法法则得.再根据加法法则，总方法数为根