算法設計與分析習題解答（第4版）

本書是《算法設計與分析（第4版）》配套輔助教材。本書將結合原教材的內容，進一步討論和講解原教材中的重點和難點，問題分析，求解思路和方法，為讀者深刻體會問題求解的核心思想提供幫助。由於原教材的內容有一定的深度和難度，讀者在學習和解答習題過程中會遇到一定的困難，因此本書選擇了原教材的一些典型的習題和難題，給出詳細的解答和分析。本書內容豐富，觀點新穎，理論聯繫實際。不僅可用作高等學校計算機專業本科生和研究生學習計算機算法設計的教材，而且也適合廣大工程技術人員和自學讀者學習參考。 ^[1] 

目錄CONTENTS第1章算法引論1

習題11實際參數交換1

習題12方法頭簽名1

習題13數組排序判定1

習題14函數的漸近表達式2

習題15O(1)和O(2)的區別2

習題16按漸近階排列表達式2

習題17算法效率2

習題18硬件效率3

習題19函數漸近階3

習題110n!的階3

習題111平均情況下的計算時間複雜性4

算法實現題11統計數字問題4

算法實現題12字典序問題5

算法實現題13最多約數問題6

算法實現題14金幣陣列問題7

算法實現題15最大間隙問題10

第2章遞歸與分治策略12

習題21Hanoi塔問題的非遞歸算法12

習題227個二分搜索算法13

習題23改寫二分搜索算法16

習題24大整數乘法的O(nmlog(3/2))算法16

習題255次n/3位整數的乘法17

習題26矩陣乘法19

習題27多項式乘積19

習題28不動點問題的O(logn)時間算法19

習題29主元素問題的線性時間算法19目錄算法設計與分析習題解答（第4版）習題210無序集主元素問題的線性時間算法20

習題211O(1)空間子數組換位算法20

習題212O(1)空間合併算法22

習題213n段合併排序算法28

習題214自然合併排序算法29

習題215最大值和最小值問題的最優算法31

習題216最大值和次大值問題的最優算法31

習題217整數集合排序32

習題218第k小元素問題的計算時間下界32

習題219非增序快速排序算法33

習題220隨機化算法34

習題221隨機化快速排序算法34

習題222隨機排列算法34

習題223算法qSort中的尾遞歸34

習題224用棧模擬遞歸34

習題225算法select中的元素劃分35

習題226O(nlogn)時間快速排序算法35

習題227最接近中位數的k個數36

習題228X和Y的中位數36

習題229網絡開關設計36

習題230帶權中位數問題37

習題231構造Gray碼的分治算法39

習題232網球循環賽日程表40

算法實現題21輸油管道問題44

算法實現題22眾數問題44

算法實現題23郵局選址問題45

算法實現題24馬的Hamilton周遊路線問題46

算法實現題25半數集問題54

算法實現題26半數單集問題55

算法實現題27士兵站隊問題56

算法實現題28有重複元素的排列問題57

算法實現題29排列的字典序問題58

算法實現題210集合劃分問題（一）60

算法實現題211集合劃分問題（二）61

算法實現題212雙色Hanoi塔問題62

算法實現題213標準二維表問題64

算法實現題214整數因子分解問題64

算法實現題215有向直線2中值問題65

第3章動態規劃68

習題31最長單調遞增子序列68

習題32最長單調遞增子序列的O(nlogn)算法69

習題33漂亮打印70

習題34整數線性規劃問題71

習題35二維揹包問題71

習題36Ackermann函數72

算法實現題31獨立任務最優調度問題74

算法實現題32最少硬幣問題76

算法實現題33序關係計數問題77

算法實現題34多重冪計數問題77

算法實現題35最小m段和問題78

算法實現題36石子合併問題79

算法實現題37數字三角形問題81

算法實現題38乘法表問題82

算法實現題39租用遊艇問題83

算法實現題310汽車加油行駛問題84

算法實現題311圈乘運算問題85

算法實現題312最少費用購物91

算法實現題313最大長方體問題93

算法實現題314正則表達式匹配問題94

算法實現題315雙調旅行售貨員問題98

算法實現題316最大k乘積問題100

第4章貪心算法102

習題41活動安排問題的貪心選擇102

習題42揹包問題的貪心選擇性質102

習題43特殊的01揹包問題103

習題44程序最優存儲問題103

習題45最優裝載問題的貪心算法103

習題46Fibonacci序列的Huffman編碼104

