分治算法(金塊問題)

1、問題描述：有一個(gè)老板有一袋金塊。每個(gè)月將有兩名雇員會(huì)因其優(yōu)異的表現(xiàn)分別被獎(jiǎng)勵(lì)一個(gè)金塊。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。根據(jù)這種方式，除非有新的金塊加入袋中，否則第一名雇員所得到的金塊總是比第二名雇員所得到的金塊重。如果有新的金塊周期性的加入袋中，則每個(gè)月都必須找出最輕和最重的金塊。假設(shè)有一臺(tái)比較重量的儀器，我們希望用最少的比較次數(shù)找出最輕和最重的金塊算法思想：分而治之方法與軟件設(shè)計(jì)的模塊化方法非常相似。為了解決一個(gè)大的問題，可以： 1) 把它分成兩個(gè)或多個(gè)更小的問題； 2) 分別解決每個(gè)小問題； 3) 把各小問題的解答組合起來，即可得到原問題的解

2、答。小問題通常與原問題相似，可以遞歸地使用分而治之策略來解決。問題分析:一般思路：假設(shè)袋中有n 個(gè)金塊?？梢杂煤瘮?shù)M a x（程序1 - 3 1）通過n-1次比較找到最重的金塊。找到最重的金塊后，可以從余下的n-1個(gè)金塊中用類似的方法通過n-2次比較找出最輕的金塊。這樣，比較的總次數(shù)為2n-3。分治法：當(dāng)n很小時(shí)，比如說， n2，識(shí)別出最重和最輕的金塊，一次比較就足夠了。當(dāng)n 較大時(shí)（n2），第一步，把這袋金塊平分成兩個(gè)小袋A和B。第二步，分別找出在A和B中最重和最輕的金塊。設(shè)A中最重和最輕的金塊分別為HA 與LA，以此類推，B中最重和最輕的金塊分別為HB 和LB。第三步，通過比較HA 和HB

3、，可以找到所有金塊中最重的；通過比較LA 和LB，可以找到所有金塊中最輕的。在第二步中，若n2，則遞歸地應(yīng)用分而治之方法程序設(shè)計(jì)據(jù)上述步驟，可以得出程序1 4 - 1的非遞歸代碼。該程序用于尋找到數(shù)組w 0 : n - 1 中的最小數(shù)和最大數(shù)，若n < 1，則程序返回f a l s e，否則返回t r u e。當(dāng)n1時(shí)，程序1 4 - 1給M i n和M a x置初值以使w M i n 是最小的重量，w M a x 為最大的重量。首先處理n1的情況。若n>1且為奇數(shù)，第一個(gè)重量w 0 將成為最小值和最大值的候選值，因此將有偶數(shù)個(gè)重量值w 1 : n - 1 參與f o r循環(huán)。當(dāng)n

4、 是偶數(shù)時(shí)，首先將兩個(gè)重量值放在for 循環(huán)外進(jìn)行比較，較小和較大的重量值分別置為Min和Max，因此也有偶數(shù)個(gè)重量值w2:n-1參與for循環(huán)。在for 循環(huán)中，外層if 通過比較確定( w i , w i + 1 )中的較大和較小者。此工作與前面提到的分而治之算法步驟中的2) 相對(duì)應(yīng)，而內(nèi)層的i f負(fù)責(zé)找出較小重量值和較大重量值中的最小值和最大值，這個(gè)工作對(duì)應(yīng)于3 )。for 循環(huán)將每一對(duì)重量值中較小值和較大值分別與當(dāng)前的最小值w M i n 和最大值w M a x 進(jìn)行比較，根據(jù)比較結(jié)果來修改M i n和M a x（如果必要）。復(fù)雜性分析注意到當(dāng)n為偶數(shù)時(shí)，在for 循環(huán)外部將執(zhí)行一次比

5、較而在f o r循環(huán)內(nèi)部執(zhí)行3 ( n / 2 - 1 )次比較，比較的總次數(shù)為3 n / 2 - 2。當(dāng)n 為奇數(shù)時(shí)，f o r循環(huán)外部沒有執(zhí)行比較，而內(nèi)部執(zhí)行了3(n-1)/2次比較。因此無論n 為奇數(shù)或偶數(shù)，當(dāng)n>0時(shí)，比較的總次數(shù)為3n/2ù-2次。關(guān)鍵步驟：程序14-1 找出最小值和最大值的非遞歸程序template<class T>bool MinMax(T w, int n, T& Min, T& Max)/ 尋找w 0 : n - 1 中的最小和最大值/ 如果少于一個(gè)元素，則返回f a l s e/ 特殊情形： n <= 1if

6、 (n < 1) return false;if (n = 1) Min = Max = 0;return true;/ /對(duì)Min 和M a x進(jìn)行初始化int s; / 循環(huán)起點(diǎn)if (n % 2) / n 為奇數(shù)Min = Max = 0;s = 1;else / n為偶數(shù)，比較第一對(duì)if (w0 > w1) Min = 1;Max = 0;else Min = 0;Max = 1;s = 2;/ 比較余下的數(shù)對(duì)for (int i = s; i < n; i += 2) / 尋找wi 和w i + 1 中的較大者 / 然后將較大者與w M a x 進(jìn)行比較 / 將較小者與w M i n 進(jìn)行比較if (wi > wi+1) if (wi > wMax) Max = i;if (wi+1 &