第5章递归关系及解法.pptVIP

第五章 递推关系及其解法; 例1(“Hanoi塔”问题)：这是个组合数学中的著名问题。n个大小不一的圆盘依其半径大小，从下而上套在A柱上，如下图示。现要求将所有的圆盘从A柱上全部转移到C柱上,每次只允许从一个柱子上转移一个盘子到另一柱子上，且在转移过程中不允许出现大盘放在小盘上方。试问要转移多少次才能将柱A上的n个盘移到C柱上。;例2 “Fibonacci兔子问题”：从某年某月(设为第0月)开始,把雌雄各一的一对小兔放入养殖场,假定两个月后长成成兔,并同时(即第二个月)开始每周产雌雄各一的一对小兔,新增的小兔也按此规律繁殖,问第n个月末养殖场共有多少对兔子? 第n月的兔子包括两部分:上月留下的和当月新生的,而新生的小兔数即为前月末的兔子数,所以 Fn=Fn-1+Fn-2 Fibonacci序列的性质:;§5.2 常系数线性齐次递归关系的解法;特征方程的根与递归关系的解之间的关系：;定理5.2.2 若q1,q2,…,qk为递归关系式(5.2.1)的特征根，c1,c2,…,ck为任意常数，则 为递归关系(5.2.1)的解。 定义5.2.4 若对递归关系(5.2.1)的任意一个解an，都存在一组常数c1,c2,…,ck使得 则称该式为递归关系式(5.2.1)的通解。 定理5.2.3 若q1,q2,…,qk为递归关系式(5.2.1)的k个互不相同的特征根，则式(5.2.4)为(5.2.1)的通解。;例1 求Fibonacci序列的通项。 例2 求解递归关系 ;注：若特征根有复根，复根成对出现，故设 则通解可表示为 其中 ;例3 求解递归关系;2.特征根有重根;例4 求解递归关系 例5 求解递归关系;§5.3 常系数线性非齐次递归关系的解法;定理5.3.1 若 为(5.3.1)的一个特解,而 ( )是由(5.3.1)导出的线性齐次递归关系(5.3.2)的通解,则 为(5.3.1)的通解。 注：由定理5.3.1知, 要求(5.3.1)的通解,只要求它的一个特解及导出的齐次递归关系的通解即可。对非齐线性递归关系的特解, 针对f(n)的特殊形式有以下情形:;1.f(n)是n的t次多项式 ⑴1不是齐次递归关系(5.3.2)的特征根 这时,(5.3.1)的特解形式为 其中 为待定常数。 例1 求解“Hanoi塔”问题的递归关系 例2 求解递归关系;⑵1是齐???递归关系(5.3.2)的m重特征根(m≥1) 这时,(5.3.1)的特解形式为 其中 为待定常数。 例3 求解递归关系 ;2 f(n)是βn的形式 ⑴ β不是导出的齐次线性递归关系的特征根 这时,(5.3.1)的特解形式为 其中 A为待定常数。 例4 求解递归关系 ;⑵β是导出的齐次线性递归关系的m重特征根(m≥1) 这时,(5.3.1)的特解形式为 其中 A为待定常数。 例5 求解递归关系 ;⑶f(n)= βn g(n),其中g(n)为n的t次多项式, β是导 出的齐次线性递归关系的m重特征根(m≥0) 这时,(5.3.1)的特解形式为 其中 为待定常数。 例6 求解递归关系 ;§5.4 递归关系的其他解法;三、母函数法 主要思想: ⑴用f(x)表示序列{a0,a1,a2,…,an,…}的普通母函数,即 ⑵利用递归关系an的表达式与(5.4.1)间的关系将(5.4.1)化为关于f(x)的方程，即有 g(f(x))=0; ⑶解出f(x)； ⑷将f(x)的表达式展开成幂级数的形式，即得an的初等表达式.;例3 求解递归关系 例4 求解递归关系;四、代换法 将序列{a0,a1,a2,…,an,…}的递归关系转换为关于新序列{b0,b1,b2,…,bn,…}的递归序列。 例5 求解递归关系 五、将常系数线性非齐次递归关系转化为常系数齐次递归关系 例6 求an-2an-1=3的通解。 例7 求;§5.5 Stirling数;由定理5.4.1得第1类Stirling数S1(n,k)的数值：;二、第2类Stirling数 若 则称S