[工学]02算法分析与设计.pptVIP

分治法（ Divide-and-conquer ） 引例：称硬币 引例：称硬币 常规的解决方法是先将这些硬币分成两枚一组，每一次只能称一组硬币。如果运气好的话，只要称一次就可以找到，运气坏的话，最多要称8次才能找出那枚硬币。 引例：称硬币 这种直接寻找的方法存在着相当大的投机性，只适用于硬币数量较少的情形。在硬币数量较多的情况下，就成为一件费时费力又需要运气的事了。 引例：称硬币 试着改变一下方法：如果我们将全部硬币分成两组，将原来设计的一次比较两枚硬币变以为一次比较两组硬币，我们会发现，通过一次比较之后，完全可以舍弃全部是真币的一组硬币，选取与原有问题一致的另一半进行下一步的比较。 这样，问题的规模就明显缩小，而且每一次比较的规模都成倍减少。 引例：称硬币 根据以上分析，我们可以得出以下的结论： 参与比较的硬币数量越多，使用该方法来实现就越快，而且投机性大大减少； 解决方法的关键在于能将大问题分割成若干个小问题； 小问题与原问题是完全类似的（与递归？）。 分治法 通常，我们将这种大化小的设计策略和思想称为“分治法”，即“分而治之”的意思。 分治法的特点： 大问题可以化为若干个小问题来解决 每个小问题的出现与大问题情况相同 所以，与递归方法相同，分治算法往往用递归方法来实现，其步骤如下： 分解：将问题分解为若干小问题，相互独立； 解决：求解小问题； 合并：将子问题的解合并为原问题的解。 采用分治策略的动因、原理 动机：某些问题，当规模较小时，运用某个算法很容易解决，但当规模较大时还运用该算法就会超时或不易解决。这时，我们用分治策略。 原理：某些问题可以将一个大规模问题划分为若干小规模问题，且小规模问题的解很容易（一般合并算法顶多O(n)）转化为大规模问题的解。 分治法的应用 分治法在检索、分类算法或某些速算算法中很有效，最常用的分治法是二分法、归并法、快速排序法等。 分治法的适用条件 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 Sentinel监视哨 在数组、线性表、序列的一端插入1个在数组（或序列）中不出现的特殊数字、字符，从而减少控制变量的比较次数，达到提高效率的目的。这个特殊数字（字符）称为监视哨 数学归纳法. 离散数学里广泛应用且强有力的证明方法 用来证明对所有整数k≥0均成立的定理: 基础步: 证明对n = n0成立; 归纳假设: 假设对任意 n成立； 归纳歩: 证明对n+1成立。 例证明: 0 + 1+ 2+3 + … + n = n(n + 1)/2 （ n≥0） 证明: (数学归纳法) 基础步 (n=0) 0 = 0(0+1)/2 归纳假设: 假设 0 + 1 + 2 + … + n = n(n+1) / 2 归纳歩: 0 + 1 + 2 + … + n + n + 1= n(n+1) / 2 + n + 1 = (n+1)(n+2)/2 快速排序 快速排序思想-分治 划分子程序Partitioning subroutine 划分实例 快速排序分析 最坏情况 最坏情况递归树 对等划分 最好情况分析 递归树 快速排序 VS. 归并排序 哪种算法更好? 测试环境: IBM370/158 编程语言 PL/1 输入为 (0, 10000)内的随机整数 Quicksort平均时间分析 Quicksort平均时间分析 Quicksort平均时间分析 随机划分 随机快速排序算法 剔除多余括号 【问题描述】 输入一个含有括号的四则运算表达式，可能含有多余的括号。编程整理该表达式，去掉所有多余的括号，要求原表达式中所有变量和运算符的相对位置保持不变，并保持与原表达式等价。 注意： 输入a+b时，不能输出b+a； 表达式以字符串形式输入，长度不超过255。对输入无需判错； 所有的变量为单个小写字母，只是要求去掉所有多余的括号，不要求对表达式化简。 【输入】 原表达式 【输出】 经过处理的表达式。 【样例输入】 (a * b) + c / da * b + c / d 【样例输出】 a * b + c / da * b + c/d 分析 此题应如何求解？有无较为基本的解法？ 四则运算表达式含