習題47最優前綴碼的編碼序列104

習題48任務集獨立性問題104

習題49矩陣擬陣104

習題410最小權最大獨立子集擬陣105

習題411整數邊權Prim算法105

習題412最大權最小生成樹105

習題413最短路徑的負邊權105

習題414整數邊權Dijkstra算法106

算法實現題41會場安排問題106

算法實現題42最優合併問題108

算法實現題43磁帶最優存儲問題108

算法實現題44磁盤文件最優存儲問題109

算法實現題45程序存儲問題110

算法實現題46最優服務次序問題111

算法實現題47多處最優服務次序問題112

算法實現題48d森林問題113

算法實現題49汽車加油問題114

算法實現題410區間覆蓋問題115

算法實現題411硬幣找錢問題116

算法實現題412刪數問題116

算法實現題413數列極差問題117

算法實現題414嵌套箱問題118

算法實現題415套匯問題119

算法實現題416信號增強裝置問題120

算法實現題417磁帶最大利用率問題121

算法實現題418非單位時間任務安排問題122

算法實現題419多元Huffman編碼問題124

算法實現題420多元Huffman編碼變形125

算法實現題421區間相交問題127

算法實現題422任務時間表問題128

第5章回溯法129

習題5\|1裝載問題改進回溯法（一）129

習題5\|2裝載問題改進回溯法（二）130

習題5\|301揹包問題的最優解130

習題5\|4最大團問題的迭代回溯法131

習題5\|5旅行售貨員問題的費用上界132

習題5\|6旅行售貨員問題的上界函數134

算法實現題5\|1子集和問題134

算法實現題5\|2最小長度電路板排列問題135

算法實現題5\|3最小重量機器設計問題138

算法實現題5\|4運動員最佳匹配問題139

算法實現題5\|5無分隔符字典問題140

算法實現題5\|6無和集問題142

算法實現題5\|7n色方柱問題143

算法實現題5\|8整數變換問題147

算法實現題5\|9拉丁矩陣問題148

算法實現題5\|10排列寶石問題150

算法實現題5\|11重複拉丁矩陣問題152

算法實現題5\|12羅密歐與朱麗葉的迷宮問題154

算法實現題5\|13工作分配問題156

算法實現題5\|14獨立鑽石跳棋問題157

算法實現題5\|15智力拼圖問題163

算法實現題5\|16佈線問題170

算法實現題5\|17最佳調度問題171

算法實現題5\|18無優先級運算問題172

算法實現題5\|19世界名畫陳列館問題174

算法實現題5\|20世界名畫陳列館問題（不重複監視）177

算法實現題5\|21部落衞隊問題179

算法實現題5\|22蟲蝕算式問題181

算法實現題5\|23完備環序列問題184

算法實現題5\|24離散01串問題186

算法實現題5\|25噴漆機器人問題188

算法實現題5\|26n2-1謎問題190

第6章分支限界法197

習題6\|101揹包問題的棧式分支限界法197

習題6\|2用最大堆存儲活結點的優先隊列式分支限界法199

習題6\|3團頂點數的上界202

習題6\|4團頂點數改進的上界202

習題6\|5修改解旅行售貨員問題的分支限界法202

習題6\|6解旅行售貨員問題的分支限界法中保存已產生的排列樹204

習題6\|7電路板排列問題的隊列式分支限界法206

算法實現題6\|1最小長度電路板排列問題(一)207

算法實現題6\|2最小長度電路板排列問題(二)210

算法實現題6\|3最小權頂點覆蓋問題213

算法實現題6\|4無向圖的最大割問題216

算法實現題6\|5最小重量機器設計問題219

算法實現題6\|6運動員最佳匹配問題221

算法實現題6\|7n後問題223

算法實現題6\|8圓排列問題225

算法實現題6\|9佈線問題227

算法實現題6\|10最佳調度問題229

算法實現題6\|11無優先級運算問題232

算法實現題6\|12世界名畫陳列館問題234

算法實現題6\|13騎士征途問題237

算法實現題6\|14推箱子問題238

算法實現題6\|15圖形變換問題243

算法實現題6\|16行列變換問題246

算法實現題6\|17重排n2宮問題247

算法實現題6\|18最長距離問題251

第7章概率算法257

習題71模擬正態分佈隨機變量257

習題72隨機抽樣算法258

習題73隨機產生m個整數258

習題74集合大小的概率算法259

習題75生日問題259

