求解递归方程-11省公开课一等奖全国示范课微课金奖PPT课件.pptx

求解递归方程;算法复杂性经常描述为递归方程，解递归方程得到算法复杂性详细表示

用特征方程解递归方程

用生成函数解递归方程

用递推方法解递归方程;用特征方程解递归方程;K阶常系数线性齐次递归方程形如：;特征方程以下：

解题原理：

1）求解上述特征方程根，得到递归方程通解

2）利用递归方程初始条件，确定通解中待定系数，得到递归方程解

考虑2种情况：

1）特征方程k个根不相同

2）特征方程有相重根;特征方程k个根不相同：;特征方程k个根有重根：;前面2种情况下c1,c2,…,ck均为待定系数；

将初始条件代入，建立联立方程，确定各个系数详细值，得到通解f(n)

例1.3阶常系数线性齐次递归方程以下;改写方程为：

因式分解：

(x-1)(x-2)(x-3)=0

得到特征根：

q1=1,q2=2,q3=3

递归方程通解为：

;由初始条件得：

得到：c1=0,c2=-2,c3=2

所以，递归方程解为：

;例2。3阶常系数线性齐次递归方程以下;得到特征根：

q1=1,q2=1,q3=3

递归方程通解为：

代入初始条件：

;得到：c1=0,c2=-1,c3=1

所以，递归方程解为：

;作业;K阶常系数线性非齐次递归方程形如：;结题原理：

1.普通没有寻找特解有效方法

2.先依据g(n)详细形式，确定特解；再将特解代入递归方程，用待定系数法，求解特解系数

3.g(n)分为以下几个情况

g(n)是nm次多项式

g(n)是n指数函数

;g(n)是nm次多项式;例3。2阶常系数线性齐次递归方程以下;令非齐次递归方程特解为：

;由此得到联立方程：

解得：A1=1,A2=13/2,A3=103/8

非齐次递归方程通解为：;初始条件代入有：

;22