分而治之算法論述(完整版)
【正文】 最少的比較次數(shù)找出最輕和最重的金塊。由于這個組只有兩個硬幣，因此不必再細分。通過比較這兩組硬幣的重量，可以判斷偽幣是否存在。若僅僅判斷硬幣是否存在，則第三步非常簡單。第一步，把這一問題分成兩個小問題。假如硬幣1比硬幣2輕，則硬幣1是偽造的；假如硬幣2比硬幣1輕，則硬幣2是偽造的。 算法思想分而治之方法與軟件設計的模塊化方法非常相似。為了解決一個大的問題，可以： 1) 把它分成兩個或多個更小的問題； 2) 分別解決每個小問題； 3) 把各小問題的解答組合起來，即可得到原問題的解答。這樣就完成了任務。隨機選擇8個硬幣作為第一組稱為A組，剩下的8個硬幣作為第二組稱為B組。無論A組還是B組中有偽幣，都可以推斷這1 6個硬幣中存在偽幣。如果沒有偽幣，則算法終止。比較組中兩個硬幣的重量，可以立即知道哪一個硬幣輕一些。假設袋中有n 個金塊。第二步，分別找出在A和B中最重和最輕的金塊。經(jīng)過另外一次比較，又能找出HA 2和LA 2。設c(n)為使用分而治之方法所需要的比較次數(shù)。為了使討論簡便，假設n 是2的冪（也就是說， n是1，2，4，8，1 6，.）。矩陣Bi 和Ci 的定義與此類似.根據(jù)上述公式，經(jīng)過8次n/ 2n/ 2階矩陣乘法和4次n/ 2n/ 2階矩陣的加法，就可以計算出A與B的乘積。前述的4個小矩陣可以由矩陣D到J通過6次矩陣加法和兩次矩陣減法得出. 用上述方案來解決n= 2的矩陣乘法。每次矩陣乘法需花費6 4m+ 4 8a次操作，每次矩陣加法或減法需花費1 6a次操作。若一次乘法的開銷與一次加/減法的開銷相同，則S t r a s s e n方法需要7 8 7 2次操作及用于問題分解的額外時間，而直接計算方法則需要7 9 3 6次操作加上程序中執(zhí)行f o r循環(huán)以及其他語句所花費的時間。在許多例子里，這些遞歸算法在遞歸程序中得到了很好的運用。由根節(jié)點表示的8金塊問題被劃分成由節(jié)點B和C所表示的兩個4金塊問題。大小為1的問題中只有一個金塊，它既是最輕的金塊也是最重的金塊。當n 是偶數(shù)時，首先將兩個重量值放在for 循環(huán)外進行比較，較小和較大的重量值分別置為Min和Max，因此也有偶數(shù)個重量值w[2:n1]參與for循環(huán)。2次。s = 1。 i += 2) {// 尋找w[i] 和w [ i + 1 ]中的較大者// 然后將較大者與w [ M a x ]進行比較// 將較小者與w [ M i n ]進行比較if (w[i] w[i+1]) {if (w[i] w[Max]) Max = i。假設把條件“偽幣比真幣輕”改為“偽幣與真幣的重量不同”，同樣假定袋中有n 個硬幣。3) 在n 分別等于1 0 0，1 0 0 0或10 000的情況下，比較1）、2）中的程序和程序1 4 1的運行時間。比較程序及程序2 2 4的運行時間。 的左上角？3) 使用S t r a s s e n方法計算A39。 所需要的時間為( )。7. 當n 不是2的冪時，可以通過增加矩陣的行和列來得到一個大小為2的冪的矩陣。1）中的程序和程序2 2 6應具有相同的平均時間和最壞情況下的時間。算法應遞歸地將大的問題劃分成兩個較小的問題。}else {if (w[i+1] w[Max]) Max = i + 1。Max = 0。 Min, Tamp。此工作與前面提到的分而治之算法步驟中的2) 相對應，而內(nèi)層的i f負責找出較小重量值和較大重量值中的最小值和最大值，這個工作對應于3 )。對于節(jié)點A到C執(zhí)行這種比較?？赏ㄟ^比較金塊a 和b 哪一個較重來解決D節(jié)點所表示的2金塊問題。不過在有些情況下，不使用這樣的遞歸棧而采用一個非遞歸程
環(huán)評公示相關推薦
鄂ICP備17016276號-1