计算机算法设计与分析基础(第四章分治法).pptVIP

主要内容： 4.1 合并排序 4.2 快速排序 4.3 折半排序 4.4 二叉树遍历及其相关特性 4.5 大整数乘法和矩阵相乘 4.6 解最近对问题与凸包问题 简介 对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 分治法的基本思想 将规模为N的问题分解为k个规模较小的子问题,使这些子问题相互独立可分别求解,再将k个子问题的解合并成原问题的解.如子问题的规模仍很大,则反复分解直到问题小到可直接求解为止。 在分治法中,子问题的解法通常与原问题相同,自然导致递归过程。 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 如果原问题可分割成k个子问题，1k≤n ，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 问题1：找出伪币 给你一个装有1 6枚硬币的袋子。1 6枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。 为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。 方法1 任意取1枚硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币。最多可能有15次比较。 方法2 将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。最多可能有8次比较。 方法3 分析 上述三种方法,分别需要比较15次,8次,4次,那么形成比较次数差异的根本原因在哪里? 方法1:每枚硬币都至少进行了一次比较,而有一枚硬币进行了15次比较 方法2:每一枚硬币只进行了一次比较 方法3:将硬币分为两组后一次比较可以将硬币的范围缩小到了原来的一半,这样充分地利用了只有1枚伪币的基本性质。 问题2：金块问题 有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。 方法1 假设袋中有n 个金块。可以用函数M a x通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。 算法如下： max:=a[1];min:=a[1]; for i:=2 to n do {2n-2次比较} begin if a[i]max then max:=a[i]; if a[i]min then min:=a[i]; end ; 可对上述改进少1次 max:=a[1]; for i:=2 to n do {n-1次比较，从n个元素中找到最大的} if a[i]max then begin max:=a[i]; j:=i end; for i:=j+1 to n do a[i-1]:=a[i]; {去掉最大的数a[j]} min:=a[1]; for i:=2 to n-1 do {n-2次比较，从剩下的元素中找最小的} if a[i]max then min:=a[i]; 找金块的示例图 方法2： n≤2，识别出最重和最轻的金块，一次比较就足够了。 n＞2，第一步，把这