分治算法(金塊問題)

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

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

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

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

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

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