算法設(shè)計(jì)與分析習(xí)題解答

第1章算法引論1
習(xí)題11實(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7按漸近階排列表達(dá)式2
習(xí)題18算法效率2
習(xí)題19硬件效率3
習(xí)題110函數(shù)漸進(jìn)階3
習(xí)題111n!的階4
習(xí)題112平均情況下的計(jì)算時(shí)間復(fù)雜性4
算法實(shí)現(xiàn)題11統(tǒng)計(jì)數(shù)字問題4
算法實(shí)現(xiàn)題12字典序問題5
算法實(shí)現(xiàn)題13最多約數(shù)問題6
算法實(shí)現(xiàn)題14金幣陣列問題8
算法實(shí)現(xiàn)題15最大間隙問題11
第2章遞歸與分治策略14
習(xí)題21Hanoi 塔問題的非遞歸算法14
習(xí)題227個(gè)二分搜索算法15
習(xí)題23改寫二分搜索算法18
習(xí)題24大整數(shù)乘法的O(nmlog(3/2))算法19
習(xí)題255次n/3位整數(shù)的乘法19
習(xí)題26矩陣乘法21
習(xí)題27多項(xiàng)式乘積21
習(xí)題28不動(dòng)點(diǎn)問題的O(logn)時(shí)間算法22
習(xí)題29主元素問題的線性時(shí)間算法22
習(xí)題210無序集主元素問題的線性時(shí)間算法22
習(xí)題211O(1)空間子數(shù)組換位算法23
習(xí)題212O(1)空間合并算法25
習(xí)題213n段合并排序算法32
習(xí)題214自然合并排序算法32
習(xí)題215最大值和最小值問題的最優(yōu)算法35
習(xí)題216最大值和次大值問題的最優(yōu)算法35
習(xí)題217整數(shù)集合排序35
習(xí)題218第k小元素問題的計(jì)算時(shí)間下界36
習(xí)題219非增序快速排序算法37
習(xí)題220隨機(jī)化算法37
習(xí)題221隨機(jī)化快速排序算法38
習(xí)題222隨機(jī)排列算法38
習(xí)題223算法qSort中的尾遞歸38
習(xí)題224用棧模擬遞歸38
習(xí)題225算法select中的元素劃分39
習(xí)題226O(nlogn)時(shí)間快速排序算法40
習(xí)題227最接近中位數(shù)的k個(gè)數(shù)40
習(xí)題228X和Y的中位數(shù)40
習(xí)題229網(wǎng)絡(luò)開關(guān)設(shè)計(jì)41
習(xí)題232帶權(quán)中位數(shù)問題42
習(xí)題234構(gòu)造Gray碼的分治算法43
習(xí)題235網(wǎng)球循環(huán)賽日程表44
算法實(shí)現(xiàn)題21輸油管道問題（習(xí)題230）49
算法實(shí)現(xiàn)題22眾數(shù)問題（習(xí)題231）50
算法實(shí)現(xiàn)題23郵局選址問題（習(xí)題232）51
算法實(shí)現(xiàn)題24馬的Hamilton周游路線問題（習(xí)題233）51
算法實(shí)現(xiàn)題25半數(shù)集問題60
算法實(shí)現(xiàn)題26半數(shù)單集問題62
算法實(shí)現(xiàn)題27士兵站隊(duì)問題63
算法實(shí)現(xiàn)題28有重復(fù)元素的排列問題63
算法實(shí)現(xiàn)題29排列的字典序問題65
算法實(shí)現(xiàn)題210集合劃分問題（一）67
算法實(shí)現(xiàn)題211集合劃分問題（二）68
算法實(shí)現(xiàn)題212雙色Hanoi塔問題69
算法實(shí)現(xiàn)題213標(biāo)準(zhǔn)二維表問題71
算法實(shí)現(xiàn)題214整數(shù)因子分解問題72
算法實(shí)現(xiàn)題215有向直線2中值問題72
第3章動(dòng)態(tài)規(guī)劃76
習(xí)題31最長單調(diào)遞增子序列76
習(xí)題32最長單調(diào)遞增子序列的O(nlogn)算法77
習(xí)題37漂亮打印78
習(xí)題311整數(shù)線性規(guī)劃問題79
習(xí)題312二維背包問題80
習(xí)題314Ackermann函數(shù)81
習(xí)題317最短行駛路線83
習(xí)題319最優(yōu)旅行路線83
算法實(shí)現(xiàn)題31獨(dú)立任務(wù)最優(yōu)調(diào)度問題（習(xí)題33）83
算法實(shí)現(xiàn)題32最少硬幣問題（習(xí)題34）85
算法實(shí)現(xiàn)題33序關(guān)系計(jì)數(shù)問題（習(xí)題35）86
算法實(shí)現(xiàn)題34多重冪計(jì)數(shù)問題（習(xí)題36）87
算法實(shí)現(xiàn)題35編輯距離問題（習(xí)題38）87
算法實(shí)現(xiàn)題36石子合并問題（習(xí)題39）89
算法實(shí)現(xiàn)題37數(shù)字三角形問題（習(xí)題310）91
算法實(shí)現(xiàn)題38乘法表問題（習(xí)題313）92
算法實(shí)現(xiàn)題39租用游艇問題（習(xí)題315）93
算法實(shí)現(xiàn)題310汽車加油行駛問題（習(xí)題316）95
算法實(shí)現(xiàn)題311圈乘運(yùn)算問題（習(xí)題318）96
算法實(shí)現(xiàn)題312最少費(fèi)用購物（習(xí)題320）102
算法實(shí)現(xiàn)題313最大長方體問題（習(xí)題321）104
算法實(shí)現(xiàn)題314正則表達(dá)式匹配問題（習(xí)題322）105
算法實(shí)現(xiàn)題315雙調(diào)旅行售貨員問題（習(xí)題323）110
算法實(shí)現(xiàn)題316最大k乘積問題（習(xí)題524）111
算法實(shí)現(xiàn)題317最小m段和問題113
算法實(shí)現(xiàn)題318紅黑樹的紅色內(nèi)結(jié)點(diǎn)問題115
第4章貪心算法123
習(xí)題42活動(dòng)安排問題的貪心選擇123
習(xí)題43背包問題的貪心選擇性質(zhì)123
習(xí)題44特殊的01背包問題124
習(xí)題410程序最優(yōu)存儲問題124
習(xí)題413最優(yōu)裝載問題的貪心算法125
習(xí)題418Fibonacci序列的Huffman編碼125
習(xí)題419最優(yōu)前綴碼的編碼序列125
習(xí)題421任務(wù)集獨(dú)立性問題126
習(xí)題422矩陣擬陣126
習(xí)題423最小權(quán)最大獨(dú)立子集擬陣126
習(xí)題427整數(shù)邊權(quán)Prim算法126
習(xí)題428最大權(quán)最小生成樹127
習(xí)題429最短路徑的負(fù)邊權(quán)127
習(xí)題430整數(shù)邊權(quán)Dijkstra算法127
算法實(shí)現(xiàn)題41會(huì)場安排問題（習(xí)題41）128
算法實(shí)現(xiàn)題42最優(yōu)合并問題（習(xí)題45）129
算法實(shí)現(xiàn)題43磁帶最優(yōu)存儲問題（習(xí)題46）130
算法實(shí)現(xiàn)題44磁盤文件最優(yōu)存儲問題（習(xí)題47）131
算法實(shí)現(xiàn)題45程序存儲問題（習(xí)題48）132
算法實(shí)現(xiàn)題46最優(yōu)服務(wù)次序問題（習(xí)題411）133
算法實(shí)現(xiàn)題47多處最優(yōu)服務(wù)次序問題（習(xí)題412）134
算法實(shí)現(xiàn)題48d森林問題（習(xí)題414）135
算法實(shí)現(xiàn)題49汽車加油問題（習(xí)題416）137
算法實(shí)現(xiàn)題410區(qū)間覆蓋問題（習(xí)題417）138
算法實(shí)現(xiàn)題411硬幣找錢問題（習(xí)題424）138
算法實(shí)現(xiàn)題412刪數(shù)問題（習(xí)題425）139
算法實(shí)現(xiàn)題413數(shù)列極差問題（習(xí)題426）140
算法實(shí)現(xiàn)題414嵌套箱問題（習(xí)題431）140
算法實(shí)現(xiàn)題415套匯問題（習(xí)題432）142
算法實(shí)現(xiàn)題416信號增強(qiáng)裝置問題（習(xí)題517）143
算法實(shí)現(xiàn)題417磁帶最大利用率問題（習(xí)題49）144
算法實(shí)現(xiàn)題418非單位時(shí)間任務(wù)安排問題（習(xí)題415）145
算法實(shí)現(xiàn)題419多元Huffman編碼問題（習(xí)題420）147
算法實(shí)現(xiàn)題420多元Huffman編碼變形149
算法實(shí)現(xiàn)題421區(qū)間相交問題151
算法實(shí)現(xiàn)題422任務(wù)時(shí)間表問題151
第5章回溯法153
習(xí)題5-1裝載問題改進(jìn)回溯法1153
習(xí)題5-2裝載問題改進(jìn)回溯法2154
習(xí)題5-401背包問題的最優(yōu)解155
習(xí)題5-5最大團(tuán)問題的迭代回溯法156
習(xí)題5-7旅行售貨員問題的費(fèi)用上界157
習(xí)題5-8旅行售貨員問題的上界函數(shù)158
算法實(shí)現(xiàn)題51子集和問題（習(xí)題53）159
算法實(shí)現(xiàn)題52最小長度電路板排列問題（習(xí)題59）160
算法實(shí)現(xiàn)題53最小重量機(jī)器設(shè)計(jì)問題（習(xí)題510）163
算法實(shí)現(xiàn)題54運(yùn)動(dòng)員最佳匹配問題（習(xí)題511）164
算法實(shí)現(xiàn)題55無分隔符字典問題（習(xí)題512）165
算法實(shí)現(xiàn)題56無和集問題（習(xí)題513）167
算法實(shí)現(xiàn)題57n色方柱問題（習(xí)題514）168
算法實(shí)現(xiàn)題58整數(shù)變換問題（習(xí)題515）173
算法實(shí)現(xiàn)題59拉丁矩陣問題（習(xí)題516）175
算法實(shí)現(xiàn)題510排列寶石問題（習(xí)題516）176
算法實(shí)現(xiàn)題511重復(fù)拉丁矩陣問題（習(xí)題516）179
算法實(shí)現(xiàn)題512羅密歐與朱麗葉的迷宮問題181
算法實(shí)現(xiàn)題513工作分配問題（習(xí)題518）183
算法實(shí)現(xiàn)題514獨(dú)立鉆石跳棋問題（習(xí)題519）184
算法實(shí)現(xiàn)題515智力拼圖問題（習(xí)題520）191
算法實(shí)現(xiàn)題516布線問題（習(xí)題521）198
算法實(shí)現(xiàn)題517最佳調(diào)度問題（習(xí)題522）200
算法實(shí)現(xiàn)題518無優(yōu)先級運(yùn)算問題（習(xí)題523）201
算法實(shí)現(xiàn)題519世界名畫陳列館問題（習(xí)題525）203
算法實(shí)現(xiàn)題520世界名畫陳列館問題（不重復(fù)監(jiān)視）（習(xí)題526）207
算法實(shí)現(xiàn)題521部落衛(wèi)隊(duì)問題（習(xí)題56）209
算法實(shí)現(xiàn)題522蟲蝕算式問題211
算法實(shí)現(xiàn)題523完備環(huán)序列問題214
算法實(shí)現(xiàn)題524離散01串問題217
算法實(shí)現(xiàn)題525噴漆機(jī)器人問題218
算法實(shí)現(xiàn)題526n2-1謎問題221
第6章分支限界法229
習(xí)題6101背包問題的棧式分支限界法229
習(xí)題62用最大堆存儲活結(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修改解旅行售貨員問題的分支限界法235
習(xí)題66解旅行售貨員問題的分支限界法中保存已產(chǎn)生的排列樹237
習(xí)題67電路板排列問題的隊(duì)列式分支限界法239
算法實(shí)現(xiàn)題61最小長度電路板排列問題一（習(xí)題68）241
算法實(shí)現(xiàn)題62最小長度電路板排列問題二（習(xí)題69）244
算法實(shí)現(xiàn)題63最小權(quán)頂點(diǎn)覆蓋問題（習(xí)題610）247
算法實(shí)現(xiàn)題64無向圖的最大割問題（習(xí)題611）250
算法實(shí)現(xiàn)題65最小重量機(jī)器設(shè)計(jì)問題（習(xí)題612）253
算法實(shí)現(xiàn)題66運(yùn)動(dòng)員最佳匹配問題（習(xí)題613）256
算法實(shí)現(xiàn)題67n皇后問題（習(xí)題615）259
算法實(shí)現(xiàn)題68圓排列問題（習(xí)題616）260
算法實(shí)現(xiàn)題69布線問題（習(xí)題617）263
算法實(shí)現(xiàn)題610最佳調(diào)度問題（習(xí)題618）265
算法實(shí)現(xiàn)題611無優(yōu)先級運(yùn)算問題（習(xí)題619）268
算法實(shí)現(xiàn)題612世界名畫陳列館問題（習(xí)題621）271
算法實(shí)現(xiàn)題613騎士征途問題274
算法實(shí)現(xiàn)題614推箱子問題275
算法實(shí)現(xiàn)題615圖形變換問題281
算法實(shí)現(xiàn)題616行列變換問題284
算法實(shí)現(xiàn)題617重排n2宮問題285
算法實(shí)現(xiàn)題618最長距離問題290
第7章概率算法296
習(xí)題71模擬正態(tài)分布隨機(jī)變量296
習(xí)題72隨機(jī)抽樣算法297
習(xí)題73隨機(jī)產(chǎn)生m個(gè)整數(shù)297
習(xí)題74集合大小的概率算法298
習(xí)題75生日問題299
習(xí)題76易驗(yàn)證問題的拉斯維加斯算法300
習(xí)題77用數(shù)組模擬有序鏈表300
習(xí)題78O(n3/2)舍伍德型排序算法300
習(xí)題79n后問題解的存在性301
習(xí)題711整數(shù)因子分解算法302
習(xí)題712非蒙特卡羅算法的例子302
習(xí)題713重復(fù)3次的蒙特卡羅算法303
習(xí)題714集合隨機(jī)元素算法304
習(xí)題715由蒙特卡羅算法構(gòu)造拉斯維加斯算法305
習(xí)題716產(chǎn)生素?cái)?shù)算法306
習(xí)題719矩陣方程問題306
算法實(shí)現(xiàn)題71模平方根問題（習(xí)題710）307
算法實(shí)現(xiàn)題72素?cái)?shù)測試問題（習(xí)題717）309
算法實(shí)現(xiàn)題73集合相等問題（習(xí)題718）309
算法實(shí)現(xiàn)題74逆矩陣問題（習(xí)題720）310
算法實(shí)現(xiàn)題75多項(xiàng)式乘積問題（習(xí)題721）311
算法實(shí)現(xiàn)題76皇后控制問題311
算法實(shí)現(xiàn)題773SAT問題315
算法實(shí)現(xiàn)題78戰(zhàn)車問題316
算法實(shí)現(xiàn)題79圓排列問題318
算法實(shí)現(xiàn)題710騎士控制問題319
算法實(shí)現(xiàn)題711騎士對攻問題320
第8章NP完全性理論322
習(xí)題81RAM和RASP程序322
習(xí)題82RAM和RASP程序的復(fù)雜性322
習(xí)題83計(jì)算nn的RAM程序322
習(xí)題84沒有MULT和DIV指令的RAM程序324
習(xí)題85MULT和DIV指令的計(jì)算能力324
習(xí)題86RAM和RASP的空間復(fù)雜性325
習(xí)題87行列式的直線式程序325
習(xí)題88求和的3帶圖靈機(jī)325
習(xí)題89模擬RAM指令325
習(xí)題810計(jì)算22n的RAM程序325
習(xí)題811計(jì)算g(m,n)的程序326
習(xí)題812圖靈機(jī)模擬RAM的時(shí)間上界326
習(xí)題813圖的同構(gòu)問題326
習(xí)題814哈密頓回路327
習(xí)題815P類語言的封閉性327
習(xí)題816NP類語言的封閉性328
習(xí)題817語言的2O（nk）時(shí)間判定算法328
習(xí)題818PCONP329
習(xí)題819NP≠CONP329
習(xí)題820重言布爾表達(dá)式329
習(xí)題821關(guān)系∝p的傳遞性329
習(xí)題822L∝p330
習(xí)題823語言的完全性330
習(xí)題824的CONP完全性330
習(xí)題825判定重言式的CONP完全性331
習(xí)題826析取范式的可滿足性331
習(xí)題8272SAT問題的線性時(shí)間算法331
習(xí)題828整數(shù)規(guī)劃問題332
習(xí)題829劃分問題333
習(xí)題830最長簡單回路問題334
第9章近似算法336
習(xí)題91平面圖著色問題的絕對近似算法336
習(xí)題92最優(yōu)程序存儲問題336
習(xí)題94樹的最優(yōu)頂點(diǎn)覆蓋337
習(xí)題95頂點(diǎn)覆蓋算法的性能比339
習(xí)題96團(tuán)的常數(shù)性能比近似算法339
習(xí)題99售貨員問題的常數(shù)性能比近似算法340
習(xí)題910瓶頸旅行售貨員問題340
習(xí)題911最優(yōu)旅行售貨員回路不自相交342
習(xí)題914集合覆蓋問題的實(shí)例342
習(xí)題916多機(jī)調(diào)度問題的近似算法343
習(xí)題917LPT算法的最壞情況實(shí)例345
習(xí)題918多機(jī)調(diào)度問題的多項(xiàng)式時(shí)間近似算法345
算法實(shí)現(xiàn)題91旅行售貨員問題的近似算法（習(xí)題99）346
算法實(shí)現(xiàn)題92可滿足問題的近似算法（習(xí)題920）348
算法實(shí)現(xiàn)題93最大可滿足問題的近似算法（習(xí)題921）349
算法實(shí)現(xiàn)題94子集和問題的近似算法（習(xí)題915）351
算法實(shí)現(xiàn)題95子集和問題的完全多項(xiàng)式時(shí)間近似算法352
算法實(shí)現(xiàn)題96實(shí)現(xiàn)算法greedySetCover（習(xí)題913）352
算法實(shí)現(xiàn)題97裝箱問題的近似算法First Fit（習(xí)題919）356
算法實(shí)現(xiàn)題98裝箱問題的近似算法Best Fit（習(xí)題919）358
算法實(shí)現(xiàn)題99裝箱問題的近似算法First Fit Decreasing（習(xí)題919）360
算法實(shí)現(xiàn)題910裝箱問題的近似算法Best Fit Decreasing（習(xí)題919）361
算法實(shí)現(xiàn)題911裝箱問題的近似算法Next Fit361
第10章算法優(yōu)化策略365
習(xí)題101算法obst的正確性365
習(xí)題102矩陣連乘問題的O(n2)時(shí)間算法365
習(xí)題106貨物儲運(yùn)問題的費(fèi)用371
習(xí)題107Garsia算法371
算法實(shí)現(xiàn)題101貨物儲運(yùn)問題（習(xí)題103）374
算法實(shí)現(xiàn)題102石子合并問題（習(xí)題104）374
算法實(shí)現(xiàn)題103最大運(yùn)輸費(fèi)用貨物儲運(yùn)問題（習(xí)題105）375
算法實(shí)現(xiàn)題104五邊形問題377
算法實(shí)現(xiàn)題105區(qū)間圖最短路問題（習(xí)題108）381
算法實(shí)現(xiàn)題106圓弧區(qū)間最短路問題（習(xí)題109）381
算法實(shí)現(xiàn)題107雙機(jī)調(diào)度問題（習(xí)題1010）382
算法實(shí)現(xiàn)題108離線最小值問題（習(xí)題1011）390
算法實(shí)現(xiàn)題109最近公共祖先問題（習(xí)題1012）393
算法實(shí)現(xiàn)題1010達(dá)爾文芯片問題395
算法實(shí)現(xiàn)題1011多柱Hanoi塔問題397
算法實(shí)現(xiàn)題1012線性時(shí)間Huffman算法400
算法實(shí)現(xiàn)題1013單機(jī)調(diào)度問題402
算法實(shí)現(xiàn)題1014最大費(fèi)用單機(jī)調(diào)度問題405
算法實(shí)現(xiàn)題1015飛機(jī)加油問題408
參考文獻(xiàn)410