组合数学 第二节第一节.ppt

* * 第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 递推关系解法的补充 2.1 递推关系 例一.Hanoi塔问题：N个半径各不相同的圆盘，三根圆柱A,B,C; 算法： n=1时，直接把A柱的盘移到C上。 n1时，先把A柱最上面的n-1张盘通过C柱移到B上; 然后再将A柱上最下面的盘移到C盘上; 最后将B盘上的盘通过A盘移到C盘上。 递归是子程序或函数重复地调用自己 2.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); } } 2.1 递推关系 例一.Hanoi塔问题：N个半径各不相同的圆盘，三根圆柱A,B,C; 算法： n=1时，1次 n1时，hn=2hn-1+1 求总共需要移动多少次？ 设分别为h1,h2,…,hn 2.1 递推关系 递推关系的定义: 对于数列a1,a2,…,an,除了前面的若干数外,其余各项an与它前面的若干个数关联起来的方程叫做递推关系。 边界条件(初始条件)：在求解递推关系时，前面必须知道若干个数，这若干个已知的数称为初始条件，或边界条件。 常系数递推关系。线性递推关系。 2.1 递推关系 用迭代法求解递推关系 例一、求解盘片为n的汉诺塔的算法如下： hanoi(int n,char A,char B,char C) {if (n==1) printf(“Move disk %d from A to C”,n); else hanoi(n-1,A,C,B); printf(“Move disk %d from A to C”,n); hanoi(n-1,B,A,C); } 求时间复杂性 解：设n张盘需执行h(n)次 h(n)=2h(n-1)+2 h(n-1)=2h(n-2)+2 h(n-2)=2h(n-3)+2 …………… h(3)=2h(2)+2 h(2)=2h(1)+2 h(1)=2 h(2)=22+2 h(3)=23+22+2 ………… h(n-1)=2n-1+2n-2+…+2 h(n)=2n+2n-1+…+22+2 h(n)=2n+1-2 O(2n) *** 例 题 例2-2 Fibonacci(费卜拉契）数列 问题：设有初生的雌、雄小兔一对，但第2个月过后便每月繁殖雌、雄各一的小兔一对，试问第n个月有雌、雄兔子多少对？ 2.1 递推关系 1，1，2，3，5，8，13，21 Fn= Fn-1+Fn-2 算法: int fibonacci(int n) {if (n=1||n=2) return(1); else return(fibonacci(n-1)+fibonacci(n-2)); } 2.1 递推关系 ** 时间复杂性：f(n)=f(n-1)+f(n-2)+1 2.2 母函数 例2-3：有红球两个，白球、黄球各一个，试求有多少种不同的组合方案，假设两个红球没有区别。 共有1+3+4+3+1=12种组合方案。 解：一、用组合方法来解： 一个都不选:1种方案 选1个球，3种方案 选2个球，4种方案 选3个球，3种方案 选4个球，1种方案 二、用函数的方法 解：设r，w，y分别代表红球，白球，黄球； 单独红球的组合方式为1，1，1： 构造函数：1+r+r2 单独白球与单独黄球的组合方式分别为： 1,1和