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

定　價：￥43.90

作　者：	王曉東
出版社：	清華大學(xué)出版社
叢編項：	普通高等教育"十一五"國家級規(guī)劃教材
標(biāo)　簽：	計算機理論

購買這本書可以去

ISBN：	9787302167198	出版時間：	2008-02-01	包裝：	平裝
開本：	16	頁數(shù)：	420 pages	字?jǐn)?shù)：

內(nèi)容簡介

　　《21世紀(jì)大學(xué)本科計算機專業(yè)系列教材：算法設(shè)計與分析習(xí)題解答（第2版）》是清華大學(xué)出版社出版的普通高等教育“十一五”國家級規(guī)劃教材《算法設(shè)計與分析（第2版）》（主教材）配套的輔助教材，對《算法設(shè)計與分析（第2版）》一書中的全部習(xí)題做了詳盡的解答?！?1世紀(jì)大學(xué)本科計算機專業(yè)系列教材：算法設(shè)計與分析習(xí)題解答（第2版）》的內(nèi)容是對《算法設(shè)計與分析（第2版）》的較深入的擴展，許多在主教材中無法講述的、較深入的主題通過習(xí)題的形式展現(xiàn)出來。為了加強學(xué)生靈活運用算法設(shè)計策略解決實際問題的能力，《21世紀(jì)大學(xué)本科計算機專業(yè)系列教材：算法設(shè)計與分析習(xí)題解答（第2版）》將主教材中的許多習(xí)題改造成算法實現(xiàn)題，要求學(xué)生不僅設(shè)計出解決具體問題的算法，而且能夠上機實現(xiàn)。作者的教學(xué)實踐反映出這類算法實現(xiàn)題的教學(xué)效果非常好。作者還結(jié)合國家精品課程建設(shè)，進行了教材的立體化開發(fā)，包括主教材、輔助教材、實驗與設(shè)計、電子課件和教學(xué)網(wǎng)站建設(shè)。本書內(nèi)容豐富，觀點新穎，理論聯(lián)系實際。不僅可以用作高等學(xué)校計算機科學(xué)與技術(shù)學(xué)科各專業(yè)本科生和研究生學(xué)習(xí)計算機算法設(shè)計的輔助教材，而且也適合廣大工程技術(shù)人員和自學(xué)讀者學(xué)習(xí)參考。

作者簡介

　　王曉東，男，1957年3月出生，福州大學(xué)計算機系教授，福建省計算機學(xué)會理事長。研究領(lǐng)域是算法設(shè)計與算法評價，基于計算機網(wǎng)絡(luò)和信息安全的大規(guī)模問題求解算法與數(shù)據(jù)結(jié)構(gòu)，信息可視化技術(shù)，幾何計算，并行和分布式算法設(shè)計，計算復(fù)雜性理論。先后主持了與算法設(shè)計與分析有關(guān)的國家自然科學(xué)基金項目、國家優(yōu)秀留學(xué)回國人員基金項目、福建省杰出人才基金項目和省自然科學(xué)基金項日等7個研究課題；獲德國家科技進步二等獎1項，省科技進步二等獎3項。主持國家精品課程算法與數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計與分析的課程建設(shè)，獲福建省教學(xué)成果·等獎。在國內(nèi)外重要學(xué)術(shù)刊物上發(fā)表有創(chuàng)見性的論文50余篇；出版《算法設(shè)計與分析》等學(xué)術(shù)著作7部，在算法復(fù)雜性研究方面取得r一系列理論研究和應(yīng)用成果。例如，在對著名的凸殼問題的計算復(fù)雜性研究成果巾推廣了關(guān)于判定樹模型下問題的計算復(fù)雜性ji界著名的Ben-Or定理，并應(yīng)用于分析凸殼問題的計算復(fù)雜性，在較一般的情況下改進和完善了網(wǎng)際算法界知名學(xué)者Aggarwal，Steele和Yao等提出的關(guān)于凸殼問題計算復(fù)雜性下界的結(jié)果。研究成果得到國內(nèi)外同行專家的好評并被國內(nèi)權(quán)威刊物所引用。

圖書目錄

