分而治之算法論述-資料下載頁
2025-08-04 14:25本頁面
【正文】 = 1if (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 (w[0] w[1]) {Min = 1。Max = 0。}else {Min = 0。Max = 1。}s = 2。}// 比較余下的數(shù)對(duì)for (int i = s。 i n。 i += 2) {// 尋找w[i] 和w [ i + 1 ]中的較大者// 然后將較大者與w [ M a x ]進(jìn)行比較// 將較小者與w [ M i n ]進(jìn)行比較if (w[i] w[i+1]) {if (w[i] w[Max]) Max = i。if (w[i+1] w[Min]) Min = i + 1。}else {if (w[i+1] w[Max]) Max = i + 1。if (w[i] w[Min]) Min = i。}}return true。}練習(xí)1. 將例1 4 1的分而治之算法擴(kuò)充到n 1個(gè)硬幣的情形。需要進(jìn)行多少次重量的比較？2. 考慮例1 4 1的偽幣問題。假設(shè)把條件“偽幣比真幣輕”改為“偽幣與真幣的重量不同”，同樣假定袋中有n 個(gè)硬幣。1) 給出相應(yīng)分而治之算法的形式化描述，該算法可輸出信息“不存在偽幣”或找出偽幣。算法應(yīng)遞歸地將大的問題劃分成兩個(gè)較小的問題。需要多少次比較才能找到偽幣（如果存在偽幣）？2) 重復(fù)1) ，但把大問題劃分為三個(gè)較小問題。3. 1) 編寫一個(gè)C++ 程序，實(shí)現(xiàn)例1 4 2中尋找n 個(gè)元素中最大值和最小值的兩種方案。使用遞歸來完成分而治之方案。2) 程序2 2 6和2 2 7是另外兩個(gè)尋找n 個(gè)元素中最大值和最小值的代碼。試分別計(jì)算出每段程序所需要的最少和最大比較次數(shù)。3) 在n 分別等于1 0 0，1 0 0 0或10 000的情況下，比較1）、2）中的程序和程序1 4 1的運(yùn)行時(shí)間。對(duì)于程序2 2 7，使用平均時(shí)間和最壞情況下的時(shí)間。1）中的程序和程序2 2 6應(yīng)具有相同的平均時(shí)間和最壞情況下的時(shí)間。4) 注意到如果比較操作的開銷不是很高，分而治之算法在最壞情況下不會(huì)比其他算法優(yōu)越，為什么？它的平均時(shí)間優(yōu)于程序2 2 7嗎？為什么？4. 證明直接運(yùn)用公式（1 4 2）~（1 4 5）得出結(jié)果的矩陣乘法的分而治之算法的復(fù)雜性為(n3 )。因此相應(yīng)的分而治之程序?qū)⒈瘸绦? 2 4要慢。5. 用迭代的方法來證明公式（1 4 6）的遞歸值為(n l og27)。*6. 編寫S t r a s s e n矩陣乘法程序。利用不同的k 值（見公式（1 4 6））進(jìn)行實(shí)驗(yàn)，以確定k 為何值時(shí)程序性能最佳。比較程序及程序2 2 4的運(yùn)行時(shí)間?？扇 為2的冪來進(jìn)行比較。7. 當(dāng)n 不是2的冪時(shí)，可以通過增加矩陣的行和列來得到一個(gè)大小為2的冪的矩陣。假設(shè)使用最少的行數(shù)和列數(shù)將矩陣擴(kuò)充為m 階矩陣，其中m 為2的冪。1) 求m / n。2) 可使用哪些矩陣項(xiàng)組成新的行和列，以使新矩陣A39。 和B39。 相乘時(shí)，原來的矩陣A和B相乘的結(jié)果會(huì)出現(xiàn)在C39。 的左上角？3) 使用S t r a s s e n方法計(jì)算A39。 * B39。 所需要的時(shí)間為( )。給出以n 為變量的運(yùn)行時(shí)間表達(dá)式。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1