1、第 2章 递推关系与母函数2.1 递推关系2.2 母函数 (生成函数 )2.3 Fibonacci数列 2.4 优选法与 Fibonacci序列的应用2.5 母函数的性质 (一 )2.6 线性常系数齐次递推关系 (二 )2.7 关于常系数齐次递推关系 (三 ) 2.8 整数的拆分 (四 )2.9 ferrers图像2.10 拆分数估计2.11 指数型母函数 (五 )2.12 广义二项式定理2.13 应用举例 (六 )2.14 非线性递推关系举例2.15 递推关系解法的补充12.1 递推关系例一 .Hanoi塔问题： N个半径各不相同的圆盘，三根圆柱 A,B,C;算法：n=1时，直接把 A柱的盘
2、移到 C上。n1时，先把 A柱最上面的 n-1张盘通过 C柱移到 B上 ;然后再将 A柱上最下面的盘移到 C盘上 ;最后将 B盘上的盘通过 A盘移到 C盘上。递归是子程序或函数重复地调用自己22.1 递推关系void hanoi(char A,char B,char C,int n)if (n=1)printf(“move disk1 from %c to %c” A,C) else hanoi(A,C,B,n-1);printf(“move disk %d from %c to %c”,n,A,C ) hanoi(B,A,C,n-1);32.1 递推关系例一 .Hanoi塔问题： N个半径各
3、不相同的圆盘，三根圆柱 A,B,C;算法：n=1时， 1次n1时， hn=2hn-1+1求总共需要移动多少次？设分别为 h1,h2, hn42.1 递推关系递推关系的定义 :对于数列 a1,a2,a n,除了前面的若干数外,其余各项 an与它前面的若干个数关联起来的方程叫做递推关系。边界条件 (初始条件 )：在求解递推关系时，前面必须知道若干个数，这若干个已知的数称为初始条件，或边界条件。常系数递推关系。线性递推关系。52.1 递推关系用迭代法求解递推关系6例一、求解盘片为 n的汉诺塔的算法如下：hanoi(int n,char A,char B,char C)if (n=1)printf(“
4、Move disk %d from A to C”,n );elsehanoi(n-1,A,C,B);printf(“Move disk %d from A to C”,n );hanoi(n-1,B,A,C);求时间复杂性7解：设 n张盘需执行 h(n)次h(n)=2h(n-1)+2h(n-1)=2h(n-2)+2h(n-2)=2h(n-3)+2h(3)=2h(2)+2h(2)=2h(1)+2h(1)=2h(2)=22+2h(3)=23+22+2h(n-1)=2n-1+2n-2+2h(n)=2n+2n-1+2 2+2h(n)=2n+1-2O(2n)*例 题8例 2-2 Fibonacci(费卜拉契）数列问题：设有初生的雌、雄小兔一对，但第 2个月过后便每月繁殖雌、雄各一的小兔一对，试问第 n个月有雌、雄兔子多少对？2.1 递推关系1， 1， 2， 3， 5， 8， 13， 21Fn= Fn-1+Fn-2 9算法 :int fibonacci(int n)if (n=1|n=2)return(1);elsereturn(fibonacci(n-1)+fibonacci(n-2);2.1 递推关系*时间复杂性： f(n)=f(n-1)+f(n-2)+110
