掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
闖進數學世界――探秘歷史名題
-
>
中醫(yī)基礎理論
-
>
當代中國政府與政治(新編21世紀公共管理系列教材)
-
>
高校軍事課教程
-
>
思想道德與法治(2021年版)
-
>
毛澤東思想和中國特色社會主義理論體系概論(2021年版)
-
>
中醫(yī)內科學·全國中醫(yī)藥行業(yè)高等教育“十四五”規(guī)劃教材
算法設計與分析習題解答-(第4版) 版權信息
- ISBN：9787302511069
- 條形碼：9787302511069 ; 978-7-302-51106-9
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>>
算法設計與分析習題解答-(第4版) 本書特色
本書是《算法設計與分析(第4版)》配套的輔助教材，對主教材中的全部習題做了詳盡的解答，并提供了應用實驗型習題的全部測試數據。 本書的內容是對主教材深入的擴展，許多主教材中無法講述的較深入的主題通過習題的形式展現(xiàn)出來。 為了加強學生靈活運用算法設計策略解決實際問題的能力，本書將主教材中的許多習題改造成算法實現(xiàn)題，要求學生不僅設計出解決具體問題的算法，而且能上機實現(xiàn)。教學實踐反映這類算法實現(xiàn)題的教學效果非常好。 作者還結合國家級精品課程建設，進行了教材的立體化開發(fā)，包括主教材、輔助教材、實驗與設計、電子課件和教學網站建設。 本書結合原教材的內容，進一步討論和講解原教材中的重點和難點，問題分析，求解思路和方法，為讀者深刻體會問題求解的核心思想提供幫助。由于原教材的內容有一定的深度和難度，讀者在學習和解答習題過程中會遇到一定的困難，因此本書選擇了原教材的一些典型的習題和難題，給出詳細的解答和分析。本書內容豐富，觀點新穎，理論聯(lián)系實際。不僅可用作高等院校計算機科學與工程專業(yè)本科生和研究生學習計算機算法設計的輔教教材，而且也適合廣大工程技術人員和自學讀者學習參考。 本書是學習算法設計與分析的經典教材學習輔導用書，清華大學出版社配套開發(fā)了豐富的在線教學資源，可以在清華大學出版社的在線教學平臺上進行練習與測試，實現(xiàn)教學互動、智能學習。 王曉東教授力作，算法經典暢銷書新作，國家級精品課程配套教材，凝練精品課程建設成果 本書結合主教材的內容，進一步討論和講解主教材中的重點和難點，問題分析，求解思路和方法，為讀者深刻體會問題求解的核心思想提供幫助。由于原教材的內容有一定的深度和難度，讀者在學習和解答習題過程中會遇到一定的困難，因此本書選擇了原教材的一些典型的習題和難題，給出詳細的解答和分析。
算法設計與分析習題解答-(第4版) 內容簡介
本書是《算法設計與分析（第4版）》配套輔助教材。本書將結合原教材的內容，進一步討論和講解原教材中的重點和難點，問題分析，求解思路和方法，為讀者深刻體會問題求解的核心思想提供幫助。由于原教材的內容有一定的深度和難度，讀者在學習和解答習題過程中會遇到一定的困難，因此本書選擇了原教材的一些典型的習題和難題，給出詳細的解答和分析。 本書內容豐富，觀點新穎，理論聯(lián)系實際。不僅可用作高等學校計算機專業(yè)本科生和研究生學習計算機算法設計的教材，而且也適合廣大工程技術人員和自學讀者學習參考。
算法設計與分析習題解答-(第4版) 目錄
目錄CONTENTS第1章算法引論1
習題11實際參數交換1
習題12方法頭簽名1
習題13數組排序判定1
習題14函數的漸近表達式2
習題15O(1)和O(2)的區(qū)別2
習題16按漸近階排列表達式2
習題17算法效率2
習題18硬件效率3
習題19函數漸近階3
習題110n!的階3
習題111平均情況下的計算時間復雜性4
算法實現(xiàn)題11統(tǒng)計數字問題4
算法實現(xiàn)題12字典序問題5
算法實現(xiàn)題13*多約數問題6
算法實現(xiàn)題14金幣陣列問題7
算法實現(xiàn)題15*大間隙問題10
第2章遞歸與分治策略12
習題21Hanoi 塔問題的非遞歸算法12
習題227個二分搜索算法13
習題23改寫二分搜索算法16
習題24大整數乘法的O(nmlog(3/2))算法16
習題255次n/3位整數的乘法17
習題26矩陣乘法19
習題27多項式乘積19
習題28不動點問題的O(logn)時間算法19
習題29主元素問題的線性時間算法19目錄算法設計與分析習題解答（第4版）習題210無序集主元素問題的線性時間算法20
習題211O(1)空間子數組換位算法20
習題212O(1)空間合并算法22
習題213n段合并排序算法28
習題214自然合并排序算法29
習題215*大值和*小值問題的*優(yōu)算法31
習題216*大值和次大值問題的*優(yōu)算法31
習題217整數集合排序32
習題218第k小元素問題的計算時間下界32
習題219非增序快速排序算法33
習題220隨機化算法34
習題221隨機化快速排序算法34
習題222隨機排列算法34
習題223算法qSort中的尾遞歸34
習題224用棧模擬遞歸34
習題225算法select中的元素劃分35
習題226O(nlogn)時間快速排序算法35
習題227*接近中位數的k個數36
習題228X和Y的中位數36
習題229網絡開關設計36
習題230帶權中位數問題37
習題231構造Gray碼的分治算法39
習題232網球循環(huán)賽日程表40
算法實現(xiàn)題21輸油管道問題44
算法實現(xiàn)題22眾數問題44
算法實現(xiàn)題23郵局選址問題45
算法實現(xiàn)題24馬的Hamilton周游路線問題46
算法實現(xiàn)題25半數集問題54
算法實現(xiàn)題26半數單集問題55
算法實現(xiàn)題27士兵站隊問題56
算法實現(xiàn)題28有重復元素的排列問題57
算法實現(xiàn)題29排列的字典序問題58
算法實現(xiàn)題210集合劃分問題（一）60
算法實現(xiàn)題211集合劃分問題（二）61
算法實現(xiàn)題212雙色Hanoi塔問題62
算法實現(xiàn)題213標準二維表問題64
算法實現(xiàn)題214整數因子分解問題64
算法實現(xiàn)題215有向直線2中值問題65
第3章動態(tài)規(guī)劃68
習題31*長單調遞增子序列68
習題32*長單調遞增子序列的O(nlogn)算法69
習題33漂亮打印70
習題34整數線性規(guī)劃問題71
習題35二維背包問題71
習題36Ackermann函數72
算法實現(xiàn)題31獨立任務*優(yōu)調度問題74
算法實現(xiàn)題32*少硬幣問題76
算法實現(xiàn)題33序關系計數問題77
算法實現(xiàn)題34多重冪計數問題77
算法實現(xiàn)題35*小m段和問題78
算法實現(xiàn)題36石子合并問題79
算法實現(xiàn)題37數字三角形問題81
算法實現(xiàn)題38乘法表問題82
算法實現(xiàn)題39租用游艇問題83
算法實現(xiàn)題310汽車加油行駛問題84
算法實現(xiàn)題311圈乘運算問題85
算法實現(xiàn)題312*少費用購物91
算法實現(xiàn)題313*大長方體問題93
算法實現(xiàn)題314正則表達式匹配問題94
算法實現(xiàn)題315雙調旅行售貨員問題98
算法實現(xiàn)題316*大k乘積問題100
第4章貪心算法102
習題41活動安排問題的貪心選擇102
習題42背包問題的貪心選擇性質102
習題43特殊的01背包問題103
習題44程序*優(yōu)存儲問題103
習題45*優(yōu)裝載問題的貪心算法103
習題46Fibonacci序列的Huffman編碼104
習題47*優(yōu)前綴碼的編碼序列104
習題48任務集獨立性問題104
習題49矩陣擬陣104
習題410*小權*大獨立子集擬陣105
習題411整數邊權Prim算法105
習題412*大權*小生成樹105
習題413*短路徑的負邊權105
習題414整數邊權Dijkstra算法106
算法實現(xiàn)題41會場安排問題106
算法實現(xiàn)題42*優(yōu)合并問題108
算法實現(xiàn)題43磁帶*優(yōu)存儲問題108
算法實現(xiàn)題44磁盤文件*優(yōu)存儲問題109
算法實現(xiàn)題45程序存儲問題110
算法實現(xiàn)題46*優(yōu)服務次序問題111
算法實現(xiàn)題47多處*優(yōu)服務次序問題112
算法實現(xiàn)題48d森林問題113
算法實現(xiàn)題49汽車加油問題114
算法實現(xiàn)題410區(qū)間覆蓋問題115
算法實現(xiàn)題411硬幣找錢問題116
算法實現(xiàn)題412刪數問題116
算法實現(xiàn)題413數列極差問題117
算法實現(xiàn)題414嵌套箱問題118
算法實現(xiàn)題415套匯問題119
算法實現(xiàn)題416信號增強裝置問題120
算法實現(xiàn)題417磁帶*大利用率問題121
算法實現(xiàn)題418非單位時間任務安排問題122
算法實現(xiàn)題419多元Huffman編碼問題124
算法實現(xiàn)題420多元Huffman編碼變形125
算法實現(xiàn)題421區(qū)間相交問題127
算法實現(xiàn)題422任務時間表問題128
第5章回溯法129
習題5\|1裝載問題改進回溯法（一）129
習題5\|2裝載問題改進回溯法（二）130
習題5\|301背包問題的*優(yōu)解130
習題5\|4*大團問題的迭代回溯法131
習題5\|5旅行售貨員問題的費用上界132
習題5\|6旅行售貨員問題的上界函數134
算法實現(xiàn)題5\|1子集和問題134
算法實現(xiàn)題5\|2*小長度電路板排列問題135
算法實現(xiàn)題5\|3*小重量機器設計問題138
算法實現(xiàn)題5\|4運動員*佳匹配問題139
算法實現(xiàn)題5\|5無分隔符字典問題140
算法實現(xiàn)題5\|6無和集問題142
算法實現(xiàn)題5\|7n色方柱問題143
算法實現(xiàn)題5\|8整數變換問題147
算法實現(xiàn)題5\|9拉丁矩陣問題148
算法實現(xiàn)題5\|10排列寶石問題150
算法實現(xiàn)題5\|11重復拉丁矩陣問題152
算法實現(xiàn)題5\|12羅密歐與朱麗葉的迷宮問題154
算法實現(xiàn)題5\|13工作分配問題156
算法實現(xiàn)題5\|14獨立鉆石跳棋問題157
算法實現(xiàn)題5\|15智力拼圖問題163
算法實現(xiàn)題5\|16布線問題170
算法實現(xiàn)題5\|17*佳調度問題171
算法實現(xiàn)題5\|18無優(yōu)先級運算問題172
算法實現(xiàn)題5\|19世界名畫陳列館問題174
算法實現(xiàn)題5\|20世界名畫陳列館問題（不重復監(jiān)視）177
算法實現(xiàn)題5\|21部落衛(wèi)隊問題179
算法實現(xiàn)題5\|22蟲蝕算式問題181
算法實現(xiàn)題5\|23完備環(huán)序列問題184
算法實現(xiàn)題5\|24離散01串問題186
算法實現(xiàn)題5\|25噴漆機器人問題188
算法實現(xiàn)題5\|26n2-1謎問題190
第6章分支限界法197
習題6\|101背包問題的棧式分支限界法197
習題6\|2用*大堆存儲活結點的優(yōu)先隊列式分支限界法199
習題6\|3團頂點數的上界202
習題6\|4團頂點數改進的上界202
習題6\|5修改解旅行售貨員問題的分支限界法202
習題6\|6解旅行售貨員問題的分支限界法中保存已產生的排列樹204
習題6\|7電路板排列問題的隊列式分支限界法206
算法實現(xiàn)題6\|1*小長度電路板排列問題(一)207
算法實現(xiàn)題6\|2*小長度電路板排列問題(二)210
算法實現(xiàn)題6\|3*小權頂點覆蓋問題213
算法實現(xiàn)題6\|4無向圖的*大割問題216
算法實現(xiàn)題6\|5*小重量機器設計問題219
算法實現(xiàn)題6\|6運動員*佳匹配問題221
算法實現(xiàn)題6\|7n后問題223
算法實現(xiàn)題6\|8圓排列問題225
算法實現(xiàn)題6\|9布線問題227
算法實現(xiàn)題6\|10*佳調度問題229
算法實現(xiàn)題6\|11無優(yōu)先級運算問題232
算法實現(xiàn)題6\|12世界名畫陳列館問題234
算法實現(xiàn)題6\|13騎士征途問題237
算法實現(xiàn)題6\|14推箱子問題238
算法實現(xiàn)題6\|15圖形變換問題243
算法實現(xiàn)題6\|16行列變換問題246
算法實現(xiàn)題6\|17重排n2宮問題247
算法實現(xiàn)題6\|18*長距離問題251
第7章概率算法257
習題71模擬正態(tài)分布隨機變量257
習題72隨機抽樣算法258
習題73隨機產生m個整數258
習題74集合大小的概率算法259
習題75生日問題259
習題76易驗證問題的拉斯維加斯算法260
習題77用數組模擬有序鏈表261
習題78O(n3/2)舍伍德型排序算法261
習題79n后問題解的存在性261
習題710整數因子分解算法262
習題711非蒙特卡羅算法的例子263
習題712重復3次的蒙特卡羅算法264
習題713集合隨機元素算法264
習題714由蒙特卡羅算法構造拉斯維加斯算法265
習題715產生素數算法266
習題716矩陣方程問題266
算法實現(xiàn)題71模平方根問題267
算法實現(xiàn)題72集合相等問題268
算法實現(xiàn)題73逆矩陣問題269
算法實現(xiàn)題74多項式乘積問題270
算法實現(xiàn)題75皇后控制問題270
算法實現(xiàn)題763SAT問題273
算法實現(xiàn)題77戰(zhàn)車問題274
算法實現(xiàn)題78圓排列問題276
算法實現(xiàn)題79騎士控制問題277
算法實現(xiàn)題710騎士對攻問題278
第8章NP完全性理論與近似算法280
習題81析取范式的可滿足性280
習題822SAT問題的線性時間算法280
習題83整數規(guī)劃問題281
習題84劃分問題282
習題85*長簡單回路問題283
習題86平面圖著色問題的絕對近似算法283
習題87*優(yōu)程序存儲問題284
習題88樹的*優(yōu)頂點覆蓋285
習題89頂點覆蓋算法的性能比286
習題810團的常數性能比近似算法286
習題811售貨員問題的常數性能比近似算法287
習題812瓶頸旅行售貨員問題287
習題813*優(yōu)旅行售貨員回路不自相交288
習題814集合覆蓋問題的實例289
習題815多機調度問題的近似算法290
習題816LPT算法的*壞情況實例291
習題817多機調度問題的多項式時間近似算法292
算法實現(xiàn)題81旅行售貨員問題的近似算法292
算法實現(xiàn)題82可滿足問題的近似算法294
算法實現(xiàn)題83*大可滿足問題的近似算法295
算法實現(xiàn)題84子集和問題的近似算法297
算法實現(xiàn)題85子集和問題的完全多項式時間近似算法297
算法實現(xiàn)題86實現(xiàn)算法greedySetCover298
算法實現(xiàn)題87裝箱問題的近似算法First Fit301
算法實現(xiàn)題88裝箱問題的近似算法Best Fit303
算法實現(xiàn)題89裝箱問題的近似算法First Fit Decreasing305
算法實現(xiàn)題810裝箱問題的近似算法Best Fit Decreasing305
算法實現(xiàn)題811裝箱問題的近似算法Next Fit306
第9章串與序列的算法309
習題91簡單子串搜索算法*壞情況復雜性309
習題92后綴重疊問題309
習題93改進前綴函數310
習題94確定所有匹配位置的KMP算法311
習題95特殊情況下簡單子串搜索算法的改進311
習題96簡單子串搜索算法的平均性能312
習題97帶間隙字符的模式串搜索312
習題98串接的前綴函數313
習題99串的循環(huán)旋轉314
習題910失敗函數性質314
習題911輸出函數性質315
習題912后綴數組類315
習題913*長公共擴展查詢316
習題914*長公共擴展性質320
習題915后綴數組性質320
習題916后綴數組搜索321
習題917后綴數組快速搜索322
算法實現(xiàn)題91安全基因序列問題326
算法實現(xiàn)題92*長重復子串問題328
算法實現(xiàn)題93*長回文子串問題329
算法實現(xiàn)題94相似基因序列性問題331
算法實現(xiàn)題95計算機病毒問題332
算法實現(xiàn)題96帶有子串包含約束的*長公共子序列問題335
算法實現(xiàn)題97多子串排斥約束的*長公共子序列問題336
第10章算法優(yōu)化策略338
習題101算法obst的正確性338
習題102矩陣連乘問題的O(n2)時間算法338
習題103貨物儲運問題的費用343
習題104Garsia算法343
算法實現(xiàn)題101貨物儲運問題346
算法實現(xiàn)題102石子合并問題346
算法實現(xiàn)題103*大運輸費用貨物儲運問題347
算法實現(xiàn)題104五邊形問題349
算法實現(xiàn)題105區(qū)間圖*短路問題352
算法實現(xiàn)題106圓弧區(qū)間*短路問題353
算法實現(xiàn)題107雙機調度問題353
算法實現(xiàn)題108離線*小值問題361
算法實現(xiàn)題109*近公共祖先問題363
算法實現(xiàn)題1010達爾文芯片問題365
算法實現(xiàn)題1011多柱Hanoi塔問題367
算法實現(xiàn)題1012線性時間Huffman算法370
算法實現(xiàn)題1013單機調度問題371
算法實現(xiàn)題1014*大費用單機調度問題374
算法實現(xiàn)題1015飛機加油問題377
第11章在線算法設計378
習題111在線算法LFU的競爭性378
習題112多讀寫頭磁盤問題的在線算法378
習題113帶權頁調度問題378
算法實現(xiàn)題111*優(yōu)頁調度問題378
算法實現(xiàn)題112在線LRU頁調度382
算法實現(xiàn)題113k服務問題383
參考文獻388
展開全部
算法設計與分析習題解答-(第4版) 節(jié)選
可用歸納設計策略解此問題。歸納假設是： 已知計算序列a［0:i-1］(i 用歸納設計策略解題時，歸納假設對應于算法循環(huán)中的循環(huán)不變式。本題的循環(huán)不變式P是： P: k是序列a［0:i］ 的*長遞增子序列的長度，0≤i 容易看出在由i-1到i的循環(huán)中，a［i］的值起關鍵作用。如果a［i］能擴展序列a［0:i-1］的*長遞增子序列的長度，則k=k+1，否則k不變。設a［0:i-1］的長度為k的*長遞增子序列的結尾元素是a［j］(0≤j≤i-1)，則當a［i］≥a［j］時可以擴展，否則不能擴展。如果序列a［0:i-1］中有多個長度為k的*長遞增子序列，那么需要存儲哪些信息？容易看出，只要存儲序列a［0:i-1］中所有長度為k的遞增子序列中結尾元素的*小值b［k］即可。因此，需要將循環(huán)不變式P增強為： P: 0≤i b［k］是序列a［0:i］中所有長度為k的遞增子序列中的*小結尾元素值。動態(tài)規(guī)劃第 3 章算法設計與分析習題解答（第4版） 相應的歸納假設也增強為： 已知計算序列a［0:i-1］(i 增強歸納假設后，在由i-1到i的循環(huán)中，當a［i］≥b［k］時，k=k+1，b［k］=a［i］,否則k值不變。注意到當a［i］≥b［k］時,k值增加，b［k］的值為a［i］。那么當a［i］ 按上述思想設計的算法可實現(xiàn)如下：public static int LIS() { int i=1,k; b［1］=a［0］; for (i=1,k=1;i { if (a［i］＞=b［k］) b［++k］=a［i］; else b［binary(i,k)］=a［i］; } return k; }static int binary(int i, int k) { int h,j; if (a［i］ for(h=1, j=k; h!=j-1;) { if (b［k=(h+j)/2］＜=a［i］) h=k; else j=k; } return j; }binary(i,k)用二分搜索算法在b［1:k］中找到下標j，使得b［j-1］≤a［i］ 給定由n個英文單詞組成的一段文章，每個單詞的長度(字符個數)依序為l1，l2，…,ln。要在一臺打印機上將這段文章“漂亮”地打印出來。打印機每行*多可打印M個字符。這里所說的“漂亮”的定義如下： 在打印機所打印的每一行中，行首和行尾可不留空格；行中每兩個單詞之間留一個空格；如果在一行中打印從單詞i到單詞j的字符，則按打印規(guī)則，應在一行中恰好打印∑jk=ilk+j－i個字符(包括字間空格字符)，且不允許將單詞打破。多余的空格數為M－j+i－∑jk=ilk；除文章的*后一行外，希望每行多余的空格數盡可能少。因此，以各行(*后一行除外)的多余空格數的立方和達到*小作為“漂亮”的標準。試用動態(tài)規(guī)劃算法設計一個“漂亮打印”方案，并分析算法的計算復雜性。
算法設計與分析習題解答-(第4版) 作者簡介
王曉東,教授，博士生導師。近年來正式出版學術著作11部。近年在國內外學術刊物上發(fā)表學術論文60多篇。參加多項科研項目并獲獎。其中獲國家科技進步二等獎一項，水電部科技進步一等獎一項，福建省科技進步三等獎一項，省水電廳科技進步一等獎一項。
書友推薦
- >
隨園食單
- >
詩經-先民的歌唱
- >
大紅狗在馬戲團-大紅狗克里弗-助人
- >
回憶愛瑪儂
- >
推拿
- >
人文閱讀與收藏·良友文學叢書:一天的工作
- >
小考拉的故事-套裝共3冊
- >
李白與唐代文化
本類暢銷
