分而治之算法論述(已修改)
2025-08-16 14:25 本頁面
【正文】 君主和殖民者們所成功運(yùn)用的分而治之策略也可以運(yùn)用到高效率的計(jì)算機(jī)算法的設(shè)計(jì)過程中。本章將首先介紹怎樣在算法設(shè)計(jì)領(lǐng)域應(yīng)用這一古老的策略，然后將利用這一策略解決如下問題：最小最大問題、矩陣乘法、殘缺棋盤、排序、選擇和計(jì)算一個(gè)幾何問題——找出二維空間中距離最近的兩個(gè)點(diǎn)。 本章給出了用來分析分而治之算法復(fù)雜性的數(shù)學(xué)方法，并通過推導(dǎo)最小最大問題和排序問題的復(fù)雜性下限來證明分而治之算法對(duì)于求解這兩種問題是最優(yōu)的（因?yàn)樗惴ǖ膹?fù)雜性與下限一致）。 算法思想分而治之方法與軟件設(shè)計(jì)的模塊化方法非常相似。為了解決一個(gè)大的問題，可以： 1) 把它分成兩個(gè)或多個(gè)更小的問題； 2) 分別解決每個(gè)小問題； 3) 把各小問題的解答組合起來，即可得到原問題的解答。小問題通常與原問題相似，可以遞歸地使用分而治之策略來解決。例21 [找出偽幣] 給你一個(gè)裝有1 6個(gè)硬幣的袋子。1 6個(gè)硬幣中有一個(gè)是偽造的，并且那個(gè)偽造的硬幣比真的硬幣要輕一些。你的任務(wù)是找出這個(gè)偽造的硬幣。為了幫助你完成這一任務(wù)，將提供一臺(tái)可用來比較兩組硬幣重量的儀器，利用這臺(tái)儀器，可以知道兩組硬幣的重量是否相同。比較硬幣1與硬幣2的重量。假如硬幣1比硬幣2輕，則硬幣1是偽造的；假如硬幣2比硬幣1輕，則硬幣2是偽造的。這樣就完成了任務(wù)。假如兩硬幣重量相等，則比較硬幣3和硬幣4。同樣，假如有一個(gè)硬幣輕一些，則尋找偽幣的任務(wù)完成。假如兩硬幣重量相等，則繼續(xù)比較硬幣5和硬幣6。按照這種方式，可以最多通過8次比較來判斷偽幣的存在并找出這一偽幣。另外一種方法就是利用分而治之方法。假如把1 6硬幣的例子看成一個(gè)大的問題。第一步，把這一問題分成兩個(gè)小問題。隨機(jī)選擇8個(gè)硬幣作為第一組稱為A組，剩下的8個(gè)硬幣作為第二組稱為B組。這樣，就把1 6個(gè)硬幣的問題分成兩個(gè)8硬幣的問題來解決。第二步，判斷A和B組中是否有偽幣?？梢岳脙x器來比較A組硬幣和B組硬幣的重量。假如兩組硬幣重量相等，則可以判斷偽幣不存在。假如兩組硬幣重量不相等，則存在偽幣，并且可以判斷它位于較輕的那一組硬幣中。最后，在第三步中，用第二步的結(jié)果得出原先1 6個(gè)硬幣問題的答案。若僅僅判斷硬幣是否存在，則第三步非常簡(jiǎn)單。無論A組還是B組中有偽幣，都可以推斷這1 6個(gè)硬幣中存在偽幣。因此，僅僅通過一次重量的比較，就可以判斷偽幣是否存在。現(xiàn)在假設(shè)需要識(shí)別出這一偽幣。把兩個(gè)或三個(gè)硬幣的情況作為不可再分的小問題。注意如果只有一個(gè)硬幣，那么不能判斷出它是否就是偽幣。在一個(gè)小問題中，通過將一個(gè)硬幣分別與其他兩個(gè)硬幣比較，最多比較兩次就可以找到偽幣。這樣，1 6硬幣的問題就被分為兩個(gè)8硬幣（A組和B組）的問題。通過比較這兩組硬幣的重量，可以判斷偽幣是否存在。如果沒有偽幣，則算法終止。否則，繼續(xù)劃分這兩組硬幣來尋找偽幣。假設(shè)B是輕的那一組，因此再把它分成兩組，每組有4個(gè)硬幣。稱其中一組為B1，另一組為B2。比較這兩組，肯定有一組輕一些。如果B1輕，則偽幣在B1中，再將B1又分成兩組，每組有兩個(gè)硬幣，稱其中一組為B1a，另一組為B1b。比較這兩組，可以得到一個(gè)較輕的組。由于這個(gè)組只有兩個(gè)硬幣，因此不必再細(xì)分。比較組中兩個(gè)硬幣的重量，可以立即知道哪一個(gè)硬幣輕一些。較輕的硬幣就是所要找的偽幣。例22 [金塊問題] 有一個(gè)老板有一袋金塊。每個(gè)月將有兩名雇員會(huì)因其優(yōu)異的表現(xiàn)分別被獎(jiǎng)勵(lì)一個(gè)金塊。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。根據(jù)這種方式，除非有新的金塊加入袋中，否則第一名雇員所得到的金塊總是比第二名雇員所得到的金塊重。如果有新的金塊周期性的加入袋中，則每個(gè)月都必須找出最輕和最重的金塊。假設(shè)有一臺(tái)比較重量的儀器，我們希望用最少的比較次數(shù)找出最輕和最重的金塊。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1