算法常用数学工具_递归方程求解ppt课件.ppt

《算法常用数学工具_递归方程求解ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章常用数学工具1.用生成函数求解递归方程2.用特征方程求解递归方程3.用递推方法求解递归方程1.用生成函数求解递归方程1.1什么是生成函数1.2生成函数的性质1.3用生成函数求解汉诺塔问题1.4用生成函数求解Fabanacci数列通项1.1什么是生成函数对于实数序列：下面函数：称为序列的生成函数。生成函数的作用是进行演算，一般不考虑其收敛性。1.2生成函数的性质加法位移乘法z变换微分和积分都是生成函数，则都是两个序列加权合成后的生成函数1.3用生成函数求解汉诺塔问题递推公式：生成函数：推导：求得，A=-1,B=11.4用生成函数求解Fabanacci数列通项递推公式：生成函数：推导：解出

2、A和B，可以把G(x)写成无穷级数和2.用特征方程求解递归方程2.1k阶常系数线性齐次递归方程2.2k阶常系数线性齐次递归方程举例（一）2.3k阶常系数线性齐次递归方程举例（二）2.4k阶常系数线性齐次递归方程举例（三）—重根的情况2.5k阶常系数线性非齐次递归方程2.6k阶常系数线性非齐次递归方程举例（一）2.7k阶常系数线性非齐次递归方程举例（二）2.1k阶常系数线性齐次递归方程变换到幂次最低（最后一项是0次幂）得特征方程：若方程有k个不同的根q1,…,qk，则递归方程的通解为：若特征方程有t个不等的根q1,q2,…,qt,且qi的重数为ei,那么令那么递推方程的通解是2.2k阶常系数线

3、性齐次递归方程举例（一）齐次递推方程：得到一元方程：该方程只有一个解：递推方程的带参数的通解为：由于f(1)=5，因此c=5/3，所以，问题的通解为：2.3k阶常系数线性齐次递归方程举例（二）齐次递推方程：得到一元二次特征方程：该方程两个解：递推方程的带参数的通解为：由于f(1)=1,f(2)=3，因此由于行列式而(1,1)是方程*的解，因此原方程的通项是2.4k阶常系数线性齐次递归方程举例（三）—重根的情况齐次递推方程：得到一元特征方程：特征根：递推方程的带参通解为：待定系数的线性方程组的解是：c1=5/9,c2=-1/3,c3=4/9通解：2.5k阶常系数线性非齐次递归方程通解为：即齐次

4、通解+特解确定特解的任务就成为关键。根据齐次特征方程根的情况，特解可以分为两种情况：没有等于1的特征根：特解的多项式次数与g(n)相同；含有等于1的特征根：特解的多项式次数比g(n)大1，但不含常数项。2.6k阶常系数线性非齐次递归方程举例（一）非齐次递推方程：齐次方程的解为：特解为：带参数的通解为：带入初始条件得通解为：2.7k阶常系数线性非齐次递归方程举例（二）非齐次递推方程：齐次方程的解为：特解为：带入特解：解得：这是顺序插入算法的复杂度注意特解形式！通解为：带入求解通解为：3.用递推方法求解递归方程3.1求平方和序列的通解3.2用递推方法求汉诺塔问题的复杂度3.1求平方和序列的通解求

5、解析通解：3.2用递推方法求汉诺塔问题的复杂度