算法設(shè)計與分析習題解答

內(nèi)容概要

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

作者簡介

　　王曉東，男，1957年3月出生，福州大學計算機系教授，福建省計算機學會理事長。研究領(lǐng)域是算法設(shè)計與算法評價，基于計算機網(wǎng)絡(luò)和信息安全的大規(guī)模問題求解算法與數(shù)據(jù)結(jié)構(gòu)，信息可視化技術(shù)，幾何計算，并行和分布式算法設(shè)計，計算復雜性理論。先后主持了與算法設(shè)計與分析有

書籍目錄

第1章　算法引論
　習題1-1　實參交換
　習題1-2　方法頭簽名
　習題1-3　數(shù)組排序判定
　習題1-4　函數(shù)的漸近表達式
　習題1-5　O（1）和O（2）的區(qū)別
　習題1-7　按漸近階排列表達式
　習題1-8　算法效率
　習題1-9　硬件效率
　習題1-10　函數(shù)漸近階
　習題1-11　n！的階
　習題1-12　平均情況下的計算時間復雜性
　算法實現(xiàn)題1-1　統(tǒng)計數(shù)字問題
　算法實現(xiàn)題1-2　字典序問題
　算法實現(xiàn)題1-3　最多約數(shù)問題
　算法實現(xiàn)題1-4　金幣陣列問題
　算法實現(xiàn)題1-5　最大間隙問題
第2章　遞歸與分治策略
　習題2-1　Hanoi塔問題的非遞歸算法
　習題2-2　7個二分搜索算法
　習題2-3　改寫二分搜索算法
　習題2-4　大整數(shù)乘法的O（n1Og（3/2））算法
　習題2-5　5次7//3位整數(shù)的乘法
　習題2-6　矩陣乘法
　習題2-7　多項式乘積
　習題2-8　不動點問題的O（1O9n）時間算法．
　習題2-9　主元素問題的線性時間算法
　習題2-10　無序集主元素問題的線性時間算法
　習題2-11　O（1）空間子數(shù)組換位算法
　習題2-12　O（1）空間合并算法
　習題2-13　n段合并排序算法
　習題2-14　自然合并排序算法
　習題2-15　最大值和最小值問題的最優(yōu)算法
　習題2-16　最大值和次大值問題的最優(yōu)算法
　習題2-17　整數(shù)集合排序
　習題2-18　第k小元素問題的計算時間下界”
　習題2-19　非增序快速排序算法
　習題2-20　隨機化算法
　習題2-21　隨機化快速排序算法
　習題2-22　隨機排列算法”
　習題2-23　算法qSort中的尾遞歸
　習題2-24　用棧模擬遞歸
　習題2-25　算法se1ect中的元素劃分
　習題2-26　O（nlogn）時間快速排序算法
　習題2-27　最接近中位數(shù)的k個數(shù)
　習題2-28　X和y的中位數(shù)
　習題2-29　網(wǎng)絡(luò)開關(guān)設(shè)計
　習題2-32　帶權(quán)中位數(shù)問題
　習題2-34　構(gòu)造Gray碼的分治算法
　習題2-35　網(wǎng)球循環(huán)賽日程表
　算法實現(xiàn)題2-1　輸油管道問題（習題2-3O）
　算法實現(xiàn)題2-2　眾數(shù)問題（習題2-31）
　算法實現(xiàn)題2-3　郵局選址問題（習題2-32）
　算法實現(xiàn)題2-4　馬的Hami1tOn周游路線問題（習題2-33）
　算法實現(xiàn)題2-5　半數(shù)集問題
　算法實現(xiàn)題2-6　半數(shù)單集問題
　算法實現(xiàn)題2-7　士兵站隊問題
　算法實現(xiàn)題2-8　有重復元素的排列問題
　算法實現(xiàn)題2-9　排列的字典序問題
　……
第3章　動態(tài)規(guī)劃
第4章　貪心算法
第5章　回溯法
第6章　分支限界法
第7章　概率算法
第8章　NP完全性理論
第9章　近似算法
第10章　算法優(yōu)化策略
第11章　在線算法設(shè)計
參考文獻

章節(jié)摘錄

版權(quán)頁：   插圖：   算法實現(xiàn)題2-1輸油管道問題（習題2-30） 問題描述 某石油公司計劃建造一條由東向西的主輸油管道。該管道要穿過一個有，2口油井的油田。從每口油井都要有一條輸油管道沿最短路徑（或南或北）與主管道相連。如果給定n口油井的位置，即它們的x坐標（東西向）和y坐標（南北向），應如何確定主管道的最優(yōu)位置（即使各油井到主管道之間的輸油管道長度總和最小的位置）？證明可在線性時間內(nèi)確定主管道的最優(yōu)位置。 編程任務(wù) 給定n口油井的位置，編程計算各油井到主管道之間的輸油管道最小長度總和。 數(shù)據(jù)輸入 由文件input.txt提供輸入數(shù)據(jù)。文件的第1行是油井數(shù)理n.1≤n≤10000。接下來n行是油井的位置，每行兩個整數(shù)x和y，-10000≤x，y≤10000。 結(jié)果輸出 程序運行結(jié)束時，將計算結(jié)果輸出到文件Output.txt中。文件的第1行中的數(shù)是油井到主管道之間的輸油管道最小長度總和。 輸入文件示例 輸出文件示例 input.txt output.txt 5 6 1 2 2 2 1 3 3-2 3 3 6 分析與解答： 設(shè)n口油井的位置分別為Pi=(xi，yi)，1≤i≤n。由于主輸油管道是東西向的，因此可用其主軸線的y坐標唯一確定其位置。主管道的最優(yōu)位置y應使∑d(y，yi)達到最小，其中，d(y，Yi)=|y-yi|。這正是習題2-32中一維郵局問題的特殊情形，即Wi=1/n，1≤i≤n的情形。由帶權(quán)中位數(shù)問題的解答可知，yi（其中1≤i≤n）的中位數(shù)挑即為輸油管道問題的最優(yōu)解。用任一線性時間找中位數(shù)算法，均可在O(n)時間內(nèi)解此問題。

編輯推薦

《普通高等教育"十一五"國家級規(guī)劃教材?21世紀大學本科計算機專業(yè)系列教材:算法設(shè)計與分析習題解答(第2版)》內(nèi)容豐富，觀點新穎，理論聯(lián)系實際。不僅可以用作高等學校計算機科學與技術(shù)學科各專業(yè)本科生和研究生學習計算機算法設(shè)計的輔助教材，而且也適合廣大工程技術(shù)人員和自學讀者學習參考。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    算法設(shè)計與分析習題解答 PDF格式下載

---