递归算法1.pptx

程序设计导论;内容;什么是递归？;递归的概念;递归;递归及其实现;递推实现n!;递归算法求n!;与或图;如果有多于 2 种取值，可用下图：;2、与结点; A 为或结点；B 为直接可解结点，值为1； C 为与结点，当 n1 时，A 的取值即 C 的值，而 C 的值即 E 的值，为了求得 E 的值，需要先求出 D 的值。D 值 fact( n-1 ) 乘以 n 即为 E 的值。;与结点可能有多个相关联的点，这时可描述为下图; 下面我们以 3！为例来画与或结点图，目的是体会 递归的含义。;下面画出了调用和返回的递归示意图;分析上图;①;递归 vs. 数学归纳法;递归 vs. 数学归纳法（2）;递归与递推;;汉诺（Hanoi）塔问题;解题思路;在 A 柱上有二只盘子，1 为小盘，2 为大盘。 第（1）步将1号盘从A移至B，这是为了让 2号盘能移动； 第（2）步将 2 号盘从A 移至 C； 第（3）步再将 1 号盘从 B 移至 C； 这三步记为（演示）：;在A柱上有3只盘子，从小到大分别为1号，2号，3号 第（1）步 将1号盘和2号盘视为一个整体；先将二者作为整体从A移至B，给3号盘创造能够一次移至C的机会。这一步记为 move( 2, A, C, B) 意思是将上面的2只盘子作为整体从A借助C移至B。 第（2）步 将3号盘从A移至C，一次到位。记为 move 3 from A to C 第（3）步 处于B上的作为一个整体的2只盘子，再移至C。这一步记为 move( 2, B, A, C) 意思是将2只盘子作为整体从B借助A移至C。;move (3, A, B, C);move (3, A, B, C); 4、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将1号和2号盘当整体从A移至B的过程中 move(2, A, C, B) 实际上是分解为以下三步 第（1）步：move 1 form A to C; 第（2）步：move 2 form A to B; 第（3）步：move 1 form C to B;; 经过以上步骤，将 1 号和 2 号盘作为整体从 A 移至 B，为 3 号盘从 A 移至 C 创造了条件。同样，3号盘一旦到了 C，就要考虑如何实现将 1 号和 2 号盘当整体从 B 移至 C 的过程了。实际上 move( 2, B, A, C ) 也要分解为三步： 第（1）步：move 1 form B to A; 第（2）步：move 2 form B to C; 第（3）步：move 1 form A to C;; 5、看 move(2, A, C, B) 是说要将 2 只盘子从 A 搬至 B，但没有 C 是不行的，因为第（1）.1步就要将 1 盘从 A 移到 C，给 2 盘创造条件从 A 移至 B，然后再把 1 盘从 C 移至 B。看到这里就能明白借助 C 的含义了。因此，在构思搬移过程的参量时，要把 3 个柱子都用上。; 6、定义搬移函数 move(n, A, B, C)，物理意义是将 n 只盘子从 A 经 B 搬到 C;这里用与结点的含义是分解为(1)(2)(3)步。这3步是相关的，相互依存的，而且是有序的，从左至右执行。 move(n, A, B, C) 分解为3步 move(n-1, A, C, B)理解为将上面的n-1只盘子作为一个整体从A经C移至B； 输出n：A to C，理解将n号盘从A移至C，是直接可解结点； Move(n-1, B, A, C)理解为将上面的n-1只盘子作为一个整体从B经A移至C。 ;这里显然是一种递归定义，当着解 move(n-1, A, C, B)时又可想到，将其分解为 3 步： 第1步：将上面的n-2只盘子作为一个整体从A经B到C，move(n-2, A, B, C)； 第2步：第n-1号盘子从A直接移至B，即n-1:A to B； 第3步：再将上面的n-2只盘子作为一个整体从C经A移至B，move(n-2, C, A, B)； 下面，我们还是以3只盘子为例画出递归的与或图。; 这个图很象一颗倒置着的树，结点move(3, A, B, C)是树根，与结点是树的分枝，叶子都是直接可解结点。;// ******************************************* // * 程 序：6_hanoi2002.cpp * // * 作 者：wuwh * // * 编制时间：2002年10月13日