第4章分治法 “分”而治之
第4章 分治法 —— “分”而治之
主要内容 般方法 2.二分检索 3.找最大和最小元素 4.归并分类 5.快速分类 6.选择问题 7.斯特拉森矩阵乘法
主要内容 1. 一般方法 2. 二分检索 3. 找最大和最小元素 4. 归并分类 5. 快速分类 6. 选择问题 7. 斯特拉森矩阵乘法
31一般方法 令对大规模问题的求解 利用分治法求解大规模问题 1.基本思想 分而治之方法与软件设计的模块化方法非常相似。 为解决一个大问题,可以(1)把它分解成两个或多个 更小的问题;(2)分别解决每个小问题;(3)把各 小问题的解答组合起来,即可得到原问题的解。 小问题通常与原问题相似或同质,因而可以递归地 使用分而治之策略解决
❖ 对大规模问题的求解 ❖ 利用分治法求解大规模问题 1.基本思想 分而治之方法与软件设计的模块化方法非常相似。 为解决一个大问题，可以（1）把它分解成两个或多个 更小的问题；（2）分别解决每个小问题；（3）把各 小问题的解答组合起来，即可得到原问题的解。 小问题通常与原问题相似或同质 ，因而可以递归地 使用分而治之策略解决。 3.1 一般方法
逐步细化的过程 /子问题 /子问题求解 al 问题 子结果 q2 12 A 分解 合并 k k 通常,子问题与原始问题“同质
Q q2 qk q1 子问题 ... a2 ak a1 子问题求解 ... 问题 A 子结果 分解 合并 逐步细化的过程 通常，子问题与原始问题“同质
例1找伪币]假设16枚金币中有一枚是伪造的,真假金 币的区别仅是重量不同,利用一个没有砝码的天平作工具, 找出这枚伪造的金币 例2[金块问题]有一个老板有一袋金块。每个月将有两 名雇员会因其优异的表现分别被奖励一个金块。按规矩, 排第一的雇员将得到袋中最重的金块,排名第二的雇员 将得到袋中最轻的金块。根据这种方式,除非有新金块 快加入袋中,否则第一名雇员所得到的金块总是比第二 名雇员所得到的金块重,如果有新的金块周期性的加入 袋中,则每个月都必须找出最重和最轻的金块。假设有 台比较重量的仪器,希望用最少的比较次数找出最重 和最轻的金块。 问题的分解策略有多种
例1 [找伪币] 假设16 枚金币中有一枚是伪造的，真假金 币的区别仅是重量不同，利用一个没有砝码的天平作工具， 找出这枚伪造的金币。 例2 [金块问题]有一个老板有一袋金块。每个月将有两 名雇员会因其优异的表现分别被奖励一个金块。按规矩， 排第一的雇员将得到袋中最重的金块，排名第二的雇员 将得到袋中最轻的金块。根据这种方式，除非有新金块 快加入袋中，否则第一名雇员所得到的金块总是比第二 名雇员所得到的金块重，如果有新的金块周期性的加入 袋中，则每个月都必须找出最重和最轻的金块。假设有 一台比较重量的仪器，希望用最少的比较次数找出最重 和最轻的金块。 问题的分解策略有多种