第08单元_算法引论.pptVIP

6 7 5 1 3 2 4 下面的任务：用刚才介绍的方法，对 5 左、右两侧的两段数据，分别进行排序。 a 0 1 2 3 4 5 6 下标 × × × 1 3 2 4 a 0 1 2 3 4 5 6 下标 l r 6 7 × × × × × a 0 1 2 3 4 5 6 下标 l r 7 6 5 4 3 2 1 最后的结果： a 0 1 2 3 4 5 6 下标 作业题：快速排序的编程实现。 － END － 那么如何使用递归算法来解决一个实际的 问题呢？求阶乘的例子是非常简单的，递归形 式已知。对于一个真正的实际问题，它的递归 形式不是那么明显的，难以找到一种合适的递 归形式来实现它，需要很强的逻辑分析能力和 抽象的能力。 递归算法的类型 递归算法可以分为两种类型： 基于分治策略的递归算法； 基于回溯策略的递归算法。 8.5.2 基于分治策略的递归算法 分而治之（divide-and-conquer）的算法 设计思想： Divide：把问题划分为若干个子问题； Conquer：以同样的方式分别去处理各个子问题； Combine：把各个子问题的处理结果综合起来，形成最终的处理结果。 fact(3) fact(2) 调用 fact(1) 调用 …… 调用 调用 …… 调用 调用 …… 调用 调用 1. 指数运算 计算xn，其中n为一个非负整数 问题描述： 简单的方法：xn ＝ x * x * … * x (n个x相乘)， 因此可以采用一个循环语句来实现，算法的 时间复杂度为O(n)。 如何来设计相应的递归算法？ 由xn ＝ x * x * … * x， 可知xn ＝ x * xn-1，且x0 ＝1.0 这就是递归算法的递归形式和递归边界，据 此可以编写出相应的递归函数。 // 此函数返回x^n double power_2(double x, unsigned int n) { if(n == 0) return(1.0); return(x * power_2(x, n-1)); } 递归算法 x3 调用 x2 调用 x1 调用 x0 返回 返回 返回 此递归算法的时间复杂度是什么？ O(n) 能否设计出一种更好的递归算法，以降低 时间复杂度？ 递归算法的设计包括：递归形式和递归边界 递归边界：即x0 ＝1.0 递归形式： // 此函数返回x^n double power_3(double x, unsigned int n) { double semi; if(n == 0) return(1.0); semi = power_3(x, n / 2); // 计算xn/2或x(n-1)/2 if(n % 2 == 0) return(semi * semi); else return(semi * semi * x); } 新的递归算法 时间复杂度？ 相传在古印度的Bramah庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中遵守以下规则：每次只允许移动一只盘，且大盘不得落在小盘上。有人会觉得这很简单，但真的动手移盘就会发现，若每秒移动一只盘子，按照上述规则将64只盘子从一根柱子移至另一根柱子上，所需时间约为5800亿年 2. 汉诺(Hanoi)塔问题 应该用递归算法来解决。但怎么样寻找洋娃娃？怎么样寻找递归的形式？从思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。 A 1、在A柱上只有一只盘子，假定盘号为1，这时 只需将该盘从A搬至C，一次完成，记为： move from A to C B C 1 1 1 1 1 1 1 A 2、在A柱上有两个盘子，1为小盘，2为大盘 第 1 步将1号盘从A移至B, 这是为了让2号盘能移动 第 2 步将2号盘从A移至C； 第 3 步再将1号盘从B移至C； 这三步记为： move from A to B； move from A to C； move from B to C； B C 2 1 1 2 1 3、在A柱上有三个盘子, 从小到大分别为1号, 2号, 3号 第 1 步将1号盘和2号盘从A移至B, 使3号盘能移动 第 2 步将3号盘从A移至