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

目錄CONTENTS第1章算法引論1
習(xí)題11實(shí)際參數(shù)交換1
習(xí)題12方法頭簽名1
習(xí)題13數(shù)組排序判定1
習(xí)題14函數(shù)的漸近表達(dá)式2
習(xí)題15O(1)和O(2)的區(qū)別2
習(xí)題16按漸近階排列表達(dá)式2
習(xí)題17算法效率2
習(xí)題18硬件效率3
習(xí)題19函數(shù)漸近階3
習(xí)題110n!的階3
習(xí)題111平均情況下的計(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)題7
算法實(shí)現(xiàn)題15最大間隙問(wèn)題10
第2章遞歸與分治策略12
習(xí)題21Hanoi 塔問(wèn)題的非遞歸算法12
習(xí)題227個(gè)二分搜索算法13
習(xí)題23改寫二分搜索算法16
習(xí)題24大整數(shù)乘法的O(nmlog(3/2))算法16
習(xí)題255次n/3位整數(shù)的乘法17
習(xí)題26矩陣乘法19
習(xí)題27多項(xiàng)式乘積19
習(xí)題28不動(dòng)點(diǎn)問(wèn)題的O(logn)時(shí)間算法19
習(xí)題29主元素問(wèn)題的線性時(shí)間算法19目錄算法設(shè)計(jì)與分析習(xí)題解答（第4版）習(xí)題210無(wú)序集主元素問(wèn)題的線性時(shí)間算法20
習(xí)題211O(1)空間子數(shù)組換位算法20
習(xí)題212O(1)空間合并算法22
習(xí)題213n段合并排序算法28
習(xí)題214自然合并排序算法29
習(xí)題215最大值和最小值問(wèn)題的最優(yōu)算法31
習(xí)題216最大值和次大值問(wèn)題的最優(yōu)算法31
習(xí)題217整數(shù)集合排序32
習(xí)題218第k小元素問(wèn)題的計(jì)算時(shí)間下界32
習(xí)題219非增序快速排序算法33
習(xí)題220隨機(jī)化算法34
習(xí)題221隨機(jī)化快速排序算法34
習(xí)題222隨機(jī)排列算法34
習(xí)題223算法qSort中的尾遞歸34
習(xí)題224用棧模擬遞歸34
習(xí)題225算法select中的元素劃分35
習(xí)題226O(nlogn)時(shí)間快速排序算法35
習(xí)題227最接近中位數(shù)的k個(gè)數(shù)36
習(xí)題228X和Y的中位數(shù)36
習(xí)題229網(wǎng)絡(luò)開(kāi)關(guān)設(shè)計(jì)36
習(xí)題230帶權(quán)中位數(shù)問(wèn)題37
習(xí)題231構(gòu)造Gray碼的分治算法39
習(xí)題232網(wǎng)球循環(huán)賽日程表40
算法實(shí)現(xiàn)題21輸油管道問(wèn)題44
算法實(shí)現(xiàn)題22眾數(shù)問(wèn)題44
算法實(shí)現(xiàn)題23郵局選址問(wèn)題45
算法實(shí)現(xiàn)題24馬的Hamilton周游路線問(wèn)題46
算法實(shí)現(xiàn)題25半數(shù)集問(wèn)題54
算法實(shí)現(xiàn)題26半數(shù)單集問(wèn)題55
算法實(shí)現(xiàn)題27士兵站隊(duì)問(wèn)題56
算法實(shí)現(xiàn)題28有重復(fù)元素的排列問(wèn)題57
算法實(shí)現(xiàn)題29排列的字典序問(wèn)題58
算法實(shí)現(xiàn)題210集合劃分問(wèn)題（一）60
算法實(shí)現(xiàn)題211集合劃分問(wèn)題（二）61
算法實(shí)現(xiàn)題212雙色Hanoi塔問(wèn)題62
算法實(shí)現(xiàn)題213標(biāo)準(zhǔn)二維表問(wèn)題64
算法實(shí)現(xiàn)題214整數(shù)因子分解問(wèn)題64
算法實(shí)現(xiàn)題215有向直線2中值問(wèn)題65
第3章動(dòng)態(tài)規(guī)劃68
習(xí)題31最長(zhǎng)單調(diào)遞增子序列68
習(xí)題32最長(zhǎng)單調(diào)遞增子序列的O(nlogn)算法69
習(xí)題33漂亮打印70
習(xí)題34整數(shù)線性規(guī)劃問(wèn)題71
習(xí)題35二維背包問(wèn)題71
習(xí)題36Ackermann函數(shù)72
算法實(shí)現(xiàn)題31獨(dú)立任務(wù)最優(yōu)調(diào)度問(wèn)題74
算法實(shí)現(xiàn)題32最少硬幣問(wèn)題76
算法實(shí)現(xiàn)題33序關(guān)系計(jì)數(shù)問(wèn)題77
算法實(shí)現(xiàn)題34多重冪計(jì)數(shù)問(wèn)題77
算法實(shí)現(xiàn)題35最小m段和問(wèn)題78
算法實(shí)現(xiàn)題36石子合并問(wèn)題79
算法實(shí)現(xiàn)題37數(shù)字三角形問(wèn)題81
算法實(shí)現(xiàn)題38乘法表問(wèn)題82
算法實(shí)現(xiàn)題39租用游艇問(wèn)題83
算法實(shí)現(xiàn)題310汽車加油行駛問(wèn)題84
算法實(shí)現(xiàn)題311圈乘運(yùn)算問(wèn)題85
算法實(shí)現(xiàn)題312最少費(fèi)用購(gòu)物91
算法實(shí)現(xiàn)題313最大長(zhǎng)方體問(wèn)題93
算法實(shí)現(xiàn)題314正則表達(dá)式匹配問(wèn)題94
算法實(shí)現(xiàn)題315雙調(diào)旅行售貨員問(wèn)題98
算法實(shí)現(xiàn)題316最大k乘積問(wèn)題100
第4章貪心算法102
習(xí)題41活動(dòng)安排問(wèn)題的貪心選擇102
習(xí)題42背包問(wèn)題的貪心選擇性質(zhì)102
習(xí)題43特殊的01背包問(wèn)題103
習(xí)題44程序最優(yōu)存儲(chǔ)問(wèn)題103
習(xí)題45最優(yōu)裝載問(wèn)題的貪心算法103
習(xí)題46Fibonacci序列的Huffman編碼104
習(xí)題47最優(yōu)前綴碼的編碼序列104
習(xí)題48任務(wù)集獨(dú)立性問(wèn)題104
習(xí)題49矩陣擬陣104
習(xí)題410最小權(quán)最大獨(dú)立子集擬陣105
習(xí)題411整數(shù)邊權(quán)Prim算法105
習(xí)題412最大權(quán)最小生成樹(shù)105
習(xí)題413最短路徑的負(fù)邊權(quán)105
習(xí)題414整數(shù)邊權(quán)Dijkstra算法106
算法實(shí)現(xiàn)題41會(huì)場(chǎng)安排問(wèn)題106
算法實(shí)現(xiàn)題42最優(yōu)合并問(wèn)題108
算法實(shí)現(xiàn)題43磁帶最優(yōu)存儲(chǔ)問(wèn)題108
算法實(shí)現(xiàn)題44磁盤文件最優(yōu)存儲(chǔ)問(wèn)題109
算法實(shí)現(xiàn)題45程序存儲(chǔ)問(wèn)題110
算法實(shí)現(xiàn)題46最優(yōu)服務(wù)次序問(wèn)題111
算法實(shí)現(xiàn)題47多處最優(yōu)服務(wù)次序問(wèn)題112
算法實(shí)現(xiàn)題48d森林問(wèn)題113
算法實(shí)現(xiàn)題49汽車加油問(wèn)題114
算法實(shí)現(xiàn)題410區(qū)間覆蓋問(wèn)題115
算法實(shí)現(xiàn)題411硬幣找錢問(wèn)題116
算法實(shí)現(xiàn)題412刪數(shù)問(wèn)題116
算法實(shí)現(xiàn)題413數(shù)列極差問(wèn)題117
算法實(shí)現(xiàn)題414嵌套箱問(wèn)題118
算法實(shí)現(xiàn)題415套匯問(wèn)題119
算法實(shí)現(xiàn)題416信號(hào)增強(qiáng)裝置問(wèn)題120
算法實(shí)現(xiàn)題417磁帶最大利用率問(wèn)題121
算法實(shí)現(xiàn)題418非單位時(shí)間任務(wù)安排問(wèn)題122
算法實(shí)現(xiàn)題419多元Huffman編碼問(wèn)題124
算法實(shí)現(xiàn)題420多元Huffman編碼變形125
算法實(shí)現(xiàn)題421區(qū)間相交問(wèn)題127
算法實(shí)現(xiàn)題422任務(wù)時(shí)間表問(wèn)題128
第5章回溯法129
習(xí)題5\\|1裝載問(wèn)題改進(jìn)回溯法（一）129
習(xí)題5\\|2裝載問(wèn)題改進(jìn)回溯法（二）130
習(xí)題5\\|301背包問(wèn)題的最優(yōu)解130
習(xí)題5\\|4最大團(tuán)問(wèn)題的迭代回溯法131
習(xí)題5\\|5旅行售貨員問(wèn)題的費(fèi)用上界132
習(xí)題5\\|6旅行售貨員問(wèn)題的上界函數(shù)134
算法實(shí)現(xiàn)題5\\|1子集和問(wèn)題134
算法實(shí)現(xiàn)題5\\|2最小長(zhǎng)度電路板排列問(wèn)題135
算法實(shí)現(xiàn)題5\\|3最小重量機(jī)器設(shè)計(jì)問(wèn)題138
算法實(shí)現(xiàn)題5\\|4運(yùn)動(dòng)員最佳匹配問(wèn)題139
算法實(shí)現(xiàn)題5\\|5無(wú)分隔符字典問(wèn)題140
算法實(shí)現(xiàn)題5\\|6無(wú)和集問(wèn)題142
算法實(shí)現(xiàn)題5\\|7n色方柱問(wèn)題143
算法實(shí)現(xiàn)題5\\|8整數(shù)變換問(wèn)題147
算法實(shí)現(xiàn)題5\\|9拉丁矩陣問(wèn)題148
算法實(shí)現(xiàn)題5\\|10排列寶石問(wèn)題150
算法實(shí)現(xiàn)題5\\|11重復(fù)拉丁矩陣問(wèn)題152
算法實(shí)現(xiàn)題5\\|12羅密歐與朱麗葉的迷宮問(wèn)題154
算法實(shí)現(xiàn)題5\\|13工作分配問(wèn)題156
算法實(shí)現(xiàn)題5\\|14獨(dú)立鉆石跳棋問(wèn)題157
算法實(shí)現(xiàn)題5\\|15智力拼圖問(wèn)題163
算法實(shí)現(xiàn)題5\\|16布線問(wèn)題170
算法實(shí)現(xiàn)題5\\|17最佳調(diào)度問(wèn)題171
算法實(shí)現(xiàn)題5\\|18無(wú)優(yōu)先級(jí)運(yùn)算問(wèn)題172
算法實(shí)現(xiàn)題5\\|19世界名畫陳列館問(wèn)題174
算法實(shí)現(xiàn)題5\\|20世界名畫陳列館問(wèn)題（不重復(fù)監(jiān)視）177
算法實(shí)現(xiàn)題5\\|21部落衛(wèi)隊(duì)問(wèn)題179
算法實(shí)現(xiàn)題5\\|22蟲(chóng)蝕算式問(wèn)題181
算法實(shí)現(xiàn)題5\\|23完備環(huán)序列問(wèn)題184
算法實(shí)現(xiàn)題5\\|24離散01串問(wèn)題186
算法實(shí)現(xiàn)題5\\|25噴漆機(jī)器人問(wèn)題188
算法實(shí)現(xiàn)題5\\|26n2-1謎問(wèn)題190
第6章分支限界法197
習(xí)題6\\|101背包問(wèn)題的棧式分支限界法197
習(xí)題6\\|2用最大堆存儲(chǔ)活結(jié)點(diǎn)的優(yōu)先隊(duì)列式分支限界法199
習(xí)題6\\|3團(tuán)頂點(diǎn)數(shù)的上界202
習(xí)題6\\|4團(tuán)頂點(diǎn)數(shù)改進(jìn)的上界202
習(xí)題6\\|5修改解旅行售貨員問(wèn)題的分支限界法202
習(xí)題6\\|6解旅行售貨員問(wèn)題的分支限界法中保存已產(chǎn)生的排列樹(shù)204
習(xí)題6\\|7電路板排列問(wèn)題的隊(duì)列式分支限界法206
算法實(shí)現(xiàn)題6\\|1最小長(zhǎng)度電路板排列問(wèn)題(一)207
算法實(shí)現(xiàn)題6\\|2最小長(zhǎng)度電路板排列問(wèn)題(二)210
算法實(shí)現(xiàn)題6\\|3最小權(quán)頂點(diǎn)覆蓋問(wèn)題213
算法實(shí)現(xiàn)題6\\|4無(wú)向圖的最大割問(wèn)題216
算法實(shí)現(xiàn)題6\\|5最小重量機(jī)器設(shè)計(jì)問(wèn)題219
算法實(shí)現(xiàn)題6\\|6運(yùn)動(dòng)員最佳匹配問(wèn)題221
算法實(shí)現(xiàn)題6\\|7n后問(wèn)題223
算法實(shí)現(xiàn)題6\\|8圓排列問(wèn)題225
算法實(shí)現(xiàn)題6\\|9布線問(wèn)題227
算法實(shí)現(xiàn)題6\\|10最佳調(diào)度問(wèn)題229
算法實(shí)現(xiàn)題6\\|11無(wú)優(yōu)先級(jí)運(yùn)算問(wèn)題232
算法實(shí)現(xiàn)題6\\|12世界名畫陳列館問(wèn)題234
算法實(shí)現(xiàn)題6\\|13騎士征途問(wèn)題237
算法實(shí)現(xiàn)題6\\|14推箱子問(wèn)題238
算法實(shí)現(xiàn)題6\\|15圖形變換問(wèn)題243
算法實(shí)現(xiàn)題6\\|16行列變換問(wèn)題246
算法實(shí)現(xiàn)題6\\|17重排n2宮問(wèn)題247
算法實(shí)現(xiàn)題6\\|18最長(zhǎng)距離問(wèn)題251
第7章概率算法257
習(xí)題71模擬正態(tài)分布隨機(jī)變量257
習(xí)題72隨機(jī)抽樣算法258
習(xí)題73隨機(jī)產(chǎn)生m個(gè)整數(shù)258
習(xí)題74集合大小的概率算法259
習(xí)題75生日問(wèn)題259
習(xí)題76易驗(yàn)證問(wèn)題的拉斯維加斯算法260
習(xí)題77用數(shù)組模擬有序鏈表261
習(xí)題78O(n3/2)舍伍德型排序算法261
習(xí)題79n后問(wèn)題解的存在性261
習(xí)題710整數(shù)因子分解算法262
習(xí)題711非蒙特卡羅算法的例子263
習(xí)題712重復(fù)3次的蒙特卡羅算法264
習(xí)題713集合隨機(jī)元素算法264
習(xí)題714由蒙特卡羅算法構(gòu)造拉斯維加斯算法265
習(xí)題715產(chǎn)生素?cái)?shù)算法266
習(xí)題716矩陣方程問(wèn)題266
算法實(shí)現(xiàn)題71模平方根問(wèn)題267
算法實(shí)現(xiàn)題72集合相等問(wèn)題268
算法實(shí)現(xiàn)題73逆矩陣問(wèn)題269
算法實(shí)現(xiàn)題74多項(xiàng)式乘積問(wèn)題270
算法實(shí)現(xiàn)題75皇后控制問(wèn)題270
算法實(shí)現(xiàn)題763SAT問(wèn)題273
算法實(shí)現(xiàn)題77戰(zhàn)車問(wèn)題274
算法實(shí)現(xiàn)題78圓排列問(wèn)題276
算法實(shí)現(xiàn)題79騎士控制問(wèn)題277
算法實(shí)現(xiàn)題710騎士對(duì)攻問(wèn)題278
第8章NP完全性理論與近似算法280
習(xí)題81析取范式的可滿足性280
習(xí)題822SAT問(wèn)題的線性時(shí)間算法280
習(xí)題83整數(shù)規(guī)劃問(wèn)題281
習(xí)題84劃分問(wèn)題282
習(xí)題85最長(zhǎng)簡(jiǎn)單回路問(wèn)題283
習(xí)題86平面圖著色問(wèn)題的絕對(duì)近似算法283
習(xí)題87最優(yōu)程序存儲(chǔ)問(wèn)題284
習(xí)題88樹(shù)的最優(yōu)頂點(diǎn)覆蓋285
習(xí)題89頂點(diǎn)覆蓋算法的性能比286
習(xí)題810團(tuán)的常數(shù)性能比近似算法286
習(xí)題811售貨員問(wèn)題的常數(shù)性能比近似算法287
習(xí)題812瓶頸旅行售貨員問(wèn)題287
習(xí)題813最優(yōu)旅行售貨員回路不自相交288
習(xí)題814集合覆蓋問(wèn)題的實(shí)例289
習(xí)題815多機(jī)調(diào)度問(wèn)題的近似算法290
習(xí)題816LPT算法的最壞情況實(shí)例291
習(xí)題817多機(jī)調(diào)度問(wèn)題的多項(xiàng)式時(shí)間近似算法292
算法實(shí)現(xiàn)題81旅行售貨員問(wèn)題的近似算法292
算法實(shí)現(xiàn)題82可滿足問(wèn)題的近似算法294
算法實(shí)現(xiàn)題83最大可滿足問(wèn)題的近似算法295
算法實(shí)現(xiàn)題84子集和問(wèn)題的近似算法297
算法實(shí)現(xiàn)題85子集和問(wèn)題的完全多項(xiàng)式時(shí)間近似算法297
算法實(shí)現(xiàn)題86實(shí)現(xiàn)算法greedySetCover298
算法實(shí)現(xiàn)題87裝箱問(wèn)題的近似算法First Fit301
算法實(shí)現(xiàn)題88裝箱問(wèn)題的近似算法Best Fit303
算法實(shí)現(xiàn)題89裝箱問(wèn)題的近似算法First Fit Decreasing305
算法實(shí)現(xiàn)題810裝箱問(wèn)題的近似算法Best Fit Decreasing305
算法實(shí)現(xiàn)題811裝箱問(wèn)題的近似算法Next Fit306
第9章串與序列的算法309
習(xí)題91簡(jiǎn)單子串搜索算法最壞情況復(fù)雜性309
習(xí)題92后綴重疊問(wèn)題309
習(xí)題93改進(jìn)前綴函數(shù)310
習(xí)題94確定所有匹配位置的KMP算法311
習(xí)題95特殊情況下簡(jiǎn)單子串搜索算法的改進(jìn)311
習(xí)題96簡(jiǎn)單子串搜索算法的平均性能312
習(xí)題97帶間隙字符的模式串搜索312
習(xí)題98串接的前綴函數(shù)313
習(xí)題99串的循環(huán)旋轉(zhuǎn)314
習(xí)題910失敗函數(shù)性質(zhì)314
習(xí)題911輸出函數(shù)性質(zhì)315
習(xí)題912后綴數(shù)組類315
習(xí)題913最長(zhǎng)公共擴(kuò)展查詢316
習(xí)題914最長(zhǎng)公共擴(kuò)展性質(zhì)320
習(xí)題915后綴數(shù)組性質(zhì)320
習(xí)題916后綴數(shù)組搜索321
習(xí)題917后綴數(shù)組快速搜索322
算法實(shí)現(xiàn)題91安全基因序列問(wèn)題326
算法實(shí)現(xiàn)題92最長(zhǎng)重復(fù)子串問(wèn)題328
算法實(shí)現(xiàn)題93最長(zhǎng)回文子串問(wèn)題329
算法實(shí)現(xiàn)題94相似基因序列性問(wèn)題331
算法實(shí)現(xiàn)題95計(jì)算機(jī)病毒問(wèn)題332
算法實(shí)現(xiàn)題96帶有子串包含約束的最長(zhǎng)公共子序列問(wèn)題335
算法實(shí)現(xiàn)題97多子串排斥約束的最長(zhǎng)公共子序列問(wèn)題336
第10章算法優(yōu)化策略338
習(xí)題101算法obst的正確性338
習(xí)題102矩陣連乘問(wèn)題的O(n2)時(shí)間算法338
習(xí)題103貨物儲(chǔ)運(yùn)問(wèn)題的費(fèi)用343
習(xí)題104Garsia算法343
算法實(shí)現(xiàn)題101貨物儲(chǔ)運(yùn)問(wèn)題346
算法實(shí)現(xiàn)題102石子合并問(wèn)題346
算法實(shí)現(xiàn)題103最大運(yùn)輸費(fèi)用貨物儲(chǔ)運(yùn)問(wèn)題347
算法實(shí)現(xiàn)題104五邊形問(wèn)題349
算法實(shí)現(xiàn)題105區(qū)間圖最短路問(wèn)題352
算法實(shí)現(xiàn)題106圓弧區(qū)間最短路問(wèn)題353
算法實(shí)現(xiàn)題107雙機(jī)調(diào)度問(wèn)題353
算法實(shí)現(xiàn)題108離線最小值問(wèn)題361
算法實(shí)現(xiàn)題109最近公共祖先問(wèn)題363
算法實(shí)現(xiàn)題1010達(dá)爾文芯片問(wèn)題365
算法實(shí)現(xiàn)題1011多柱Hanoi塔問(wèn)題367
算法實(shí)現(xiàn)題1012線性時(shí)間Huffman算法370
算法實(shí)現(xiàn)題1013單機(jī)調(diào)度問(wèn)題371
算法實(shí)現(xiàn)題1014最大費(fèi)用單機(jī)調(diào)度問(wèn)題374
算法實(shí)現(xiàn)題1015飛機(jī)加油問(wèn)題377
第11章在線算法設(shè)計(jì)378
習(xí)題111在線算法LFU的競(jìng)爭(zhēng)性378
習(xí)題112多讀寫頭磁盤問(wèn)題的在線算法378
習(xí)題113帶權(quán)頁(yè)調(diào)度問(wèn)題378
算法實(shí)現(xiàn)題111最優(yōu)頁(yè)調(diào)度問(wèn)題378
算法實(shí)現(xiàn)題112在線LRU頁(yè)調(diào)度382
算法實(shí)現(xiàn)題113k服務(wù)問(wèn)題383
參考文獻(xiàn)388