第5章 减治法

《第5章 减治法》由会员分享，可在线阅读，更多相关《第5章 减治法（43页珍藏版）》请在装配图网上搜索。

1、算法设计与分析算法设计与分析清华大学出版社清华大学出版社第第5章章 减治法减治法 5.1 减治法的设计思想减治法的设计思想 5.2 查找问题中的减治法查找问题中的减治法5.3 排序问题中的减治法排序问题中的减治法5.4 组合问题中的减治法组合问题中的减治法算法设计与分析算法设计与分析清华大学出版社清华大学出版社5.1 减治法的设计思想减治法的设计思想 规规模模为为n的的原原问问题题的的解解与与较较小小规规模模（通通常常是是n/2）的子问题的解之间具有关系：的子问题的解之间具有关系：（1）原原问问题题的的解解只只存存在在于于其其中中一一个个较较小小规规模模的的子子问题中；问题中；（2）原原问问题

2、题的的解解与与其其中中一一个个较较小小规规模模的的解解之之间间存存在某种对应关系。在某种对应关系。由于原问题的解与较小规模的子问题的解之由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。规模的子问题就可以得到原问题的解。算法设计与分析算法设计与分析清华大学出版社清华大学出版社 子问题子问题 的规模是的规模是n/2 子问题的解子问题的解 原问题的解原问题的解 原问题原问题 的规模是的规模是n减治法的设计思想减治法的设计思想算法设计与分析算法设计与分析清华大学出版社清华大学出版社例：计算例：计

