1、1递归及递归算法分析2主要内容v递归的实现机制递归的实现机制v递归算法编制递归算法编制v递归关系式求解递归关系式求解3递归的实现机制1.递归的概念递归的概念v直接或间接地调用自身的算法称为直接或间接地调用自身的算法称为递归算递归算法法。v用函数自身给出定义的函数称为用函数自身给出定义的函数称为递归函数递归函数。v直接调用自身的算法称为直接递归直接调用自身的算法称为直接递归v间接调用自身的算法称为间接递归间接调用自身的算法称为间接递归4v由分治法产生的子问题往往是原问题的较小由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在模式，这就为使用递归技术提供了方便。在这种情况
2、下，反复应用分治手段，可以使子这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。这自然导致递归过程的产生。v分治与递归像一对孪生兄弟，经常同时应用分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。在算法设计之中，并由此产生许多高效算法。5主程序主程序call A1：2.子程序的内部实现原理子程序的内部实现原理v1）子程序调用的一般形式）子程序调用的一般形式 一次调用一次调用 N次调用次调用 嵌套调用
3、嵌套调用 平行调用平行调用子程序子程序A主程序主程序 call A1：call A2：子程序子程序A主程序主程序 call A1：子程序子程序A子程序子程序Bcall B2：主程序主程序 call B1：子程序子程序Bcall A2：子程序子程序A6v2）值的回传）值的回传v实参和形参的数据传递实参和形参的数据传递传值传值 实参的值不发生改变实参的值不发生改变传地址传地址 实参的值发生改变实参的值发生改变v值的回传通常有两种形式：值的回传通常有两种形式：两次传值方式：按照指定类型为变参设置相应的两次传值方式：按照指定类型为变参设置相应的存储空间，在执行调用时，将实参值传送给变参存储空间，在执行
4、调用时，将实参值传送给变参在返回时将变参的值传给实参。在返回时将变参的值传给实参。传地址：在内部将变参用一个地址替换，调用时，传地址：在内部将变参用一个地址替换，调用时，先执行地址传送，将实参地址传送给变参，在执先执行地址传送，将实参地址传送给变参，在执行过程中，对变参的操作实际变成对实参的操作。行过程中，对变参的操作实际变成对实参的操作。实参实参变参变参12实参实参变参变参X地址地址X7v3)子程序调用的内部操作子程序调用的内部操作v执行调用时，系统完成的操作执行调用时，系统完成的操作返回地址进栈，为子程序的局部变量开辟空间返回地址进栈，为子程序的局部变量开辟空间为子程序准备数据：计算实参值
5、，并将其值送给为子程序准备数据：计算实参值，并将其值送给形参形参转入子程序入口地址转入子程序入口地址v返回时，系统完成的操作：返回时，系统完成的操作：变参或函数的值保存到回传变量中变参或函数的值保存到回传变量中从栈顶取返回地址从栈顶取返回地址返回调用程序返回调用程序将回传变量的值送给实参将回传变量的值送给实参8v3.递归过程的内部实现原理递归过程的内部实现原理程序程序A if 出口条件出口条件 then 简单语句简单语句 else 简单语句；简单语句；call A ； 1：简单语句；：简单语句； endifendAv递归程序的执行令人担心是否引递归程序的执行令人担心是否引发死循环。担心是多余的
6、！发死循环。担心是多余的！v因为每次调用，必有一些数据发因为每次调用，必有一些数据发生变化，直到出现一组数据终止生变化，直到出现一组数据终止递归。这组数据就是递归出口。递归。这组数据就是递归出口。1。1。1执行到出口条件执行到出口条件开始出栈开始出栈9递归举例递归举例v直接递归直接递归proc fact（n） if n=0 then return 1 else return n*fact(n-1)v间接递归间接递归proc p1(n) if n0 then if odd(n) then p1(n-1); print n; else p2(n-1);print n;proc p2(n) if n
7、0 then if n mod 3=0 then p1(n-1) else p2(n-1)10例例1 1 阶乘函数阶乘函数阶乘函数可递归地定义为：阶乘函数可递归地定义为：00)!1(1!nnnnn边界条件边界条件递归方程递归方程边界条件与递归方程是递归函数的二个要素，递归函边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出数只有具备了这两个要素，才能在有限次计算后得出结果。结果。递归函数举例递归函数举例11递归函数举例例例2 Fibonacci2 Fibonacci数列数列无穷数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci
8、数列。它可以递归地定义为：边界条件边界条件递归方程递归方程110)2() 1(11)(nnnnFnFnF第第n个个Fibonacci数可递归地计算如下：数可递归地计算如下：public static int fibonacci(int n) if (n 1n1时，时，perm(R)perm(R)由由(r(r1 1)perm(R)perm(R1 1) )，(r(r2 2)perm(R)perm(R2 2) )，(r(rn n)perm(R)perm(Rn n) )构成。构成。 N!17vr1-t(1)=1vr1、r2-r1perm(R1) r2perm(R2) vt(2)=2*t(1)vr1、r
9、2、r3vr1perm(R1)vr2perm(R2)vr3perm(R3)vt(3)=3*T(2)v.vt(n)=n*t(n-1)18v例例5 整数划分问题整数划分问题v将正整数将正整数n表示成一系列正整数之和：表示成一系列正整数之和：n=n1+n2+nk，v其中其中n1n2nk1，k1。v正整数正整数n的这种表示称为正整数的这种表示称为正整数n的划分。求正整数的划分。求正整数n的不同划分个数。的不同划分个数。 v例如正整数例如正整数6有如下有如下11种不同的划分：种不同的划分：v 6；v 5+1；v 4+2，4+1+1；v 3+3，3+2+1，3+1+1+1；v 2+2+2，2+2+1+1，
10、2+1+1+1+1；v 1+1+1+1+1+1。19v前面的几个例子中，问题本身都具有比较明显的前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。递归关系，因而容易用递归函数直接求解。v在本例中，如果设在本例中，如果设p(n)为正整数为正整数n的划分数，则难的划分数，则难以找到递归关系，因此考虑增加一个自变量：将以找到递归关系，因此考虑增加一个自变量：将最大加数最大加数n1不大于不大于m的划分个数记作的划分个数记作q(n,m)。可。可以建立以建立q(n,m)的如下递归关系。的如下递归关系。11, 1),() 1,() 1,(1),(1),(mnmnmnmnmmnq
11、mnqnnqnnqmnq?20(3) q(n,n)=1+q(n,n-1);v正整数正整数n的划分由的划分由n1=n的划分和的划分和n1n-1的划的划分组成。分组成。(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1 的划分组成。(1) q(n,1)=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，即nn111(2) q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此，q(1,m)=1。包含包含m的划分的划分不包含不包含m21递归算法设计递归算法设计v用递归求解问题的用递归求解问题
12、的3个要求：个要求：1.问题的描述涉及规模问题的描述涉及规模2.规模发生变化后，问题性质不改变规模发生变化后，问题性质不改变3.问题的解决有出口问题的解决有出口proc f（参数表）（参数表） if 递归出口递归出口 then 简单语句；简单语句； else 简单语句；简单语句；call f（参数表）；简单语句；（参数表）；简单语句； endifendf2223例例6 Hanoi6 Hanoi塔问题塔问题设设a,b,ca,b,c是是3 3个塔座。开始时，在塔座个塔座。开始时，在塔座a a上有一叠共上有一叠共n n个圆盘，这个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编些圆盘自下
13、而上，由大到小地叠在一起。各圆盘从小到大编号为号为1,2,1,2,n,n,现要求将塔座现要求将塔座a a上的这一叠圆盘移到塔座上的这一叠圆盘移到塔座b b上，上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则规则1 1：每次只能移动：每次只能移动1 1个圆盘；个圆盘；规则规则2 2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则规则3 3：在满足移动规则：在满足移动规则1 1和和2 2的前提下，可将圆盘移至的前提下，可将圆盘移至a,b,ca,b,c中中任一塔座上。任一塔座上。2
14、4在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。当n1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。例例6 Hanoi6 Hanoi塔问题塔问题 public static void hano
15、i(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 25vn=3 t(3)=7vn=4 t(4)=15vn=10 t(10)=1023vn=16 t(16)=6553426递归小结优点：优点：结构清晰，可读性强，而且容易用数学归纳法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。序带来很大方便。缺点：缺点：递归算法的运行效率较低，无论是耗费的计算递归算法的运行效率较低，
16、无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。时间还是占用的存储空间都比非递归算法要多。27递归算法的时间复杂度分析递归算法的时间复杂度分析v递归函数求解递归函数求解简单递归式求解简单递归式求解master method 递推方程的特征方程求解递推方程的特征方程求解28vpublic static void hanoi(int n, int a, int b, int c)v v if (n 0)v v hanoi(n-1, a, c, b);v move(a,b);v hanoi(n-1, c, b, a);v v vT(n)=2T(n-1)+O(1) n1 0 n=0T(n)=
17、2n-1429简单递归式的求解1.T(n)=T(n-1)+c1 n1 c2 n=12. T(n)=2T(n/2)+c1 n 2 c2 n23. T(n)=2T(n/2)+(n) n 2 O(1) n 1) 0 (n = 1) 例例1 T(n) = 解解 ：T(n)=2T(n/2)+1 =22T(n/22)+2+1 =23T(n/23)+22+2+1 令令2r=n =2rT(1)+2r-1+。+2+1 =(1-2r)/(1-2)=n-1 T( n ) = n - 131 解上述递推式：解上述递推式： T( n ) = 3 T( n/2 ) + k n = 3 3 T( n/22 ) + k (n
18、 / 2 ) + k n =32T(n/22)+3k(n/2)+kn = =3rT(n/2r)+(3/2)r-1kn+.+kn =3rk+ (3/2)r-1kn+.+kn = 3 r+1 k - 2 k n= 3 k 3log2n - 2 k n 3 k n 1.59 - 2 k n = O( n 1. 59 ) 例例2 递推关系式：递推关系式： 3 T( n/2 ) + k n (n 1) k ( n = 1)T (n ) =32 例例3 T( n/2 ) + T( n/2 ) + (n - 1) (n 1) 0 (n = 1)T(n) = 设：设：n = 2r （ r:非负整数）。非负整数
19、）。 有：有：T(n) = 2 T(n/2 ) + ( n - 1 ) T(n/2) = 2 T(n/22 ) + (n/2 - 1) T(n/22) = 2 T(n/23 ) + (n/22 - 1) T(n/2r-1) = 2 T(n/2r ) + (n/2r-1 - 1)+) 2 22 2 22 23 + 22 2r-1 2r 2r-1 T( n ) = 2r T(1) + rn - (2r-1 + 2r-2 + +20) = nlog2n - n +1 = O(nlog n)33Master MethodvT(n)=aT(n/b)+f(n) a1b1vf(n)是一个非负渐进函数是一个非
20、负渐进函数vcase1： 0,使使f(n)=O(nlog ba-) 即即0f(n)0,c0,使使f(n)= (nlog ba+) ,af(n/b)cf(n)v 则则T(n)=(f(n)34v例例1 T(n)=4T(n/2)+nva=4 b=2 f(n)=O(n2-)取取=1 则则T(n)=(n(n2 2) )v例例2 T(n)=4T(n/2)+n2va=4 b=2 f(n)= (n2lgnk)取取K=0v则则T(n)=(n2lgn)v例例3 T(n)=4T(n/2)+n3va=4 b=2 f(n)=n3= (nlog ba+)取取=1v且且4f(n/2)=n3/2 1) 1 ( n = 1)
21、0 ( n = 0)38 解：解：(R): F(n) = F(n -1) + F(n - 2) (E): x2 - x - 1 = 0 (E)的根：的根： x1 = 1/2 + 5 2 , x2 = 1/2 - 5 2 因为因为 x1 x2 所以所以 F(n) = c1(1/2 + 5 2)n +c2 (1/2 - 5 2)n c1 + c2 = 0 c1( 1/2 + 5 2 ) + c2(1/2 - 5 2 ) = 1C1 = 1/ 5C2 = - 1/ 5 F(n) = 1/ 5 (1/2 + 5 2)n - (1/2 - 5 2)n 由由 F(0) = 0 和和F(1) = 1 知：知
22、：392 T( n - 1) + 2 T( n - 2 ) ( n 2 ) 3 ( n = 1 ) 8 ( n = 2 )例例 T( n ) = (R): T( n ) = 2 T( n - 1) + 2 T( n - 2 ) (E): x2 - 2x - 2 = 0 x1 = 1 + 3, x2 = 1 - 3 因为：因为：x1 x2 T(n) = c1(1 + 3)n + c2( 1 - 3)n 由：由：T(1) = 3 和和 T(2) = 8 得：得： c1 = 1/2 + 3/3, c2 = 1/2 - 3/3, 故：故：T(n) = (1/2 + 3/3)(1 + 3)n + (1/
23、2 - 3/3)( 1 - 3)n40 例例 求：求：Sn = K2k = 0n 解：由：解：由： Sn = 12 + 22 + + n2 (1) 递推：递推：S n-1 = 12 + 22 + +(n - 1)2 (2) 由（由（1）- （2） 得：得：Sn - S n-1 = n2 (3) 对（对（3）递推：）递推：Sn-1 - Sn-2 = (n - 1)2 (4) 由由(3) - (4) 得：得：Sn - 2S n-1 + S n-2 = 2n - 1 反复使用上面的方法，消去等号右边多项式，得：反复使用上面的方法，消去等号右边多项式，得： S n - 4Sn-1 + 6Sn-2 -
24、4Sn-3 + Sn-4 = 0 (R) (E): x4-4x3+6x2-4x+1=0 -(x - 1) 4 = 0 x1 = x2 = x3 = x4 = 1541 因为特征方程的解是四重根，所以：因为特征方程的解是四重根，所以： Sn = c11n +c2 n 1n + c3 n2 1n + c4 n3 1n = c1 + c2n + c3n2 + c4n3 由：由： S0 = 0, S1 = 1, S2 = 5, S3 = 14, 知：知： c1 = 0 , c2 = 1/6, c3 = 1/2, c4 = 1/3 所以：所以：Sn = 1/6 n ( n + 1 ) (2 n + 1
25、)42 2 非齐次常系数线性递推方程的特征方程解法非齐次常系数线性递推方程的特征方程解法 （1）定义：）定义：(R)为为k阶非齐次常系数线性递推方程阶非齐次常系数线性递推方程: (R): H(n) = a1H(n - 1)+a2H(n - 2)+ +akH(n - k)+f(n) 其中：其中： 1）a1, a2, , ak为常数；为常数； 2）ak 0, n k, f(n) 0。 （2）（）（R）的解结构：）的解结构： 设：（设：（R）的通解是）的通解是H(n)，且它有一个特解，且它有一个特解H*(n)； 而与（而与（R)相对应的相对应的 齐次方程齐次方程(R)的通解是的通解是H(n)。 则有
26、（则有（R）的解：）的解：H(n) = H(n) + H*(n) 43(3) (R)的特解形式讨论的特解形式讨论 1）当）当f(n) 形如形如bnt( b 0, t:非负整数）时，非负整数）时，(R)的特解为：的特解为： H*(n) = p1nt + p2nt-1+ + pt n + pt+1 其中：其中：p1, p2, ， pt+1是待定系数。是待定系数。 但，当但，当x = 1是是(R)的的 j 重特征根（重特征根（j 1）时，其特解应）时，其特解应 改设为：改设为： H*(n) = p1nt+j + p2nt-1+j+ + pt+1nj 2）当）当f(n) 形如形如 b rn( b 0,
27、 r 0 ）时，）时，(R)的特解为：的特解为： H*(n) = p rn 其中：其中：p是待定系数。是待定系数。 但，当但，当 x = r 是是(R) 对应的对应的(R)的的 j 重特征根重特征根( j 1)时，时， (R)的特解应改设为：的特解应改设为： H*(n) = p nj rn44 T(n) = 2T( n - 1 ) + k (n 1) (k:正数）正数） k ( n = 1 ) 解：解：(R) : T(n) = 2T(n - 1) + k (R) : T(n) = 2T(n - 1) (E): x - 2 = 0 x = 2 (R)的通解：的通解： T(n) = c 2n 因为
28、因为(R)中，中，f(n) = k 所以，所以， 设：设： T*(n) = p 显然，显然， T*(n - 1) = p 45 把把T*(n)、T*(n - 1)代入代入(R) , 有：有：p = 2p + k p = - k 故：故：T*(n) = - k (R)的通解：的通解：T(n) = T(n) + T*(n) = c 2n - k 由由T(1) = k, 把它代入上式，把它代入上式， 有：有：2 c - k = k c = k (R)的通解：的通解：T(n) = k( 2n - 1) = O( 2n )46例例 T(n) = 2n-3 - T( n -2 ) ( n 4 ) 1 (
29、n = 3 ) 2 ( n = 4 ) 解：解：(R): T(n) = - T(n - 2 ) + 2n-3 (R): T(n) = - T(n - 2 ) (E): x2 + 1 = 0 (R) 的通解：的通解：T(n) = c1cos(n /2) + c2sin(n /2) （ 其中：其中： = 1， = /2）47 设：设：(R) 的特解是：的特解是：T*(n) = p 2n 把它代入把它代入(R),有：有：p 2n = - p 2 n-2 + 2 n-3 得：得：p = 1/10 T(n) = c1cos(n /2) + c2sin(n /2) + 2n/10 由：由：T(3) = 1
30、 和和 T(4) = 2, 知：知：c1 = 2/5, c2 = -1/5 故：故： T(n) = 2/5cos(n /2) - 1/5sin(n /2) + 2n/10 （ n 2 ）48 例例 再求：再求：Sn = K2k = 0 n 解：由：解：由： Sn = 12 + 22 + + n2 (1) 递推：递推：S n-1 = 12 + 22 + +(n - 1)2 (2) 由（由（1）- （2） 得：得：Sn - S n-1 = n2 (R) (E): x - 1 = 0 x = 1 (R): Sn - S n-1 = 0 (R)的通解：的通解：Sn = c 设：设：(R)的特解是：的特
31、解是：S*n = p1n3 + p2n2 + p3n 代入代入(R), 得：得：p1 = 1/3, p2 = 1/2, p3 = 1/6 (R)的通解：的通解：Sn = p1n3 + p2n2 + p3n + c 由由S0 = 0,知：知：c = 0 故：故： Sn = p1n3 + p2n2 + p3n49 变系数变系数/非线性递推方程的求解非线性递推方程的求解 原则：原则：“变换变换”。 一、变一、变“非线性非线性”为为“线性线性” 解：令：解：令：G(n) = H2(n),则有：则有：G(n) - 2G(n - 1) = 1 ( G(n) 0, n 0 ) G(0) = 4 解上述递推式
32、，得：解上述递推式，得：G(n) =5 2n - 1 H(n) = 5 2n - 1 H(0) = 2 例例 求求H(n)。已知：。已知：H2(n) - 2H2(n - 1) = 1 ( H(n) 0 , n 0 ) 50 二、变二、变“变系数变系数”为为“常系数常系数” b (n = 1; b:非负常数）非负常数）(n - 1) + 1/n T(k - 1) + 1/nT(n-k) (n 1)k=1 k=1nn T(n) = 51 整理、改写上述递推式：整理、改写上述递推式： T(n) = (n - 1) + 2/n T(k) n-1k=1 nT(n) = n(n - 1) + 2 T(k)
33、 n-1k=1(1)(n-1)T(n-1) = (n-1)(n - 2) + 2 T(k) n-2k=1(2)递推：递推： 由由(1) - (2) 得：得： nT(n) - (n - 1)T(n - 1) = 2(n - 1) + 2T(n - 1) 即：即： T(n) = T(n - 1) + n+11n12(n - 1)n(n + 1)(3) 令：令：Q(n) = T(n), 有：有：Q(n - 1) = T(n - 1)n+11n152 代入代入(3)式：式：Q(n) = Q(n - 1) + n(n + 1)2(n - 1)递推：递推：Q(n - 1) = Q(n - 2) + (n
34、- 1)n2(n - 2) Q(n - 2) = Q(n - 3) + (n - 2)(n - 1)2(n - 3) Q(2) = Q(1) + 2 12 3+) Q(n) - Q(1) = nk=2k(k + 1)2(k - 1) k=2n=k+14-k 2=n+14- 1 + 2 k=3nk153 因为：因为： k=3nk1 3n1xdx= ln n - ln 3 由：由：Q(n) = T(n), 及：及：T(1) = b, 知：知：Q(1) = 1/2bn+11 T(n) = (n + 1) Q(n) 2(n + 1) ln n + (b/2 - 1 - 2ln 3)(n +1) + 4
35、 = O(n ln n)54递归程序的阅读法递归程序的阅读法v用图形方式描述执行轨迹用图形方式描述执行轨迹1.按次序写出程序在当前调用层上实际执行的语句，按次序写出程序在当前调用层上实际执行的语句，并用有向弧表明语句执行次序并用有向弧表明语句执行次序2.对程序中的每个调用语句写出实际调用形式，在对程序中的每个调用语句写出实际调用形式，在其下（右）边写出本次调用的子程序实际执行的其下（右）边写出本次调用的子程序实际执行的语句，用有向弧指示。语句，用有向弧指示。3.被调用子程序执行完有向弧指向其上级（标上形被调用子程序执行完有向弧指向其上级（标上形参的值）参的值）4.变参：再返回路线上增加语句实参
36、变参：再返回路线上增加语句实参=变参变参 函数：函数： 实参实参=函数值函数值最后，顺着有向弧的路径写出结果。最后，顺着有向弧的路径写出结果。55例vproc f(w)v if w0 thenv f(w-1)v print wv f(w-1)v vend f56习题答案习题答案 答：答：T(n) = 2b nlog2n - 2b n + 3b = O(nlog2n) 2. 2. 求解：求解：T(nT(n)= )= aT(n/c) + bnaT(n/c) + bn (n 1) (n 1)b (n = 1)b (n = 1)(a, c:(a, c:正整数；正整数；b: b:正数）正数）答：当答：当
37、 n = cr(r：非负整数：非负整数)时，有时，有 T(n) = (bn) ki(k = a/c)i=0logc nb (n = 1) (b:b (n = 1) (b:正数正数) )T(n/2) + b n logT(n/2) + b n log2 2 n (n 1)n (n 1)T(n) =T(n) =1. 1. 用递推法求解用递推法求解57(1) 当当 ac 时时, T(n) = bn (kr+1 - 1) / (k-1) = bk / (k - 1) ar - bn / (k - 1) = bk/(k - 1) alogcn - bn/(k - 1) = O ( nlogca )3.
38、3. 用特征方程法求解用特征方程法求解T(n)T(n)。已知：。已知： 2 T(n - 1) + n (n 1)2 T(n - 1) + n (n 1) 1 (n = 1) 1 (n = 1)（1）T(n) =T(n) =答：答：T(n) = 2n+1 - ( n + 2 )587T(n 1) - 12T(n 2) + 37T(n 1) - 12T(n 2) + 3n n (n 1) (n 1)0 (n = 0)0 (n = 0)1 (n = 1)1 (n = 1)（2）T(n)=T(n)=答：答： T(n) = 10 4n - ( 3n + 10) 3n 4. 4. 试证：当特征方程试证：当
39、特征方程(E)(E)包含有二重根包含有二重根 x x 1,21,2 = x = xp p 时，齐次方时，齐次方程程(R)(R)通解包含有：通解包含有：T(nT(n)= c)= c1 1x xp pn n + c + c2 2 n x n xp pn n 证：设：齐次常系数线性递推方程如下：证：设：齐次常系数线性递推方程如下： H(n) = a1H(n-1) + a2H(n-2) + +akH(n-k) (R) 它所对应的特征方程是：它所对应的特征方程是： xk - a1xk-1 - a2xk-2 - - ak-1x - ak = 0 (E) 实际上，我们只要证明实际上，我们只要证明x = nx
40、p是是(R)的解，即可。的解，即可。n59 对对(E)两边同乘两边同乘xn-k (x 0)，有：，有： xn - a1xn-1 -a2xn-2 - - a k-1xn-k+1 - ak xn-k = 0 (M) 因为因为(E)有二重根有二重根x1 = x2 = xp， 所以所以(M)式可改写成式可改写成 (x - xp)2 f(x) = 0 (M) 对式对式(M)左边求导，得到：左边求导，得到： nxn-1 - a1(n-1)xn-2 - a2(n-2)xn-3 - - ak-1(n-k+1)xn-k - ak(n-k)xn-k-1 (M) 现证现证(M) 等于零：等于零： 可见，可见， (M
41、) 式实际上就是：式实际上就是： 2(x - xp) f(x) + (x - xp) 2 f (x) =(x - xp)2f(x) + (x - xp) f (x) (N) 显然，当显然，当x = xp仍有仍有(N)等于零。等于零。60 也就是说，把也就是说，把x = xp代入代入(M) ，应当有下式成立：，应当有下式成立： nxpn-1 - a1(n-1)xpn-2 - a2(n-2)xpn-3 - - ak-1(n-k+1)xpn-k - ak(n-k)xpn-k-1 = 0 上式两端同乘以上式两端同乘以xp（xp 0），有：），有： nxpn - a1(n-1)xpn-1 - a2(n-2)xpn-2 - - ak-1(n-k+1)xpn-k+1- ak(n-k)xpn-k = 0 (M) 等于零，证毕。等于零，证毕。 此式说明，此式说明， x = nxp是是(R)的一个解。的一个解。 易证，易证， x = xp是是(R)的另一个解。的另一个解。 综上，特征方程综上，特征方程(E)包含有二重根包含有二重根 x 1,2 = xp 时，齐次方时，齐次方程程(R)通解包含有：通解包含有：T(n) = c1xpn + c2 n xpn，证毕。，证毕。
