组合数学——母函数与递推关系.ppt

第二章—递推关系与母函数主讲教师数学学院魏毅强教授联系电话 ********** Email : ******@tyut. Yiqiang Wei < ******@tyut.> 目录 递推关系与母函数 母函数 —递推关系与母函数 Yiqiang Wei < ******@tyut.> 利用递推关系进行计数是最重要的一种组合计数方法,该方法在算法分析中经常用到,举例说明如下: 例1 (Hanoi 塔问题):这是个组合数学中的著名问题。 N个圆盘依其半径大小,从下而上套在 A柱上, 如下图示。每次只允许取一个移到柱 B或C上,而且不允许大盘放在小盘上方。若要求把柱 A上的 n个盘移到 C柱上请设计一种方法来,并估计要移动几个盘次。现在只有 A、B、C三根柱子可用。 递推关系与母函数 引例 Yiqiang Wei < ******@tyut.> 递推关系与母函数 A B C ?? Hanoi 问题是个典型的问题,第一步要设计算法, 进而估计它的复杂性,即估计工作量。 Yiqiang Wei < ******@tyut.> n=2 时的算法: z第一步先把最上面的一个圆盘套在 B上 z第二步把下面的一个圆盘移到 C上 z最后把 B上的圆盘移到 C上到此转移完毕 A B C 递推关系与母函数 Yiqiang Wei < ******@tyut.> 递推关系与母函数?假定 n-1 个盘子的转移算法已经确定。 z对于一般 n个圆盘的问题, z先把上面的 n-1 个圆盘经过 C转移到 B。 z第二步把 A下面一个圆盘移到 C上 z最后再把 B上的 n-1 个圆盘经过 A转移到 C上??????A B C Yiqiang Wei < ******@tyut.> 递推关系与母函数上述算法是递归的运用。 n=2 时已给出算法; n=3 时,第一步便利用算法把上面两个盘移到 B上, 第二步再把第三个圆盘转移到柱 C上;最后把柱 B 上两个圆盘转移到柱 C上。 n=4 ,5,…以此类推。 Yiqiang Wei < ******@tyut.> ?算法分析:令 h(n )表示 n个圆盘所需要的转移盘次。根据算法先把前面 n-1 个盘子转移到 B上; 然后把第 n个盘子转到 C上;最后再一次将 B上的 n-1 个盘子转移到 C上。 1)1( )(2n,1)1(2)(?????h nhnh 递推关系与母函数 Yiqiang Wei < ******@tyut.> 递推关系与母函数 1)1(?h12121)1(2)2( 2??????hh121 1)- 2(2 1)2(2)3( 3 2??????hh是关系式() 的初始条件, 于是,由() 依次可得 1211)- 2(2 1)3(2)4( 4 3??????hh故,由数学归纳发可得(证明略) 1n1,-2)(?? nnh