習(xí)題1-1 實參交換1
習(xí)題1-2 方法頭簽名1
習(xí)題1-3 數(shù)組排序判定1
習(xí)題1-4 函數(shù)的漸近表達式2
習(xí)題1-5 O(1)和O(2)的區(qū)別2
習(xí)題1-7 按漸近階排列表達式2
習(xí)題1-8 算法效率2
習(xí)題1-9 硬件效率3
習(xí)題1-10 函數(shù)漸近階3
習(xí)題1-11 n!的階4
習(xí)題1-12 平均情況下的計算時間復(fù)雜性4
算法實現(xiàn)題1-1 統(tǒng)計數(shù)字問題4
算法實現(xiàn)題1-2 字典序問題5
算法實現(xiàn)題1-3 最多約數(shù)問題6
算法實現(xiàn)題1-4 金幣陣列問題8
算法實現(xiàn)題1-5 最大間隙問題11第2章遞歸與分治策略14
習(xí)題2-1 Hanoi 塔問題的非遞歸算法14

算法實現(xiàn)題2-1 輸油管道問題（習(xí)題2-30) 49

習(xí)題3-1 最長單調(diào)遞增子序列76
習(xí)題3-2 最長單調(diào)遞增子序列的O(nlogn)算法77
習(xí)題3-7 漂亮打印78
習(xí)題3-11 整數(shù)線性規(guī)劃問題79
習(xí)題3-12 二維背包問題80
習(xí)題3-14 Ackermann函數(shù)81
習(xí)題3-17 最短行駛路線83
習(xí)題3-19 最優(yōu)旅行路線83
算法實現(xiàn)題3-1 獨立任務(wù)最優(yōu)調(diào)度問題（習(xí)題3-3) 83
算法實現(xiàn)題3-2 最少硬幣問題（習(xí)題3-4) 85
算法實現(xiàn)題3-3 序關(guān)系計數(shù)問題（習(xí)題3-5) 86
算法實現(xiàn)題3-4 多重冪計數(shù)問題（習(xí)題3-6) 87

習(xí)題4-2 活動安排問題的貪心選擇123

算法實現(xiàn)題4-1 會場安排問題（習(xí)題4-1) 128

習(xí)題5\|1 裝載問題改進回溯法（一）153
習(xí)題5\|2 裝載問題改進回溯法（二）154
習(xí)題5\|4 0-1背包問題的最優(yōu)解155
習(xí)題5\|5 最大團問題的迭代回溯法156
習(xí)題5\|7 旅行售貨員問題的費用上界157
習(xí)題5\|8 旅行售貨員問題的上界函數(shù)158
算法實現(xiàn)題5-1 子集和問題（習(xí)題5-3) 159

習(xí)題6-1 0-1背包問題的棧式分支限界法229
習(xí)題6-2 用最大堆存儲活結(jié)點的優(yōu)先隊列式分支限界法231
習(xí)題6-3 團頂點數(shù)的上界234
習(xí)題6-4 團頂點數(shù)改進的上界235
習(xí)題6-5 修改解旅行售貨員問題的分支限界法235
習(xí)題6-6 解旅行售貨員問題的分支限界法中保存已產(chǎn)生的排列樹237
習(xí)題6-7 電路板排列問題的隊列式分支限界法239
算法實現(xiàn)題6-1 最小長度電路板排列問題一（習(xí)題6-8) 241

習(xí)題7-1 模擬正態(tài)分布隨機變量296

算法實現(xiàn)題7-1 模平方根問題（習(xí)題7-10) 307

習(xí)題8-1 RAM和RASP程序322

習(xí)題9-1 平面圖著色問題的絕對近似算法336

算法實現(xiàn)題9-1 旅行售貨員問題的近似算法（習(xí)題9-9) 346

習(xí)題10-1 算法obst的正確性365
習(xí)題10-2 矩陣連乘問題的O(n2)時間算法365
習(xí)題10-6 貨物儲運問題的費用371
習(xí)題10-7 Garsia算法371

第11章在線算法設(shè)計410
習(xí)題11-1 在線算法LFU的競爭性410
習(xí)題11-4 多讀寫頭磁盤問題的在線算法410
習(xí)題11-6 帶權(quán)頁調(diào)度問題410
算法實現(xiàn)題11-1 最優(yōu)頁調(diào)度問題（習(xí)題11-2) 411
算法實現(xiàn)題11-2 在線LRU頁調(diào)度（習(xí)題11-3) 414
算法實現(xiàn)題11-3 k服務(wù)問題（習(xí)題11-5) 416
參考文獻422