3、算an的值，的值，应用减治技术得到如下计算方法：应用减治技术得到如下计算方法：应用分治法得到应用分治法得到an的计算方法是：的计算方法是：O(log2n)O(nlog2n)=-且是奇数且是奇数且是偶数且是偶数1)(1)(122)1(22naananaannn算法设计与分析算法设计与分析清华大学出版社清华大学出版社 所以，通常来说，应用减治法处理问题的效率所以，通常来说，应用减治法处理问题的效率是很高的，一般是是很高的，一般是O(log2n)数量级。数量级。减治法只对一个子问题求解，并且不需要进行减治法只对一个子问题求解，并且不需要进行解的合并。应用减治法（例如减半法）得到的算法解的合并。应用减

4、治法（例如减半法）得到的算法通常具有如下递推式：通常具有如下递推式：算法设计与分析算法设计与分析清华大学出版社清华大学出版社5.2 查找问题中的减治法查找问题中的减治法 5.2.1 折半查找折半查找 5.2.2 二叉查找树二叉查找树算法设计与分析算法设计与分析清华大学出版社清华大学出版社基本思想：在有序表中，取中间记录作为比较对象，若给基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于

5、中间记录的关键码，则在中间记录的右半区若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。的区域无记录，查找失败。5.2.1 折半查找折半查找 r1 rmid-1 rmid rmid+1 rn （mid=(1+n)/2）如果如果krmid查找这里查找这里 k算法设计与分析算法设计与分析清华大学出版社清华大学出版社例：查找值为例：查找值为14的记录的过程：的记录的过程：0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35

6、 38 42 46 49 52low=1high=13mid=7 high=6 mid=3 high=2 mid=1 31141814714low=2mid=2 14=14算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法5.1折半查找折半查找 1.low=1；high=n；/设置初始查找区间设置初始查找区间 2.测试查找区间测试查找区间low，high是否存在，若不存在，则查找失败；是否存在，若不存在，则查找失败；否则否则 3.取中间点取中间点mid=(low+high)/2;比较比较k与与rmid，有以下三种情况：有以下三种情况：3.1 若若krmid，则，则low=mid+

7、1；查找在右半区进行，转查找在右半区进行，转2；3.3 若若k=rmid，则查找成功，返回记录在表中位置则查找成功，返回记录在表中位置mid；算法设计与分析算法设计与分析清华大学出版社清华大学出版社判定树判定树描述折半查找的判定过程。描述折半查找的判定过程。长度为长度为n的判定树的构造方法为：的判定树的构造方法为：（1）当）当n=0时，判定树为空；时，判定树为空；（2）当）当n0时，判定树的根结点是有序表中序号时，判定树的根结点是有序表中序号为为mid=(n+1)/2的记录，根结点的左子树是与有序的记录，根结点的左子树是与有序表表r1 rmid-1相对应的判定树，根结点的右子相对应的判定树，根

8、结点的右子树是与树是与rmid+1 rn相对应的判定树。相对应的判定树。算法设计与分析算法设计与分析清华大学出版社清华大学出版社具有具有11个结点的判定树个结点的判定树6312548111079 在表中查找任一记录的过程，即是判定树中从根结点到在表中查找任一记录的过程，即是判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。具有树中的层数。具有n个结点的判定数的深度为个结点的判定数的深度为 。算法设计与分析算法设计与分析清华大学出版社清华大学出版社5.2.2 二叉查找树二叉查找树 由由二二叉叉排排序序树树的的定定

9、义义，在在二二叉叉排排序序树树root中中查查找找给给定定值值k的过程是：的过程是：若若root是空树，则查找失败；是空树，则查找失败；若若k根结点的值，则查找成功；根结点的值，则查找成功；否则，若否则，若k根结点的值，则在根结点的值，则在root的左子树上查找；的左子树上查找；否则，在否则，在root的右子树上查找；的右子树上查找；上述过程一直持续到上述过程一直持续到k被找到或者待查找的子树为空，被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。如果待查找的子树为空，则查找失败。v二叉排序树的查找效率就在于只需要查找两个子树之一。二叉排序树的查找效率就在于只需要查找两个子树之一。

10、算法设计与分析算法设计与分析清华大学出版社清华大学出版社(a)按按63,90,55,58,70,42,10,45,83,67 (b)按按55,42,10,70,63,58,83,67,90,45 的顺序构造的二叉排序树的顺序构造的二叉排序树 的顺序构造的二叉排序树的顺序构造的二叉排序树5842709063455583671010836370554542675890算法设计与分析算法设计与分析清华大学出版社清华大学出版社二叉排序树的结点结构为：二叉排序树的结点结构为：struct BiNode int data;/结点的值，假设查找集合的元素为整型结点的值，假设查找集合的元素为整型 BiNode

11、*lchild,*rchild;/指向左、右子树的指针指向左、右子树的指针;算法算法5.2二叉排序树的查找二叉排序树的查找 BiNode*SearchBST(BiNode*root,int k)if(root=NULL)return NULL；else if(root-data=k)return root;else if(kdata)return SearchBST(root-lchild,k);else return SearchBST(root-rchild,k);算法设计与分析算法设计与分析清华大学出版社清华大学出版社 在二叉排序树上查找关键码等于给定值的结点的过程，在二叉排序树上查找关

12、键码等于给定值的结点的过程，恰好走了一条从根结点到该结点的路径，和给定值的比较恰好走了一条从根结点到该结点的路径，和给定值的比较次数等于给定值的结点在二叉排序树中的层数，比较次数次数等于给定值的结点在二叉排序树中的层数，比较次数最少为最少为1次（即整个二叉排序树的根结点就是待查结点），次（即整个二叉排序树的根结点就是待查结点），最多不超过树的深度。具有最多不超过树的深度。具有n个结点的二叉树的深度至少是个结点的二叉树的深度至少是 ，至多是，至多是n，所以，二叉排序树的查找性能在所以，二叉排序树的查找性能在O(log2n)和和O(n)之间。之间。算法设计与分析算法设计与分析清华大学出版社清华大学

13、出版社5.3 排序问题中的减治法排序问题中的减治法 5.3.1 堆排序堆排序 5.3.2 选择问题选择问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社5.3.1 堆排序堆排序 以以结结点点的的编编号号作作为为下下标标，将将堆堆用用顺顺序序存存储储结结构构（即即数数组组）来存储，则堆对应于一组序列。来存储，则堆对应于一组序列。(a)大根堆及其对应的序列大根堆及其对应的序列(b)小根堆及其对应的序列小根堆及其对应的序列47 35 26 20 18 7 13 107 10 13 18 35 26 47 20473526131820710261013473518720算法设计与分析算法设计

14、与分析清华大学出版社清华大学出版社 堆排序的基本思想是：首先将待排序的记录序列构造成堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。记录，以此类推，直到堆中只有一个记录为止。r1 r2 ri ri+1 rn-1 rn 无序区 有序区 为一个堆 已

15、经位于最终位置 堆顶和堆中最后一个记录交换算法设计与分析算法设计与分析清华大学出版社清华大学出版社堆调整问题：将一个无序序列调整为堆（1）筛选法调整堆 关键问题：完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？(a)28与与35交换交换(b)28与与32交换交换(c)将将28筛到叶子筛到叶子283218201218201235321820123535283228算法设计与分析算法设计与分析清华大学出版社清华大学出版社 假设当前要筛选结点的编号为k，堆中最后一个结点的编号为n，并且结点k的左右子树均是堆（即rk+1 rn满足堆的条件），则筛选算法用伪代码可描述为

16、：算法5.3筛选法调整堆 1.设置i和j，分别指向当前要筛选的结点和要筛选结点的左孩子；2.若结点i已是叶子，则筛选完毕；否则，比较要筛选结点的左右 孩子结点，并将j指向关键码较大的结点；3.将要筛选结点i的关键码与结点j的关键码进行比较，有以下两种情况：3.1 如果结点i的关键码大，则完全二叉树已经是堆；3.2 否则将ri与rj交换；令i=j，转步骤2继续进行筛选；时间性能是O(log2n)。算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法5.4筛选法调整堆筛选法调整堆 void SiftHeap(int r,int k,int n)i=k;j=2*i;/置置i为要筛的结点，

17、为要筛的结点，j为为i的左孩子的左孩子 while(j=n)/筛选还没有进行到叶子筛选还没有进行到叶子 if(jn&rjrj)/根结点已经大于左右孩子中的较大者根结点已经大于左右孩子中的较大者 break;else rirj;/将根结点与结点将根结点与结点j交换交换 i=j;j=2*i;/被筛结点位于原来结点被筛结点位于原来结点j的位置的位置 算法设计与分析算法设计与分析清华大学出版社清华大学出版社321820124035828203218201240820352818201240820352832(a)35与与28交交换换 (b)35与与32交交换换 (c)3540调调整整完完毕毕（2）插入

18、法调整堆关键问题是：在堆中插入一个结点，如何调整被插入结点，使整个完全二叉树仍然是一个堆？算法设计与分析算法设计与分析清华大学出版社清华大学出版社 假设当前堆中有k个结点，则要插入结点的编号为k+1，插入法调整堆的算法如下：算法算法5.5插入法调整堆插入法调整堆 1.设设i指向当前要插入的结点；指向当前要插入的结点；2.若结点若结点i是整个堆的根结点，则调整完毕；是整个堆的根结点，则调整完毕；3否则，设否则，设j指向结点指向结点i的双亲结点；将结点的双亲结点；将结点i与结点与结点j进行比较；进行比较；3.1 如果结点如果结点i的关键码小，则完全二叉树已经是堆，调整完毕；的关键码小，则完全二叉树

19、已经是堆，调整完毕；3.2 否则将否则将ri与与rj交换；令交换；令i=j，转步骤转步骤2继续进行调整；继续进行调整；时间复杂性为O(log2n)。算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法5.6插入法调整堆插入法调整堆 void InsertHeap(int r,int k)/堆中有堆中有k个结点，现插入一个新结点个结点，现插入一个新结点k+1 i=k+1;/置置i为要插入的结点为要插入的结点 while(i!=1)j=i/2;/j为为i的双亲结点的双亲结点 if(rirj)/待插入结点已小于根结点，调整结束待插入结点已小于根结点，调整结束 break;else rir

20、j;/将根结点与结点将根结点与结点j交换交换 i=j;/待插入点位于原来结点待插入点位于原来结点j的位置的位置 算法设计与分析算法设计与分析清华大学出版社清华大学出版社设无序序列设无序序列 T=(r1,r2,rn)，T 的第的第k（1kn）小元素定义为小元素定义为T按升序排列后在第按升序排列后在第k个位置上的元素。个位置上的元素。给定一个序列给定一个序列T和一个整数和一个整数k，寻找，寻找 T 的第的第k小元素小元素的问题称为的问题称为选择问题选择问题。特别地，将寻找第。特别地，将寻找第n/2小元小元素的问题称为素的问题称为中值问题中值问题。5.3.2 选择问题选择问题算法设计与分析算法设计与

21、分析清华大学出版社清华大学出版社（1）若）若k=s，则，则rs就是第就是第k小元素；小元素；（2）若）若ks，则第则第k小元素一定在序列小元素一定在序列rs+1 rj中；中；ri rk rs-1 rs rs+1 rj 均均rs 轴值轴值 均均rs ri rs-1 rs rs+1 rk rj 均均rs 轴值轴值 均均rs(a)若若ks，则则rk在在右右半半区区 考虑快速排序中的划分过程，一般情况下，设待划分考虑快速排序中的划分过程，一般情况下，设待划分的序列为的序列为ri rj，选定一个轴值将序列，选定一个轴值将序列ri rj进行划分，使进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元

22、素都得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是位于轴值的右侧，假定轴值的最终位置是s，则：，则：算法设计与分析算法设计与分析清华大学出版社清华大学出版社选择问题的例子选择问题的例子:5 3 8 1 4 6 9 2 7 选择问题的查找过程示例（查找第4小元素）以以5为轴值划分序列为轴值划分序列42，只在右侧查找，只在右侧查找以以4为轴值划分序列为轴值划分序列44，轴值即为第，轴值即为第4小元素小元素2 3 4 1 5 6 9 8 72 3 4 1 1 2 4 3 4 3 3 4 算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法5.7选择问题

23、 1.i=1;j=n;/设置初始查找区间 2.以ri为轴值对序列rirj进行一次划分，得到轴值的位置s;3.将轴值位置s与k比较 3.1 如果k=s，则将rs作为结果返回；3.2 否则，如果k1)i=i/2;for(j=0;jdef abcdef abcdef，可可以以肯肯定定这这六六枚枚硬硬币币中中必必有有一一枚枚为为假假币币，同同时时也也说说明明g，h为为真真币币。这这时时可可将将天天平平两两端端各各去去掉掉一一枚枚硬硬币币，假假设设去去掉掉c和和f，同同时时将将天天平平两两端端的的硬硬币币各各换换一一枚枚，假假设设硬硬币币b，e作作了了互互换换，然然后后进进行行第第二二次次比较，比较的结

24、果同样可能有三种：比较，比较的结果同样可能有三种：aedb：这这种种情情况况表表明明天天平平两两端端去去掉掉硬硬币币c，f且且硬硬币币b，e互互换换后后，天天平平两两端端的的轻轻重重关关系系保保持持不不变变，从从而而说说明明了了假假币币必必然然是是a，d中中的的一一个个，这这时时我我们们只只要要用用一一枚枚真真币币（例例如如h）和和a进进行行比比较较，就就能能找找出出假假币币。若若ah，则则a是是较较重重的的假假币币；若若ah，则则d为为较较轻轻的的假假币币；不不可可能能出出现现ah，则，则c是较重的假币；若是较重的假币；若ch，则，则f为较轻的假币；不可能出现为较轻的假币；不可能出现ch的情

25、况。的情况。aeh，则则b是是较较重重的的假假币币；若若bh，则则e为为较较轻轻的的假假币币；不可能出现不可能出现b=八枚硬币问题的判定树八枚硬币问题的判定树算法设计与分析算法设计与分析清华大学出版社清华大学出版社5.5 实验项目实验项目八枚硬币问题八枚硬币问题 1.实验题目实验题目 在八枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测出这枚假币。2实验目的实验目的（1）深刻理解并掌握减治法的设计思想；（2）提高应用减治法设计算法的技能；（3）理解这样一个观点：建立正确的模型对于问题的求解是非常重要的。算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.实验要求实验要求（1）设计减治算法实现八枚硬币问题；（2）设计实验程序，考察用减治技术设计的算法是否高效；（3）扩展算法，使之能处理n枚硬币中有1枚假币的问题。