数据结构课件1-11全书讲第11讲算法设计与分析幻灯片.pptVIP

第11讲 算法设计与分析 算法设计 通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性、可靠性、简单性和易理解性。其次是算法所需要的存储空间少和执行更快等因素。 递归算法 一个直接或间接地调用自身的算法称为递归算法，一个直接或间接地调用自身的函数称为递归函数。 在算法设计中，使用递归技术往往能使函数的定义和算法的描述简捷并且便于理解。 一般递归具有如下的形式： if (递归结束条件) { /*递归结束条件成立，结束递归调用 */ 递归结束部分; } else { /*递归结束条件不成立，继续进行递归调用 */ 递归调用部分; } 或 if (递归调用条件) { /* 递归调用条件成立，继续进行递归调用 */ 递归调用部分; } [else { /* 递归调用条件不成立，结束递归调用 */ 递归结束部分; }] 例：用递归求阶乘n!。 阶乘可用迭代表示如下： int Factorial(int n) // 操作结果: 用递归求阶乘n! { if (n 0) { // 递归条件成立 return n * Factorial( n - 1); // 递归调用 } else { // 递归条件不成立 return 1; // 递归结束 } } 例：Fibonacci数列递归算法。 无究数列：0, 1, 1, 2, 3, 5, 8, 13, …，称为Fibonacci数列，可以迭代定义为： int Fibonacci(int n) // 操作结果: 返回Fibonacci数列的第n项 { if (n == 0) { // 递归结束条件成立 return 0; // 终止递归调用 } else if (n == 1) { // 递归结束条件成立 return 1; // 终止递归调用 } else { // 递归结束条件不成立 return Fibonacci(n - 1) + Fibonacci(n - 2); // 递归调用 } } 分治算法 分治算法与软件设计的模块化方法类似。为了解决一个大的问题，将一个规模为n的问题分解为规模较小的子问题，这些子问题互相独立并且和原问题相同。分别解这些子问题，最后将将各个子问题的解合并得到原问题的解。 子问题通常与原问题相似，可以递归地使用分治策略来解决。 。 例：Hanoi塔问题 传说在古代印度的贝拿勒圣庙里，安装着三根插至黄铜板上的宝石针，印度主神梵天在其中一根针上从下到上由大到小的顺序放64片金圆盘，称为梵塔，然后要僧侣轮流值班把这些金圆盘移到另一根针上，移动时必须遵守如下规则： （1）每次只能移动一个盘片； （2）任何时候大盘片不能压在小盘片之上； （3）盘片只允许套在三根针中的某一根上。 这位印度主神号称如果这64片盘全部移到另一根针上时，世界在一声霹雳中毁灭，Hanoi塔问题又称“世界末日”问题。下图为3阶Hanoi塔的初始情况。 于n阶Hanoi塔问题Hanoi(n, a, b, c)，当n=0时，没盘子可供移动，什么也不做；当n=1时，可直接将1号盘子从a轴移动到c轴上；当n=2时，可先将2号盘子移动到b轴，再将1号盘子移动到c轴，最后将2号盘子移动到c轴；对于一般n0的一般情况可采用如下分治策略进行移动 （1）将1至n-1号盘从 a 轴移动至 b 轴，可递归求解Hanoi(n-1, a, c, b)； （2）将 n号盘从 a 轴移动至 c 轴； （3）将1至n-1号盘从b轴移动至c轴，可递归求解 Hanoi(n-1, b, a, c)。 void Hanoi(int n,char a,char b,char c) // 操作结果: 将a塔座上的直径由小到大,至上而下编辑为 // 1至n的n个盘子按规则移到塔座c上，塔座b可用作 // 辅助塔座 { if (n 0) { // 递归条件成立 Hanoi(n - 1, a, c, b); // 将a塔座上编号为1至 // n-1的圆盘移到b塔座，c作辅助塔座 cout 编号为 n 的盘子从 a 塔座移到 c 塔座 endl; // 将编号为n的圆盘从a塔座移到c塔座 Hanoi(n - 1, b, a, c); // 将b塔座上编号为1至 // n-1的圆盘移到c塔座，a作辅助塔座 } } 算法分析 递归函数包含递归结束