递推方程与生成函数.ppt

主要内容主要内容l递推方程的定义及实例递推方程的定义及实例l递推方程的公式解法递推方程的公式解法l递推方程的其他解法递推方程的其他解法l生成函数及其应用生成函数及其应用l指数生成函数及其应用指数生成函数及其应用lCatalan数与数与Stirling数数第十三章第十三章 递推方程与生成函数递推方程与生成函数113.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！，！，,记作记作 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).因此得到递推方程因此得到递推方程 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(1)=0解得解得 W(n)=O(n2).归并排序，不妨设归并排序，不妨设 n=2k.W(n)=2W(n/2)+n1 W(1)=0解得解得 W(n)=O(nlogn)513.2 递推方程的公式解法递推方程的公式解法l特征方程、特征根特征方程、特征根l递推方程的解与特征根的关系递推方程的解与特征根的关系l无重根下通解的结构无重根下通解的结构l求解实例求解实例l有重根下通解的结构有重根下通解的结构l求解实例求解实例6其中其中 a1,a2,ak为为常数，常数，ak 0 称称为为 k 阶阶常系数常系数线线性性齐齐次次递递推方程推方程 b0,b1,bk 1 为为 k 个个初初值值定义定义13.2 常系数线性齐次递推方程的标准形：常系数线性齐次递推方程的标准形：常系数线性齐次递推方程常系数线性齐次递推方程实例：实例：Fibonacci 数列的递推方程数列的递推方程7特征方程与特征根特征方程与特征根 定定义义13.3 特征方程特征方程 xk a1xk 1 ak=0，特征方程的根称特征方程的根称为递为递推方程的推方程的 特征根特征根 实实例：例：递递推方程推方程 fn=fn 1+fn 2 特征方程特征方程 x2 x 1=0 特征根特征根8递推方程解与特征根的关系递推方程解与特征根的关系定理定理13.1 设设 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 是递推方程的特征根，则是递推方程的特征根，则 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 是是常系数线性齐次常系数线性齐次递推方程不等递推方程不等的特征根，则的特征根，则 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有重根下的通解结构有重根下的通解结构定理定理13.4 设设 q1,q2,qt 是是递递推方程的不相等的特征根，推方程的不相等的特征根，且且 qi 的重数的重数为为 ei，i=1,2,t，令，令那么通解那么通解 13例例5 求解以下求解以下递递推方程推方程其中待定常数其中待定常数满满足以下方程足以下方程组组 原方程的解原方程的解为为 解解 特征方程特征方程 x4+x3 3x2 5x 2=0,特征根特征根 1,1,1,2通解为通解为求解实例求解实例14l递推方程的标准型递推方程的标准型l通解结构通解结构l特解的求法特解的求法 多项式函数多项式函数 指数函数指数函数 组合形式组合形式常系数线性非齐次递推方程求解常系数线性非齐次递推方程求解15证证 代入代入验证验证,H(n)是解是解.下面下面证证明任意解明任意解 h(n)为为某个某个齐齐次解次解与特解与特解H*(n)之和之和.设设 h(n)为递为递推方程的解，推方程的解，则则h(n)H*(n)是是齐齐次解，即次解，即 h(n)是一个是一个齐齐次解与次解与H*(n)之和之和.定理定理13.5 设设是是对应齐对应齐次方程的通解，次方程的通解，H*(n)是一个特解，是一个特解，则则 是递推方程的通解是递推方程的通解.递推方程的标准型及通解递推方程的标准型及通解16解解 设设 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塔塔 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 解得解得 P1=1/2,P2=1/2.通解通解为为 W(n)=c 1n+n(n 1)/2=c+n(n 1)/2代入初代入初值值W(1)=0，得到，得到W(n)=n(n 1)/2=O(n2).实实 例例(续续)19特解的形式特解的形式:指数指数f(n)为指数函数为指数函数 n，若若 是是 e 重特征根重特征根(e可以等于可以等于0)，则特，则特解为解为Pne n,其中其中P为待定常数为待定常数.例例9 通信编码问题通信编码问题 解解 an=6an 1+8n 1,a1=7 设设 a*n=P 8n 1,代入得代入得 P=4 通解通解 an=c 6n+4 8n 1 代入初值得代入初值得 an=(6n+8n)/2 例例10 H(n)5H(n1)+6H(n2)=2n，解解 令令 H*(n)=Pn2n 代入得代入得 Pn2n 5P(n1)2n1+6P(n2)2n2=2n 解得解得 P=2,特解特解 H*(n)=n2n+1 20l换元法换元法l迭代归纳法迭代归纳法l应用实例应用实例 13.3 递推方程的其他解法递推方程的其他解法21思想：通思想：通过换过换元元转转化成常系数化成常系数线线性性递递推方程推方程 解解 令令代入得代入得 bn=2 bn1+1，b0=4解得解得 例例11an0换元法换元法22解解 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 例例12 归并排序归并排序换元法换元法:实例实例23迭代归纳法：归并排序迭代归纳法：归并排序例例1324迭代归纳法：错位排列迭代归纳法：错位排列例例14 Dn=(n1)(Dn1+Dn2)解：解：25快速排序算法快速排序算法算法算法 Quicksort(A,p,r)/p 和和 r 分别表示分别表示A首和末元素下标首和末元素下标 1.if p r 2.then qPartition(A,p,r)/划分为划分为Ap.q 1和和Aq+1.r 3.ApAq 4.Quicksort(A,p,q 1)5.Quicksort(A,q+1,r)26划分过程划分过程算法算法 Partition(A,p,r)1.x Ap /选首元素作为划分标准选首元素作为划分标准x2.i p 1 3.j r+14.while true 5.do repeat j j 1 6.until A j x /Ai是从前找的第一个比是从前找的第一个比x大的元大的元素素9.if i j /继续搜索继续搜索Ai到到Aj之间的范围之间的范围10 then A i A j /A i 与与A j 交换，回到交换，回到行行411.else return j/结束结束While循环循环27实例实例 27 99 0 8 13 64 86 16 7 10 88 25 90 i j 27 25 0 8 13 64 86 16 7 10 88 99 90 i j 27 25 0 8 13 10 86 16 7 64 88 99 90 i j 27 25 0 8 13 10 7 16 86 64 88 99 90 j i 16 25 0 8 13 10 7 27 86 64 88 99 90 28平均情况时间复杂度分析平均情况时间复杂度分析递推方程递推方程差消法化简差消法化简29迭代求解迭代求解30递归树递归树W(n)=n k(1+2+2k 1)=nk (2k 1)=n log n n+13113.4 生成函数及其应用生成函数及其应用l牛顿二项式系数与牛顿二项式定理牛顿二项式系数与牛顿二项式定理l生成函数的定义生成函数的定义l生成函数的应用生成函数的应用32牛顿二项式系数牛顿二项式系数定定义义13.5 设设 r 为实为实数，数，n为为整数，引入形式符号整数，引入形式符号称称为为牛牛顿顿二二项项式系数式系数.实例实例33牛顿二项式定理牛顿二项式定理定理定理13.6（牛（牛顿顿二二项项式定理）式定理）设设 为实为实数，数，则对则对一切一切实实数数x,y，|x/y|0为常为常数数.当当 p 上涨时上涨时 q 将减少将减少.供给关系：供给关系：p=kr，其中，其中p为价格，为价格，r 为供给量，为供给量，k0为常数为常数.当当p上涨时，上涨时，r 将增加将增加.假设价格随需求量能做到即时变化，而商品生产和流通需要假设价格随需求量能做到即时变化，而商品生产和流通需要时间，因此供给量随价格的变化需要时间，因此供给量随价格的变化需要1个单位时间的延迟个单位时间的延迟.假假定每个时间的需求量都和供给量相等，考虑一个时间序列定每个时间的需求量都和供给量相等，考虑一个时间序列0,1,n,，设时间，设时间0的价格是的价格是 p0，求时间，求时间 n 的价格的价格 pn.练习练习682设设第第 n 时间时间的价格的价格为为 pn,需求量需求量为为 qn，供，供给给量量为为 rn，那么有，那么有 练习练习6代入得到代入得到 解得解得837用三个用三个1、两个、两个2、五个、五个3可以组成多少个不同的四位数可以组成多少个不同的四位数？如果这个四位数是偶数，那么又有多少个？如果这个四位数是偶数，那么又有多少个？练习练习7其中其中x4的系数的系数为为 因此因此 a4=71.84练习练习8方法一方法一.n 个编号球恰放入个编号球恰放入 k 个相同盒子且不允许相邻编号个相同盒子且不允许相邻编号在同一盒的方法数在同一盒的方法数.选定球选定球a1,进行变换：如果进行变换：如果a1自己在一自己在一个盒子，将盒子拿走，得到个盒子，将盒子拿走，得到 n 1个不同球恰放入个不同球恰放入k 1个相个相同同盒且相邻编号不落入同一盒子的方法盒且相邻编号不落入同一盒子的方法.如果与如果与a1在同一盒子的球有在同一盒子的球有 将球将球 放入放入 所在的盒子，所在的盒子，然后拿走含然后拿走含a1的盒子，从而得到的盒子，从而得到n 1个不同球个不同球恰好放到恰好放到 k 1个盒子且至少两个相邻标号球落入同一盒的个盒子且至少两个相邻标号球落入同一盒的方法方法.所求方法数等于所求方法数等于n 1个不同球恰好放入个不同球恰好放入k 1个相同盒个相同盒子子的方法数，即的方法数，即 .再考虑盒子编号为再考虑盒子编号为 8用恰好用恰好k 种可能的种可能的颜颜色做旗子，使得每面旗子由色做旗子，使得每面旗子由 n 条彩条彩带带构成（构成（n k），且相），且相邻邻两彩两彩带带的的颜颜色都不相同，色都不相同，证证明不同明不同的旗子数是的旗子数是85方法二方法二数学归纳法数学归纳法.当当 n=1,必有必有 k=1,这时有这时有 ，命题为真，命题为真.假设对一切假设对一切 n,k 命题为真，考虑命题为真，考虑 n+1条使用条使用 k 种颜色的涂色种颜色的涂色方案方案.若用若用 k 种颜色涂色前种颜色涂色前 n 条，最后一条有条，最后一条有 k 1 种选择，种选择，方法数为方法数为 .若用若用 k 1 种颜色涂色前种颜色涂色前 n 条，选条，选择择颜色的方式数为颜色的方式数为 k,涂色方法数为涂色方法数为 因此由乘法法则得因此由乘法法则得 .再根据加法法则，总方再根据加法法则，总方法数为法数为根据归纳法命题成立根据归纳法命题成立.86方法三方法三令令n+1个球恰落入个球恰落入k+1相同盒子且球编号不相邻方法数为相同盒子且球编号不相邻方法数为 将这些方法分成两类：其中第将这些方法分成两类：其中第 n+1个球独占一盒的方法数个球独占一盒的方法数为为 ；第；第 n+1个球不独占一个盒子的方法数为个球不独占一个盒子的方法数为 与第二类与第二类Stirling数递推方程初值一样，因此数递推方程初值一样，因此考虑盒子编号，于是得到考虑盒子编号，于是得到 n+1个球恰好落入个球恰好落入k+1个不同的盒个不同的盒子，且球的编号不相邻的方法数为子，且球的编号不相邻的方法数为87