分冶策略(生成PDF)

《分冶策略(生成PDF)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分冶策略（生成PDF）分治策略（DivideandConquer）一、算法思想任何一个川以用计算机求解的问题所需的计算时间都与其规模有关。问题规模越小，解.题所需的计算时间往往也越少，从而也越容易计算。想解决一个较人的问题，有时是相当困难的。分治法的思想就是，将一个难以直接解决的人问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分而治Z方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：1）把它分成两个或多个更小的问题；2）分别解决每个小问题；3）把各小问题的解答组合起來，即可

2、得到原问题的解答。小问题通常与原问题相似，可以递归地使川分而治Z策略來解决。1、解决算法实现的同时，需要估算算法实现所需时间。分治算法时间是这样确定的：解决子问题所需的工作总量（由子问题的个数、解决每个子问题的工作量决定）合并所有了问题所需的工作量。2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法3、分治的具体过程：begin｛开始｝if①问题不可分then②返回问题解elsebegin③从原问题中划出含一半运算对象的子问题1;④递归调用分治法过程，求出解1;⑤从原问题中划出含另一半运算对

3、•象的子问题2；⑥递归调用分治法过程，求出解2；⑦将解1、解2组介成整修问题的解；end;end;｛结束｝二、分治策略的应用（1）找出伪币-1-给你一个装有16个硬币的袋子。16个硬币中有一•个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。［问题简析］为了帮助你完成这一任务，将提供一台可用來比较两组硬币巫量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硕币1与硕币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硕币2比硬币1轻，则硕币2是伪造的。这样就

4、完成了任务。假如两駛币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硕币重量相等，则继续比较硕币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。另外-•种方法就是利用分而治Z方法。假如把16硬币的例子看成一个犬的问题。第一步，把这一问题分成两个小问题。随机选择8个硕币作为第一组称为A组，剩下的8个硕币作为第二纽称为B纽。这样，就把16个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬

5、币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并口•可以判断它位于较轻的那一组硕币中。最后，在第三步中，用第二步的结果得出原先16个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组述是B纽中有伪币，都可以推断这16个硬币中存在伪币。因此，仅仅通过一次重量的比较，就对以判断伪币是否存在。现在假设需要识别出这一伪币。把两个或三个硬币的情况作为不口J再分的小问题。注童如果只有一个硕币，那么不能判断出它是否就是伪币。在一•个小问题屮，通过

6、将一个硕币分别与其他两个驶币比较，最多比较两次就可以找到伪币。这样，16硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，对以判断伪币是否存在。如果没冇伪币，则算法终止。否则，继续划分这两组破币來寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。称其中一组为B1,另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个驶币，称其中一组为Bb,另一组为Bib。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，

7、因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。（2）二分搜索（折半查找）算法思想：将数列按有序化（递增或递减）排列，查找过程中采川跳跃式方式查找，即先以有序数列-2-的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。折半杳找是--种高效的查找方法。它可以明显减少比较次数，提高杳找效率。但是，折半查找的先决条件是查找表中的数据元素必须冇序。算法步骤描述：stepl首先确定

8、整个查找区间的中间位置：mid=（left+right）/2step2用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功若大于，则在后（右）半个区域继续进行折半查找若小于，则在前（左）半个区域继续进行折半查找Step3对确疋的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功，要么查找失败。折半查找的存储结构采用-•维数组存放。折半查找算法举例对给定数列（有序）｛3,5,11,17,21,23,28,30,32,50）,按折半杳