算法常用数学工具_递归方程求解

第2章常用数学工具1.用生成函数求解递归方程2.用特征方程求解递归方程3.用递推方法求解递归方程1.用生成函数求解递归方程1.1什么是生成函数1.2生成函数的性质1.3用生成函数求解汉诺塔问题1.4用生成函数求解Fabanacci数列通项1.1什么是生成函数,......,......,10naaa010......kkknnzazazaazG对于实数序列：下面函数：称为序列的生成函数。生成函数的作用是进行演算，一般不考虑其收敛性。1.2生成函数的性质加法位移乘法z变换微分和积分0kkkzazG0kkkzbzH都是生成函数，则)(zHzG都是两个序列加权合成后的生成函数1.3用生成函数求解汉诺塔问题111)1(2hnhnh132......321kkxkhxhxhxhxG递推公式：生成函数：xxxxxxhhxhhxhxGx1.........2231221)(213232推导：)21)(1()(xxxxG)21)(1()2()()21()1()(xxxBABAxBxAxG求得，A=-1,B=113322323322)12(...)12()12()12(...)1(...)2221()1(1)21(1)(kkkxxxxxxxxxxxxxG1.4用生成函数求解Fabanacci数列通项1)2(,11)2()1(hhnhnhnh132......321kkxkhxhxhxhxG递推公式：生成函数：xxxxhhhxhhhxhhxhxGxx001...234)1(23121)(124232推导：25125125125125211222xBxAxxxxxxxxxG解出A和B，可以把G(x)写成无穷级数和112512512512512512512511251251251nnnnnnxBxAxxBxAxBxA2.用特征方程求解递归方程2.1k阶常系数线性齐次递归方程2.2k阶常系数线性齐次递归方程举例（一）2.3k阶常系数线性齐次递归方程举例（二）2.4k阶常系数线性齐次递归方程举例（三）—重根的情况2.5k阶常系数线性非齐次递归方程2.6k阶常系数线性非齐次递归方程举例（一）2.7k阶常系数线性非齐次递归方程举例（二）2.1k阶常系数线性齐次递归方程初始条件)(...)2()1()(21knfanfanfanfk变换到幂次最低（最后一项是0次幂）得特征方程：kkkkaxaxax...2211若方程有k个不同的根q1,…,qk，则递归方程的通解为：nkknnqcqcqcnf......)(2211若特征方程有t个不等的根q1,q2,…,qt,且qi的重数为ei,那么令nieieiiiqncnccnfii121...)(那么递推方程的通解是niinfnf1)(2.2k阶常系数线性齐次递归方程举例（一）5)1()1(3)(fnfnf3x齐次递推方程：得到一元方程：3x该方程只有一个解：ncnf3)(递推方程的带参数的通解为：由于f(1)=5，因此c=5/3，所以，问题的通解为：nnf335)(2.3k阶常系数线性齐次递归方程举例（二）32,112)1()(ffnfnfnf012xx齐次递推方程：得到一元二次特征方程：251,251xx该方程两个解：nnccnf251251)(21递推方程的带参数的通解为：由于f(1)=1,f(2)=3，因此325325312512512121cccc由于行列式02253253251251325325312512512121cccc而(1,1)是方程*的解，因此原方程的通项是nnnf251251)(2.4k阶常系数线性齐次递归方程举例（三）—重根的情况0)2(,0)1(,5)0(0)3-(4)1(3-)(fffnfnfnf043-23xx齐次递推方程：得到一元特征方程：2,2,-1x特征根：nncnccnf)1(-2)()(321递推方程的带参通解为：待定系数的线性方程组的解是：c1=5/9,c2=-1/3,c3=4/90840-22132132131ccccccccnnnnnf1-94231-295)(通解：2.5k阶常系数线性非齐次递归方程初始条件)()(...)2()1()(21ngknfanfanfanfk通解为：)()()(*nfnfnf即齐次通解+特解确定特解的任务就成为关键。根据齐次特征方程根的情况，特解可以分为两种情况：没有等于1的特征根：特解的多项式次数与g(n)相同；含有等于1的特征根：特解的多项式次数比g(n)大1，但不含常数项。2.6k阶常系数线性非齐次递归方程举例（一）3)2(,1)1(1)1(2)(ffnfnf非齐次递推方程：齐次方程的解为：ncnf2)(1特解为：2*)(cnf带参数的通解为：212)(ccnfn带入初始条件得通解为：12)(nnf2.7k阶常系数线性非齐次递归方程举例（二）1)1(1)1()(fnnfnf非齐次递推方程：齐次方程的解为：ncnf1)(1特解为：ncncnf322*)(带入特解：1)1-()1-()(322322n-ncncncnc解得：21-,2132cc这是顺序插入算法的复杂度注意特解形式！通解为：12)/1-()(cnnnf带入求解通解为：12)/1-()(nnnf3.用递推方法求解递归方程3.1求平方和序列的通解3.2用递推方法求汉诺塔问题的复杂度3.1求平方和序列的通解11*31*31212*32*323......1)1(3)1(3)1(133)1(233233233233nnnnnnnn2222......321)(nnf求解析通解：3131)1()(113nknkknnf3.2用递推方法求汉诺塔问题的复杂度1)1(1)1(2)(fnfnf1)1(2)2(1)2(2)3(......1)2(2)1(1)1(2)(ffffnfnfnfnf1*2)1(2*2)2(*21*2)2(2*2)3(*2......1*2)2(2*2)1(*21*2)1(2*2)(*2222333111000nnnnnnffffnfnfnfnf12)2...222()1(2)(22101nnnfnf