递推关系定义.PPTVIP

第七讲　递推关系定义 7.1 递推关系的定义及建立 7.1 递推关系的定义及建立 7.1 递推关系的定义及建立 如何建立递推关系？举例说明如下： 7.1 递推关系的定义及建立 Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，集估计工作量。 7.1 递推关系的定义及建立 n=2时已给出算法；n=3时，第一步便利用算法把 上面两个盘移到B上，第二步再把第三个圆盘转移 到柱C上；最后把柱B上两个圆盘转移到柱C上。 N=4，5，…以此类推。 7.1 递推关系的定义及建立 假定n-1个盘子的转移算法已经确定。 7.1 递推关系的定义及建立 　　算法分析：令h(n)表示n个圆盘所需要的转移盘 次。根据算法先把前面n-1个盘子转移到B上；然后 把第n个盘子转到C上；最后再一次将B上的n-1个盘 子转移到C上。 n=2时，算法是对的，因此，n=3是算法是对的。 以此类推。于是有 7.1 递推关系的定义及建立 7.1 递推关系的定义及建立 7.1 递推关系的定义及建立 7.2 Fibonacci数列及性质 　　Fibonacci数列是递推关系的又一个典型问题， 数列的本身有着许多应用。 但 7.2 Fibonacci数列及性质 7.2 Fibonacci数列及性质 7.2 Fibonacci数列及性质 7.2 Fibonacci数列及性质 性质 1） 7.2 Fibonacci数列及性质 7.2 Fibonacci数列及性质 性质 2） 7.2 Fibonacci数列及性质 性质3） 7.2 Fibonacci数列及性质 性质4） 7.2 Fibonacci数列及性质 性质5） 7.2 Fibonacci数列及性质 性质6） 7.2 Fibonacci数列及性质 * * 　　递推关系是组合数学的一个重要课题,它不仅在几乎所有的数学分支中占有重要的地位,而且在计算机科学,特别是在算法分析中有着广泛的应用. 定义 设 是一个序列，把该序列中的 和 它前面的几个 关联起来的方程称为 一个递推关系。 如： 错排数 例. Hanoi问题：这是个组合数学中的著名问题。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。 算法： N=2时， 第一步先把最上面的一个圆盘套在B上                       第二步把下面的一个圆盘移到C上                       到此转移完毕 A B C 最后把B上的圆盘移到C上 对于一般n个圆盘的问题， 先把上面的n-1个圆盘经过C转移到B。 第二步把A下面一个圆盘移到C上 最后再把B上的n-1个圆盘经过A转移到C上 A B C 　　当然，利用递推关系上式也可以依次求得 ，这样的连锁反应关系， 叫做递推关系。 例 在一个平面上有一个圆和 条直线,这些直线中 条在圆内都同其他的直线相交.如果没有多 于三条的直线相交于一点,试问这 条直线将圆 的每一 分成多少个区域? 设这 条直线将圆分成的区域数为 ，如果有 条直线在圆内分成 个区域，那 么，再加入第 条直线 与在圆内的其他 条直线相交。显然， 条直线在圆内分成 条线段，而每 条 直线在圆内经过的区域分成两个区域。 第 条直线后，圆内就增加了 个区域． 这条直线被 线段又将第 这样，加入 而对于 显然有 。 可建立如下的递推关系： 7.1 递推关系的定义及建立 　例　在一个平面中,有 个圆两两相交,但任两个圆 任三个圆无公交点.求这 个圆把平面分成 由图易见 不相切, 多少个区域? 设 个圆将平面分成 个区域． 现假设前 个圆 个区域，当加入第 个圆时，由题 个圆相交于 个点，这 个点把第 个圆分成 个弧，而每条弧 个圆分成的区域分 成两个区域， 个圆使成的 区域数增加了 个。 将平面分成 设这个圆与前一个 正好将前面的 故新加入的第 因此可以建立如下的递推关系： 问题：有雌雄兔子一对，雌兔每月产雌雄各一的 一对新兔，从