【正文】 ，我們希望用最少的比較次數(shù)找出最輕和最重的金塊。每一組有兩個金塊，可以用一次比較在A中找出較重的金塊HA1和較輕的金塊LA1。為了得到兩個矩陣相乘的分而治之算法，需要： 1) 定義一個小問題，并指明小問題是如何進行乘法運算的； 2) 確定如何把一個大的問題劃分成較小的問題，并指明如何對這些較小的問題進行乘法運算； 3) 最后指出如何根據(jù)小問題的結果得到大問題的結果。這7個小矩陣為矩陣D, E, ., J，矩陣D到J可以通過7次矩陣乘法， 6次矩陣加法，和4次矩陣減法計算得出。直接計算時需要4 0 9 6m+ 3 8 4 0a次操作。算法從根節(jié)點開始。若n1且為奇數(shù)，第一個重量w [ 0 ]將成為最小值和最大值的候選值，因此將有偶數(shù)個重量值w [ 1 : n 1 ]參與f o r循環(huán)。 // 循環(huán)起點if (n % 2) {// n 為奇數(shù)Min = Max = 0。需要進行多少次重量的比較？2. 考慮例1 4 1的偽幣問題。利用不同的k 值（見公式（1 4 6））進行實驗，以確定k 為何值時程序性能最佳。給出以n 為變量的運行時間表達式。4) 注意到如果比較操作的開銷不是很高，分而治之算法在最壞情況下不會比其他算法優(yōu)越，為什么？它的平均時間優(yōu)于程序2 2 7嗎？為什么？4. 證明直接運用公式（1 4 2）~（1 4 5）得出結果的矩陣乘法的分而治之算法的復雜性為(n3 )。if (w[i] w[Min]) Min = i。 Max){// 尋找w [ 0 : n 1 ]中的最小和最大值// 如果少于一個元素，則返回f a l s e// 特殊情形： n = 1if (n 1) return false。根據(jù)上述步驟，可以得出程序1 4 1的非遞歸代碼。解決金塊問題的分而治之算法（例2 2）和歸并排序方法（ 2 . 3節(jié)）就可以不利用遞歸而通過一個非遞歸程序來更快地完成。要使S t r a s s e n方法比直接計算方法快，至少要求5 1 24 4 8次乘法的開銷比6 2 44 4 8次加/減法的開銷大。算法的復雜性為(n3 )，此復雜性與程序2 2 4直接使用公式（2 1）所得到的復雜性是一樣的。對于較大的n，c(n) = 2c(n/ 2 ) + 2。在第二步中，若n＞2，則遞歸地應用分而治之方法。每個月將有兩名雇員會因其優(yōu)異的表現(xiàn)分別被獎勵一個金塊。把兩個或三個硬幣的情況作為不可再分的小問題。假如兩硬幣重量相等，則繼續(xù)比較硬幣5和硬幣6。君主和殖民者們所成功運用的分而治之策略也可以運用到高效率的計算機算法的設計過程中。按照這種方式，可以最多通過8次比較來判斷偽幣的存在并找出這一偽幣。注意如果只有一個硬幣，那么不能判斷出它是否就是偽幣。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。假設n= 8。當n是2的冪時，使用迭代方法（見例2 2 0）可知c(n) = 3n/ 2 2。事實上，由于矩陣分割和再組合所花費的額外開銷，使用分而治之算法得出結果的時間將比用程序2 2 4還要長?；蛘哒f一次乘法的開銷應該大于近似2 . 7 5次加/減法的開銷。例24 [金塊問題] 用例2 2的算法尋找8個金塊中最輕和最重金塊的工作可以用二叉樹來表示。該程序用于尋找到數(shù)組w [ 0 : n 1 ]中的最小數(shù)和最大數(shù)，若n 1，則程序返回f a l s e，否則返回t r u e。if (n == 1) {Min = Max = 0。}}return true。因此相應的分而治之程序將比程序2 2 4要慢。 。*6.