递归方程求解
- 格式：docx
- 大小：167.74 KB
- 文档页数：6
解递归方程下面的求解方法，其正确性可阅读组合数学中的相关内容1、 递推法例：Hanoi 塔问题递归算法的时间复杂性，由以下递归方程给出：()2(1) 1 2(1)1T n T n n T =-+≥⎧⎨=⎩递推求解如下：232122122()2(1)12(2(2)1)12(2)212(3)221......2(1)2 (221)22 (221)21n n n n n T n T n T n T n T n T ----=-+=-++=-++=-++++=+++++=+++++=-所以，Hanoi 塔问题递归算法的时间复杂性为：()(2)n T n O =例：分治法实例。
设n 表示问题的尺寸，n/b 表示将问题分成a 个子问题后的每个子问题的尺寸，其中a,b 为常数。
d(n)表示在分解或合成子问题而得到整个问题解决时的时间耗费。
则整个问题的时间耗费由下面的递归方程给出： ()(/)() 2(1)1T n aT n b d n n T =+≥⎧⎨=⎩递推求解如下：222232332210()((/)(/))()(/)(/)()((/)(/))(/)()(/)(/)(/)() ......(/)(/)k k ki i i T n a aT n b d n b d n a T n b ad n b d n a aT n b d n b ad n b d n a T n b a d n b ad n b d n a T n b a d n b -==++=++=+++=+++=+∑设：kn b =，则log b k n =，有： 10()(1)(/)k ki i i T n a T a d n b -==+∑ 当()d n 为常数时，有：log 10()() 1()(log ) 1 b a k k k ii b O a O n a T n a c a O n a -=⎧=≠=+=⎨=⎩∑ 当(),d n cn c =为常数时，有：111000(/)(/)(/)k k k i i i ii i i i a d n b a cn b cn a b ---=====∑∑∑若：a b <，则：10(/)()k i i cn a b O n -==∑log ()()()b a T n n O n O n =+=若：a b =，则：10(/)log k i b i cn a b cnk cn n -===∑log ()log (log )b a b b T n n cn n O n n =+=若：a b >，则：1log log 0(/)1(/)()()()/1/1b b k k kk n a ik i a b a b cn a b cn c O a O a O n a b a b -=--=====--∑ log log log ()()()b b b a a a T n n O n O n =+=综上所述：log () ()(log ) () b n O n a b T n O n n a b O na b ⎧<⎪==⎨⎪>⎩2、公式解法K 阶常系数齐次递推方程：12()(1)(2)...()0k T n a T n a T n a T n k -------= 0,,,1,...,k i a n k a i k ≠≥=是常数则对应的特征方程为：1212...0k k k k x a x a x a ------=特征方程有k 个根：12,,...,k q q q ，称为齐次方程的特征根。
若：k 个根中无重根，则齐次方程的通解为：1122()...n n nk k T n c q c q c q =+++其中的系数为待定系数，由方程的初始条件确定。
若：k 个根中有r 重根，12,,...,k q q q 中，11...i i i r q q q ++-===，则齐次方程的通解为：1111111()...(...)...n n r n n n i i i i i r i i r i r k k T n c q c q c c n c n q c q c q ---++-++=+++++++++例：求解递归方程()(1)3(2)5(3)2(4)0 4(0)1,(1)0,(2)1,(3)2T n T n T n T n T n n T T T T +-------=≥⎧⎨====⎩ 解：递归方程的特征方程为 4323520x x x x +---=其特征根为：-1，-1，-1，2递归方程通解为：21234()()(1)2n n T n C C n C n C =++-+由初始条件有： 1412341234123412024413982C C C C C C C C C C C C C C +=⎧⎪---+=⎪⎨+++=⎪⎪---+=⎩ 解得：1234712,,0,939C C C C ==-== 因此递归方程的解为：712()(1)(1)2939n n n T n n =---+⋅K 阶常系数线性非齐次递推方程：12()(1)(2)...()()k T n a T n a T n a T n k f n -------= 0,()0,()()k a f n f n T n ≠≠与线性无关 方程通解为：()()*()T n T n T n =+ ，其中()T n 是对应的齐次方程的通解， *()T n 是一个特解。
当f(n)是n 的t 次多项式时，可设特解*()T n 也是n 的t 次多项式：1121*()...t t t t T n Pn P n Pn P -+=++++，其中121,,...,t PP P +是待定系数，将*()T n 代入原递推方程后即可求出。
例：求解递归方程的一个特解2()5(1)6(2)3T n T n T n n +-+-=解：设特解为2123*()T n P nP n P =++，代入原递归方程有：2221231231235((1)(1))6((2)(2))P n P n P P n P n P P n P n P n +++-+-++-+-+= 化简有：2211212312(3412)(291712)3Pn P P n P P P n +-++-+=比较两边的系数，有11123123341202917120P P P P P P =⎧⎪-+=⎨⎪-+=⎩ 解得：123117115,,424288P P P === 因此递归方程的特解为：2117115*()424288T n n n =++ 当f(n)是指数函数时，若().n f n αβ=，其中,αβ为给定系数。
若β不是对应的齐次方程的特征根，则可设特解：*()n T n P β=⋅，其中P 待定。
若β是对应的齐次方程的e 重特征根，则可设特解：*()e n T n Pn β=⋅，其中P 待定。
例：求解递归方程()5(1)6(2)424(0)0,(1)0nT n T n T n T T ⎧+-+-=⋅⎨==⎩ 解：递归方程对应的齐次方程的特征方程为：2560x x ++=，解为-2，-3 递归方程对应的齐次方程的通解为：12()(2)(3)n n T n C C =-+-设特解为*()4n T n P =⋅，代入原递归方程有： 1245464424n n n n P P P --⋅+⋅+⋅=⋅解得：16P =，递归方程的特解为：*()164nT n =⋅ 递归方程的解为：12()()*()(2)(3)164n n n T n T n T n C C =+=-+-+⋅由初始条件得： 1212160(2)(3)640C C C C ++=⎧⎨-+-+=⎩ 解得：12112,96C C =-=所以递归方程的解为：()112(2)96(3)164n n n T n =--+-+⋅3、 生成函数法设01,,...,,...n a a a 是一个数列，作形式幂级数：2012()......n n A x a a x a x a x =+++++称A(x)是数列01,,...,,...n a a a 的生成函数。
当{}n a 的通项由递归方程的形式给出时，利用生成函数可以求解出n a 的结果。
例：Hanoi 塔问题中，若：n a 表示移动n 个盘子所需要的移动次数，则递归方程有： 11211n n a a a -=+⎧⎨=⎩ 解：以{}n a 为系数构造生成函数：212()......n n A x a x a x a x =++++ 231212()22...2...n n xA x a x a x a x --=----+2312132111223(12)()(2)(2)...(2)... (2) ...1n n n ii i i x A x a x a a x a a x a a x a x a a x x x x xx -∞-=-=+-+-++-+=+-=+++=-∑223323111()(1)(12)121(1222....)(1...)(21)i ii x A x x x x xx x x x x x x ∞===-----=++++-++++=-∑其中n x 的系数为21n -，所以有21n n a =- 所以，Hanoi 塔问题递归算法的时间复杂性为：(2)nO练习：用公式法求解： ()2(1) 1 2(1)1T n T n n T =-+≥⎧⎨=⎩ 1、 求通解： 特征方程： 202x x -== 通解为：()2n T n c =2、 求特解： *()T n p =代入原递推方程： 211p p p =+=- 方程的解为： ()21n T n c =- 代入初始条件： (1)2111T c c =-== ()21n T n ∴=-。
