分而治之算法論述(存儲(chǔ)版)
【正文】 + 4 2 8 8a次操作。注意事項(xiàng)因此，根節(jié)點(diǎn)A表示尋找8個(gè)金塊中最輕、最重金塊的問題，而節(jié)點(diǎn)B表示找出a,b,c 和d 這4個(gè)金塊中最輕和最重金塊的問題。2) 比較每個(gè)大小為2的問題中的金塊，確定哪一個(gè)較重和哪一個(gè)較輕。首先處理n≤1的情況。當(dāng)n 為奇數(shù)時(shí)，f o r循環(huán)外部沒有執(zhí)行比較，而內(nèi)部執(zhí)行了3(n1)/2次比較。}/ /對(duì)Min 和M a x進(jìn)行初始化int s。}// 比較余下的數(shù)對(duì)for (int i = s。1. 將例1 4 1的分而治之算法擴(kuò)充到n 1個(gè)硬幣的情形。2) 程序2 2 6和2 2 7是另外兩個(gè)尋找n 個(gè)元素中最大值和最小值的代碼。*6. 編寫S t r a s s e n矩陣乘法程序。 和B39。 。1) 求m / n。因此相應(yīng)的分而治之程序?qū)⒈瘸绦? 2 4要慢。3. 1) 編寫一個(gè)C++ 程序，實(shí)現(xiàn)例1 4 2中尋找n 個(gè)元素中最大值和最小值的兩種方案。}}return true。Max = 1。if (n == 1) {Min = Max = 0。下面進(jìn)行復(fù)雜性分析。該程序用于尋找到數(shù)組w [ 0 : n 1 ]中的最小數(shù)和最大數(shù)，若n 1，則程序返回f a l s e，否則返回t r u e。接著在F，G和C上重復(fù)這一過程，最后解決問題A。例24 [金塊問題] 用例2 2的算法尋找8個(gè)金塊中最輕和最重金塊的工作可以用二叉樹來表示。因?yàn)榇蟮木仃嚂?huì)被遞歸地分割成小矩陣直到每個(gè)矩陣的大小小于或等于k（k至少為8，也許更大，具體值由計(jì)算機(jī)的性能決定）. 用迭代方法計(jì)算，可得t(n) = (nl og27 )?；蛘哒f一次乘法的開銷應(yīng)該大于近似2 . 7 5次加/減法的開銷。而直接使用公式（2 1），則需要8次乘法和7次加/減法。事實(shí)上，由于矩陣分割和再組合所花費(fèi)的額外開銷，使用分而治之算法得出結(jié)果的時(shí)間將比用程序2 2 4還要長?？疾煲粋€(gè)n 1的大問題。當(dāng)n是2的冪時(shí)，使用迭代方法（見例2 2 0）可知c(n) = 3n/ 2 2。通過比較HA 和HB（LA 和LB），就能找出所有金塊中最重和最輕的。假設(shè)n= 8。程序2 2 6和2 2 7是另外兩種方法，前者需要進(jìn)行2n2次比較，后者最多需要進(jìn)行2n2次比較。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。比較這兩組，肯定有一組輕一些。注意如果只有一個(gè)硬幣，那么不能判斷出它是否就是偽幣。假如兩組硬幣重量相等，則可以判斷偽幣不存在。按照這種方式，可以最多通過8次比較來判斷偽幣的存在并找出這一偽幣。你的任務(wù)是找出這個(gè)偽造的硬幣。君主和殖民者們所成功運(yùn)用的分而治之策略也可以運(yùn)用到高效率的計(jì)算機(jī)算法的設(shè)計(jì)過程中。1 6個(gè)硬幣中有一個(gè)是偽造的，并且那個(gè)偽造的硬幣比真的硬幣要輕一些。假如兩硬幣重量相等，則繼續(xù)比較硬幣5和硬幣6?？梢岳脙x器來比較A組硬幣和B組硬幣的重量。把兩個(gè)或三個(gè)硬幣的情況作為不可再分的小問題。稱其中一組為B1，另一組為B2。每個(gè)月將有兩名雇員會(huì)因其優(yōu)異的表現(xiàn)分別被獎(jiǎng)勵(lì)一個(gè)金塊。這樣，比較的總次數(shù)為2n3。在第二步中，若n＞2，則遞歸地應(yīng)用分而治之方法。同樣需要另外4次比較來確定HB 和LB。對(duì)于較大的n，c(n) = 2c(n/ 2 ) + 2。對(duì)于11階的小矩陣，可以通過將兩矩陣中的兩個(gè)元素直接相乘而得到結(jié)果。算法的復(fù)雜性為(n3 )，此復(fù)雜性與程序2 2 4直接使用公式（2 1）所得到的復(fù)雜性是一樣的。利用計(jì)算D～J的公式，得：D= 1（68）=2E= 4（75）= 8F=（
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1