習題76易驗證問題的拉斯維加斯算法260

習題77用數組模擬有序鏈表261

習題78O(n3/2)舍伍德型排序算法261

習題79n後問題解的存在性261

習題710整數因子分解算法262

習題711非蒙特卡羅算法的例子263

習題712重複3次的蒙特卡羅算法264

習題713集合隨機元素算法264

習題714由蒙特卡羅算法構造拉斯維加斯算法265

習題715產生素數算法266

習題716矩陣方程問題266

算法實現題71模平方根問題267

算法實現題72集合相等問題268

算法實現題73逆矩陣問題269

算法實現題74多項式乘積問題270

算法實現題75皇后控制問題270

算法實現題763SAT問題273

算法實現題77戰車問題274

算法實現題78圓排列問題276

算法實現題79騎士控制問題277

算法實現題710騎士對攻問題278

第8章NP完全性理論與近似算法280

習題81析取範式的可滿足性280

習題822SAT問題的線性時間算法280

習題83整數規劃問題281

習題84劃分問題282

習題85最長簡單迴路問題283

習題86平面圖着色問題的絕對近似算法283

習題87最優程序存儲問題284

習題88樹的最優頂點覆蓋285

習題89頂點覆蓋算法的性能比286

習題810團的常數性能比近似算法286

習題811售貨員問題的常數性能比近似算法287

習題812瓶頸旅行售貨員問題287

習題813最優旅行售貨員迴路不自相交288

習題814集合覆蓋問題的實例289

習題815多機調度問題的近似算法290

習題816LPT算法的最壞情況實例291

習題817多機調度問題的多項式時間近似算法292

算法實現題81旅行售貨員問題的近似算法292

算法實現題82可滿足問題的近似算法294

算法實現題83最大可滿足問題的近似算法295

算法實現題84子集和問題的近似算法297

算法實現題85子集和問題的完全多項式時間近似算法297

算法實現題86實現算法greedySetCover298

算法實現題87裝箱問題的近似算法FirstFit301

算法實現題88裝箱問題的近似算法BestFit303

算法實現題89裝箱問題的近似算法FirstFitDecreasing305

算法實現題810裝箱問題的近似算法BestFitDecreasing305

算法實現題811裝箱問題的近似算法NextFit306

第9章串與序列的算法309

習題91簡單子串搜索算法最壞情況複雜性309

習題92後綴重疊問題309

習題93改進前綴函數310

習題94確定所有匹配位置的KMP算法311

習題95特殊情況下簡單子串搜索算法的改進311

習題96簡單子串搜索算法的平均性能312

習題97帶間隙字符的模式串搜索312

習題98串接的前綴函數313

習題99串的循環旋轉314

習題910失敗函數性質314

習題911輸出函數性質315

習題912後綴數組類315

習題913最長公共擴展查詢316

習題914最長公共擴展性質320

習題915後綴數組性質320

習題916後綴數組搜索321

習題917後綴數組快速搜索322

算法實現題91安全基因序列問題326

算法實現題92最長重複子串問題328

算法實現題93最長迴文子串問題329

算法實現題94相似基因序列性問題331

算法實現題95計算機病毒問題332

算法實現題96帶有子串包含約束的最長公共子序列問題335

算法實現題97多子串排斥約束的最長公共子序列問題336

第10章算法優化策略338

習題101算法obst的正確性338

習題102矩陣連乘問題的O(n2)時間算法338

習題103貨物儲運問題的費用343

習題104Garsia算法343

算法實現題101貨物儲運問題346

算法實現題102石子合併問題346

算法實現題103最大運輸費用貨物儲運問題347

算法實現題104五邊形問題349

算法實現題105區間圖最短路問題352

算法實現題106圓弧區間最短路問題353

算法實現題107雙機調度問題353

算法實現題108離線最小值問題361

算法實現題109最近公共祖先問題363

算法實現題1010達爾文芯片問題365

算法實現題1011多柱Hanoi塔問題367

算法實現題1012線性時間Huffman算法370

算法實現題1013單機調度問題371

算法實現題1014最大費用單機調度問題374

算法實現題1015飛機加油問題377

第11章在線算法設計378

習題111在線算法LFU的競爭性378

習題112多讀寫頭磁盤問題的在線算法378

習題113帶權頁調度問題378

算法實現題111最優頁調度問題378

算法實現題112在線LRU頁調度382

算法實現題113k服務問題383

參考文獻388 ^[2]