分治策略ppt課件-展示頁
2025-05-15 08:34本頁面
【正文】 3 4 ? 一種方式 兩兩對比，找到輕者，最差比較 8次 ? 另外一種 1)將 16個硬幣分成 A、 B兩半； 2)將 A放儀器的一邊， B放另一邊，如果 A袋輕，則表明偽幣在 A，解子問題 A即可，否則，解子問題 B。你的任務是找出這個偽造的硬幣。2022/6/3 1 第 4講 分治策略 2022/6/3 2 主要內(nèi)容 ? 分治法基本思想 ? 二分搜索算法 ? 合并排序算法 ? 快速排序算法 ? 線性時間選擇 2022/6/3 3 分治法的基本思想 例 :[找偽幣問題 ]給你一個裝有 1 6個硬幣的袋子。 1 6個硬幣中有一個是偽造的，并且那個偽造的硬幣比真的硬幣要輕一些。為了幫助你完成這一任務，將提供一臺可用來比較兩組硬幣重量的儀器，利用這臺儀器，可以知道兩組硬幣的重量是否相同。 2022/6/3 5 例 2－ 5 金塊問題 有一個老板有一袋金塊。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。如果有新的金塊周期性的加入袋中，則每個月都必須找出最輕和最重的金塊。 2022/6/3 6 ? 假設袋中有 n 個金塊。找到最重的金塊后，可以從余下的 n1個金塊中用類似的方法通過 n2次比較找出最輕的金塊。 ? n≤2時，識別出最重和最輕的金塊，做一次比較。 第二步 ，分別找出在 A和 B中最重和最輕的金塊。 第三步 ，通過比較 HA 和 HB，可以找到所有金塊中最重的；通過比較 LA 和 LB，可以找到所有金塊中最輕的。假設 n是 2的冪。當 n是 2的冪時，可知 c(n) = 3n/ 2 2。 2022/6/3 8 分治法的基本思想 分而治之方法與軟件設計的模塊化方法非常相似。小問題通常與原問題相似，可以遞歸地使用分而治之策略來解決。 DivideandConquer(P) { if (|P|=n0) Adhoc(P)。,Pk。i=k。 return Merge(y1, } 判斷輸入規(guī)模 p是否足夠的小 解該規(guī)模問題的函數(shù) 分割函數(shù) 分治解決 合并得到最后結果 2022/6/3 11 問題 ? 應把原問題分為多少個子問題才較適宜？ ? 每個子問題是否規(guī)模相同或怎樣才為適當？ 2022/6/3 12 分治法計算效率 ? 原問題規(guī)模 ——n ? 分成 k個子問題，每個規(guī)模 ——n/m ? 設分解
教學課件相關推薦
鄂ICP備17016276號-1