算法设计与分析 第5章 减治法.pptVIP

第五章 减 治 法;变治法分两个阶段工作，即“变”阶段和“治”阶段. 变治法的三种类型： 1)实例化简(instance simplification) 2)改变表现(representation change) 3)问题化简(problem reduction);子问题 的规模是n/2;;应用分治法（例如二分法）得到的算法通常具有如下递推式： ;2一个简单的例子—两个序列的中位数;想法：分别求出两个序列的中位数，记为a和b；比较a和b，有下列三种情况： ① a = b：则a即为两个序列的中位数； ② a b：则中位数只能出现在a和b之间，在序列A中舍弃a之前的元素得到序列A1，在序列B中舍弃b之后的元素得到序列B1； ③ a b：则中位数只能出现在b和a之间，在序列A中舍弃a之后的元素得到序列A1，在序列B中舍弃b之前的元素得到序列B1； 在A1和B1中分别求出中位数，重复上述过程，直到两个序列中只有一个元素，则较小者即为所求。;对于两个给定的序列A={11, 13, 15, 17, 19}, B={2, 4, 10, 15, 20}，求序列A和B的中位数的过程。;1. 循环直到序列A和序列B均只有一个元素 1.1 a = 序列A的中位数； 1.2 b = 序列B的中位数； 1.3 比较a和b，执行下面三种情况之一： 1.3.1 若a=b，则返回a，算法结束； 1.3.2 若ab，则在序列A中舍弃a之前的元素，在序列B中舍弃b之后的元素，转步骤1； 1.3.3 若ab，则在序列A中舍弃a之后的元素，在序列B中舍弃b之前的元素，转步骤1； 2. 序列A和序列B均只有一个元素，返回较小者；;查找问题中的减治法——折半查找;折半查找——想法;折半查找——实例;1. low=1；high=n； //设置初始查找区间 2. 测试查找区间［low，high］是否存在，若不存在，则查找失败；否则 3. 取中间点mid=(low+high)/2; 比较k与r[mid]，有以下三种情况： 3.1 若kr[mid]，则high=mid-1；查找在左半区进行，转2； 3.2 若kr[mid]，则low=mid+1；查找在右半区进行，转2； 3.3 若k=r[mid]，则查找成功，返回记录在表中位置mid；;查找问题中的减治法——二叉查找树;二叉查找树查找——想法;在二叉查找树中查找关键字值为35，95的过程：;BiNode * SearchBST(BiNode *root, int k) { if (root= =NULL) return NULL； else if (root-data==k) return root; else if (kroot-data) return SearchBST(root-lchild, k); else return SearchBST(root-rchild, k); };查找问题中的减治法——选择问题;选择问题——想法;选择问题——实例;选择问题——算法;排序问题中的减治法——堆排序;堆排序——想法;堆排序——实例;堆排序——算法;问题描述：假设有n=2k个选手进行竞技淘汰赛，最后决出冠军的选手，设计竞技淘汰比赛的过程。;淘汰赛冠军问题——实例 ; string Game(string r[ ], int n) { i=n; while (i1) { i=i/2; for (j=0; ji; j++) if (Comp(r[j+i], r[j])) r[j]=r[j+i]; } return r[0]; };;最自然的想法就是一分为二，也就是把n枚硬币分成两组，每组有?n/2?枚硬币，如果n为奇数，就留下一枚硬币，然后把两组硬币分别放到天平的两端。如果两组硬币的重量相同，那么留下的硬币就是假币；否则，用同样的方法对较轻的那组硬币进行同样的处理，因为假币一定在较轻的那组里。 考虑不是把硬币分成两组，而是分成三组？ ;1. 如果n等于1，则该硬币即为假币，输出对应的序号，算法结束； 2. 计算3组的硬币个数num1、num2和num3； 3. add1 = 第1组???币的重量和；add2 = 第2