算法設(shè)計(jì)與分析習(xí)題解答（第2版）

習(xí)題1-1 實(shí)參交換1
習(xí)題1-2 方法頭簽名1
習(xí)題1-3 數(shù)組排序判定1
習(xí)題1-4 函數(shù)的漸近表達(dá)式2
習(xí)題1-5 O(1)和O(2)的區(qū)別2
習(xí)題1-7 按漸近階排列表達(dá)式2
習(xí)題1-8 算法效率2
習(xí)題1-9 硬件效率3
習(xí)題1-10 函數(shù)漸近階3
習(xí)題1-11 n!的階4
習(xí)題1-12 平均情況下的計(jì)算時(shí)間復(fù)雜性4
算法實(shí)現(xiàn)題1-1 統(tǒng)計(jì)數(shù)字問(wèn)題4
算法實(shí)現(xiàn)題1-2 字典序問(wèn)題5
算法實(shí)現(xiàn)題1-3 最多約數(shù)問(wèn)題6
算法實(shí)現(xiàn)題1-4 金幣陣列問(wèn)題8
算法實(shí)現(xiàn)題1-5 最大間隙問(wèn)題11第2章 遞歸與分治策略14
習(xí)題2-1 Hanoi 塔問(wèn)題的非遞歸算法14

算法實(shí)現(xiàn)題2-1 輸油管道問(wèn)題（習(xí)題2-30) 49

習(xí)題3-1 最長(zhǎng)單調(diào)遞增子序列76
習(xí)題3-2 最長(zhǎng)單調(diào)遞增子序列的O(nlogn)算法77
習(xí)題3-7 漂亮打印78
習(xí)題3-11 整數(shù)線性規(guī)劃問(wèn)題79
習(xí)題3-12 二維背包問(wèn)題80
習(xí)題3-14 Ackermann函數(shù)81
習(xí)題3-17 最短行駛路線83
習(xí)題3-19 最優(yōu)旅行路線83
算法實(shí)現(xiàn)題3-1 獨(dú)立任務(wù)最優(yōu)調(diào)度問(wèn)題（習(xí)題3-3) 83
算法實(shí)現(xiàn)題3-2 最少硬幣問(wèn)題（習(xí)題3-4) 85
算法實(shí)現(xiàn)題3-3 序關(guān)系計(jì)數(shù)問(wèn)題（習(xí)題3-5) 86
算法實(shí)現(xiàn)題3-4 多重冪計(jì)數(shù)問(wèn)題（習(xí)題3-6) 87

習(xí)題4-2 活動(dòng)安排問(wèn)題的貪心選擇123

算法實(shí)現(xiàn)題4-1 會(huì)場(chǎng)安排問(wèn)題（習(xí)題4-1) 128

習(xí)題5\|1 裝載問(wèn)題改進(jìn)回溯法（一）153
習(xí)題5\|2 裝載問(wèn)題改進(jìn)回溯法（二）154
習(xí)題5\|4 0-1背包問(wèn)題的最優(yōu)解155
習(xí)題5\|5 最大團(tuán)問(wèn)題的迭代回溯法156
習(xí)題5\|7 旅行售貨員問(wèn)題的費(fèi)用上界157
習(xí)題5\|8 旅行售貨員問(wèn)題的上界函數(shù)158
算法實(shí)現(xiàn)題5-1 子集和問(wèn)題（習(xí)題5-3) 159

習(xí)題6-1 0-1背包問(wèn)題的棧式分支限界法229
習(xí)題6-2 用最大堆存儲(chǔ)活結(jié)點(diǎn)的優(yōu)先隊(duì)列式分支限界法231
習(xí)題6-3 團(tuán)頂點(diǎn)數(shù)的上界234
習(xí)題6-4 團(tuán)頂點(diǎn)數(shù)改進(jìn)的上界235
習(xí)題6-5 修改解旅行售貨員問(wèn)題的分支限界法235
習(xí)題6-6 解旅行售貨員問(wèn)題的分支限界法中保存已產(chǎn)生的排列樹(shù)237
習(xí)題6-7 電路板排列問(wèn)題的隊(duì)列式分支限界法239
算法實(shí)現(xiàn)題6-1 最小長(zhǎng)度電路板排列問(wèn)題一（習(xí)題6-8) 241

習(xí)題7-1 模擬正態(tài)分布隨機(jī)變量296

算法實(shí)現(xiàn)題7-1 模平方根問(wèn)題（習(xí)題7-10) 307

習(xí)題8-1 RAM和RASP程序322


習(xí)題9-1 平面圖著色問(wèn)題的絕對(duì)近似算法336

算法實(shí)現(xiàn)題9-1 旅行售貨員問(wèn)題的近似算法（習(xí)題9-9) 346

習(xí)題10-1 算法obst的正確性365
習(xí)題10-2 矩陣連乘問(wèn)題的O(n2)時(shí)間算法365
習(xí)題10-6 貨物儲(chǔ)運(yùn)問(wèn)題的費(fèi)用371
習(xí)題10-7 Garsia算法371

第11章 在線算法設(shè)計(jì)410
習(xí)題11-1 在線算法LFU的競(jìng)爭(zhēng)性410
習(xí)題11-4 多讀寫(xiě)頭磁盤(pán)問(wèn)題的在線算法410
習(xí)題11-6 帶權(quán)頁(yè)調(diào)度問(wèn)題410
算法實(shí)現(xiàn)題11-1 最優(yōu)頁(yè)調(diào)度問(wèn)題（習(xí)題11-2) 411
算法實(shí)現(xiàn)題11-2 在線LRU頁(yè)調(diào)度（習(xí)題11-3) 414
算法實(shí)現(xiàn)題11-3 k服務(wù)問(wèn)題（習(xí)題11-5) 416
參考文獻(xiàn)422