第2章常用数学工具1.用生成函数求解递归方程2.用特征方程求解递归方程3.用递推方法求解递归方程1.用生成函数求解递归方程1.1什么是生成函数1.2生成函数的性质1.3用生成函数求解汉诺塔问题1.4用生成函数求解Fabanacci数列通项1.1什么是生成函数,......,......,10naaa010......kkknnzazazaazG对于实数序列:下面函数:称为序列的生成函数。生成函数的作用是进行演算,一般不考虑其收敛性。1.2生成函数的性质加法位移乘法z变换微分和积分0kkkzazG0kkkzbzH都是生成函数,则)(zHzG都是两个序列加权合成后的生成函数1.3用生成函数求解汉诺塔问题111)1(2hnhnh132......321kkxkhxhxhxhxG递推公式:生成函数:xxxxxxhhxhhxhxGx1.........2231221)(213232推导:)21)(1()(xxxxG)21)(1()2()()21()1()(xxxBABAxBxAxG求得,A=-1,B=113322323322)12(...)12()12()12(...)1(...)2221()1(1)21(1)(kkkxxxxxxxxxxxxxG1.4用生成函数求解Fabanacci数列通项1)2(,11)2()1(hhnhnhnh132......321kkxkhxhxhxhxG递推公式:生成函数:xxxxhhhxhhhxhhxhxGxx001...234)1(23121)(124232推导:25125125125125211222xBxAxxxxxxxxxG解出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)(fnfnf3x齐次递推方程:得到一元方程:3x该方程只有一个解:ncnf3)(递推方程的带参数的通解为:由于f(1)=5,因此c=5/3,所以,问题的通解为:nnf335)(2.3k阶常系数线性齐次递归方程举例(二)32,112)1()(ffnfnfnf012xx齐次递推方程:得到一元二次特征方程:251,251xx该方程两个解:nnccnf251251)(21递推方程的带参数的通解为:由于f(1)=1,f(2)=3,因此325325312512512121cccc由于行列式02253253251251325325312512512121cccc而(1,1)是方程*的解,因此原方程的通项是nnnf251251)(2.4k阶常系数线性齐次递归方程举例(三)—重根的情况0)2(,0)1(,5)0(0)3-(4)1(3-)(fffnfnfnf043-23xx齐次递推方程:得到一元特征方程:2,2,-1x特征根:nncnccnf)1(-2)()(321递推方程的带参通解为:待定系数的线性方程组的解是:c1=5/9,c2=-1/3,c3=4/90840-22132132131ccccccccnnnnnf1-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-,2132cc这是顺序插入算法的复杂度注意特解形式!通解为: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()(113nknkknnf3.2用递推方法求汉诺塔问题的复杂度1)1(1)1(2)(fnfnf1)1(2)2(1)2(2)3(......1)2(2)1(1)1(2)(ffffnfnfnfnf1*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)(22101nnnfnf