算法設計與分析習題解答(第4版)

算法設計與分析習題解答(第4版)

《算法設計與分析習題解答(第4版)》是2018年11月1日清華大學出版社出版的圖書,作者是王曉東。

基本介紹

  • 中文名:算法設計與分析習題解答(第4版)
  • 作者:王曉東
  • 出版社:清華大學出版社
  • 出版時間:2018年11月1日
  • 定價:59 元
  • ISBN:9787302511069
內容簡介,圖書目錄,

內容簡介

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

圖書目錄

目錄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

相關詞條

熱門詞條

聯絡我們