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

组合数学

Email:

帅天平

北京邮电大学数学系

第二章:递推关系与母函数

01020304

1,递推关系引入，2,常系数递推关3,母函数及其性4,用母函数求解

Fibonacci数列系求解质递推关系

050607

5,母函数的应用6指数型母函数7,非线性递推关

-整数剖分及其应用系举例--几类特

殊组合数

2.1递推关系-引入1

Mathematicsfortheanalysisof

algorithms

Birkhauser,Boston1st,1981;

and,

3rd,1999.

○中对递推关系及其应用有更广

泛的叙述。

○利用递推关系进行计数的方法

在算法分析中经常用到。

2.1递推关系-引入2

ABC

例1,Hanoi问题：这是组合数学中的一个著名问

题。N个圆盘依其半径大小，从下而上套在A柱上，

如下图示。每次只允许取一个移到柱B或C上，而

且不允许大盘放在小盘上方。若要求把柱A上的n

个盘移到C柱上,请设计一种方法并估计要移动几

个盘次。现在只有A、B、C三根柱子可用。

2.1递推关系-引入3

Hanoi问题是个典型的组合问题,第一步要设

计

算法，进而估计它的复杂性，及估计工作量。

N=2时算法：

第第一二步步先把把下最面上的面一的个一圆个盘圆移盘到套上在上

zz最后把B上的圆盘移到C上CB

到此转移完毕

ABC

2.1递推关系-引入4

l假定n-1个盘子的转移算法已经确定。

对于一般n个圆盘的问题，

先把上面的n-1个圆盘经过C转移到B。

第二步把A下面一个圆盘移到C上

最后再把B上的n-1个圆盘经过A转移到C上





ABC

2.1递推关系-引入5

上述算法是递归的运用。n=2时已给出

算法；n=3时，第一步便利用算法把上

面两个盘移到B上，第二步再把第三个

圆盘转移到柱C上；最后把柱B上两个

圆盘转移到柱C上。N=4，5，…以此

类推。

2.1