组合2母函数递推关系.ppt

组合数学帅天平北京邮电大学数学系Email:******@1TPSHUAI第二章:递推关系与母函数1,递推关系引入,i数列2,常系数递推关系求解3,母函数及其性质4,用母函数求解递推关系5,母函数的应用-整数剖分6指数型母函数及其应用7,非线性递推关系举例---引入1利用递推关系进行计数的方法在算法分析中经常用到。,MathematicsfortheanalysisofalgorithmsBirkhauser,Boston1st,1981;3rd,。3TPSHUAI例1,Hanoi问题:这是组合数学中的一个著名问题。N个圆盘依其半径大小,从下而上套在A柱上,如下图示。每次只允许取一个移到柱B或C上,而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上,请设计一种方法并估计要移动几个盘次。现在只有A、B、C三根柱子可用。-引入2ABC4TPSHUAIHanoi问题是个典型的组合问题,第一步要设计算法,进而估计它的复杂性,及估计工作量。-引入3算法:N=2时第一步先把最上面的一个圆盘套在B上第二步把下面的一个圆盘移到C上最后把B上的圆盘移到C上到此转移完毕5TPSHUAI对于一般n个圆盘的问题,假定n-1个盘子的转移算法已经确定。先把上面的n-1个圆盘经过C转移到B。第二步把A下面一个圆盘移到C上最后再把B上的n--引入46TPSHUAI上述算法是递归的运用。n=2时已给出算法;n=3时,第一步便利用算法把上面两个盘移到B上,第二步再把第三个圆盘转移到柱C上;最后把柱B上两个圆盘转移到柱C上。N=4,5,…以此类推。-引入57TPSHUAI算法分析:令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上;然后把第n个盘子转到C上;最后再一次将B上的n-1个盘子转移到C上。n=2时,算法是对的,因此,n=3是算法是对的。以此类推。-引入6算法复杂度为:利用递推关系(a)式也可以依次求得h(1),h(2),h(3)…,这样的连锁反应关系,叫做递推关系。i数列是递推关系的又一个典型问题,该数列的本身有着许多应用。问题:有雌雄兔子一对,假定过两月后每月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子?设满n个月时兔子对数为Fn其中当月新生兔数目设为Nn对。第n-1个月留下的兔子数目设为On对。-i数列19TPSHUAI但即第n-(1)-i数列210TPSHUAI