《算法設計與分析與分析習題解答》是2006年清華大學出版社出版的圖書，作者是王曉東。本書主要介紹了算法設計與分析的基本知識和規律技巧。
基本介紹
- 書名：算法設計與分析與分析習題解答
- 作者：王曉東
- 類別：計算機通信 >計算機理論
- 頁數：409
- 出版時間：2006年
內容提要,章節目錄,
內容提要
本書是《算法設計與分析》的配套輔助教材。
章節目錄
第1章 算法引論
習題1-1 實參交換
習題1-2 方法頭簽名
習題1-3 數組排序判定
習題1-4 函式的漸近表達式
習題1-5 O（1）和O（2）的區別
習題1-7 按漸近階排列表達式
習題1-8 算法效率
習題1-9 硬體效率
習題1-10 函式漸進階
習題1-11 n！的階
習題1-12 平均情況下的計算時間複雜性
算法實現題1-1 統計數字問題
算法實現題1-2 字典序問題
算法實現題1-3 最多約數問題
算法實現題1-4 金幣陣列問題
算法實現題1-5 最大間隙問題
第2章 遞歸與分治策略
習題2-1 Hanoi塔問題的非遞歸算法
習題2-2 7個二分搜尋算法
習題2-3 改寫二分搜尋算法
習題2-4 大整數乘法的O（nmlog(3/2)）算法
習題2-5 5次n/3位整數的乘法
習題2-6 矩陣乘法
習題2-7 多項式乘積
習題2-8 不動點問題的O（logn）時間算法
習題2-9 主元素問題的線性時間算法
習題2-10 無序集主元素問題的線性時間算法
習題2-11 O（1）空間子數組換位算法
習題2-12 O（1）空間合併算法
習題2-13 ？段合併排序算法
習題2-14 自然合併排序算法
習題2-15 最大值和最小值問題的最優算法
習題2-16 最大值和次大值問題的最優算法
習題2-17 整數集合排序
習題2-18 第k小元素問題的計算時間下界
習題2-19 非增序快速排序算法
習題2-20 隨機化算法
習題2-21 隨機化快速排序算法
習題2-22 隨機排列算法
習題2-23 算法qSort中的尾遞歸
習題2-24 用棧模擬遞歸
習題2-25 算法select中的元素劃分
習題2-26 O（nlogn）時間快速排序算法
習題2-27 最接近中位數的k個數
習題2-28 X和Y的中位數
習題2-29 網路開關設計
習題2-32 帶權中位數問題
習題2-34 構造Gray碼的分治算法
習題2-35 網球循環賽日程表
算法實現題2-1 輸油管道問題（習題2-30）
算法實現題2-2 眾數問題（習題2-31）
算法實現題2-3 郵局選址問題（習題2-32）
算法實現題2-4 馬的Hamilton週遊路線問題（習題2-33）
算法實現題2-5 半數集問題
算法實現題2-6 半數單集問題
算法實現題2-7 士兵站隊問題
算法實現題2-8 有重複元素的排列問題
算法實現題2-9 排列的字典序問題
算法實現題2-10 集合劃分問題（一）
算法實現題2-11 集合劃分問題（二）
算法實現題2-12 雙色Hanoi塔問題
算法實現題2-13 標準二維表問題
算法實現題2-14 整數因子分解問題
算法實現題2-15 有向直線2中值問題
第3章 動態規劃
習題3-1 最長單調遞增子序列
習題3-2 最長單調遞增子序列的O（nlogn）算法
習題3-7 漂亮列印
習題3-11 整數線性規劃問題
習題3-12 二維背包問題
習題3-14 Ackermann函式
習題3-17 最短行駛路線
習題3-19 最優旅行路線
算法實現題3-1 獨立任務最優調度問題（習題3-3）
算法實現題3-2 最少硬幣問題（習題3-4）
算法實現題3-3 序關係計數問題（習題3-5）
算法實現題3-4 多重冪計數問題（習題3-6）
算法實現題3-5 編輯距離問題（習題3-8）
算法實現題3-6 石子合併問題（習題3-9）
算法實現題3-7 數字三角形問題（習題3-10）
算法實現題3-8 乘法表問題（習題3-13）
算法實現題3-9 租用遊艇問題（習題3-15）
算法實現題3-10 汽車加油行駛問題（習題3-16）
算法實現題3-11 圈乘運算問題（習題3-18）
算法實現題3-12 最少費用購物（習題3-20）
算法實現題3-13 最大長方體問題（習題3-21）
算法實現題3-14 正則表達式匹配問題（習題3-22）
算法實現題3-15 雙調旅行售貨員問題（習題3-23）
算法實現題3-16 最大k乘積問題（習題5-24）
算法實現題3-17 最小m段和問題
算法實現題3-18 紅黑樹的紅色內結點問題
第4章 貪心算法
習題4-2 活動安排問題的貪心選擇
習題4-3 背包問題的貪心選擇性質
習題4-4 特殊的0-1背包問題
習題4-10 程式最優存儲問題
習題4-13 最優裝載問題的貪心算法
習題4-18 Fibonacci序列的Huffman編碼
習題4-19 最優前綴碼的編碼序列
習題4-21 任務集獨立性問題
習題4-22 矩陣擬陣
習題4-23 最小權最大獨立子集擬陣
習題4-27 整數邊權Prim算法
習題4-28 最大權最小生成樹
習題4-29 最短路徑的負邊權
習題4-30 整數邊權Dijkstra算法
算法實現題4-1 會場安排問題（習題4-1）
算法實現題4-2 最優合併問題（習題4-5）
算法實現題4-3 磁帶最優存儲問題（習題4-6）
算法實現題4-4 磁碟檔案最優存儲問題（習題4-7）
算法實現題4-5 程式存儲問題（習題4-8）
算法實現題4-6 最優服務次序問題（習題4-11）
算法實現題4-7 多處最優服務次序問題（習題4-12）
算法實現題4-8 d森林問題（習題4-14）
算法實現題4-9 汽車加油問題（習題4-16）
算法實現題4-10 區間覆蓋問題（習題4-17）
算法實現題4-11 硬幣找錢問題（習題4-24）
算法實現題4-12 刪數問題（習題4-25）
算法實現題4-13 數列極差問題（習題4-26）
算法實現題4-14 嵌套箱問題（習題4-31）
算法實現題4-15 套匯問題（習題4-32）
算法實現題4-16 信號增強裝置問題（習題5-17）
算法實現題4-17 磁帶最大利用率問題（習題4-9）
算法實現題4-18 非單位時間任務安排問題（習題4-15）
算法實現題4-19 多元Huffman編碼問題（習題4-20）
算法實現題4-20 多元Huffman編碼變形
算法實現題4-21 區間相交問題
算法實現題4-22 任務時間表問題
第5章 回溯法
習題5-1 裝載問題改進回溯法1
習題5-2 裝載問題改進回溯法2
習題5-4 0-1背包問題的最優解
習題5-5 最大團問題的疊代回溯法
習題5-7 旅行售貨員問題的費用上界
習題5-8 旅行售貨員問題的上界函式
算法實現題5-1 子集和問題（習題5-3）
算法實現題5-2 最小長度電路板排列問題（習題5-9）
算法實現題5-3 最小重量機器設計問題（習題5-10）
算法實現題5-4 運動員最佳匹配問題（習題5-11）
算法實現題5-5 無分隔設定字典問題（習題5-12）
算法實現題5-6 無和集問題（習題5-13）
算法實現題5-7 n色方柱問題（習題5-14）
算法實現題5-8 整數變換問題（習題5-15）
算法實現題5-9 拉丁矩陣問題（習題5-16）
算法實現題5-10 排列寶石問題（習題5-16）
算法實現題5-11 重複拉丁矩陣問題（習題5-16）
算法實現題5-12 羅密歐與朱麗葉的迷宮問題
算法實現題5-13 工作分配問題（習題5-18）
算法實現題5-14 獨立鑽石跳棋問題（習題5-19）
算法實現題5-15 智力拚圖問題（習題5-20）
算法實現題5-16 布線問題（習題5-21）
算法實現題5-17 最佳調度問題（習題5-22）
算法實現題5-18 無優先權運算問題（習題5-23）
算法實現題5-19 世界名畫陳列館問題（習題5-25）
算法實現題5-20 世界名畫陳列館問題（不重複監視）（習題5-26）
算法實現題5-21 部落衛隊問題（習題5-6）
算法實現題5-22 蟲蝕算式問題
算法實現題5-23 完備環序列問題
算法實現題5-24 離散01串問題
算法實現題5-25 噴漆機器人問題
算法實現題5-26 n2-1謎問題
第6章 分支限界法
習題6-1 0-1背包問題的棧式分支限界法
習題6-2 用最大堆存儲活結點的優先佇列式分支限界法
習題6-3 團頂點數的上界
習題6-4 團頂點數改進的上界
習題6-5 修改解旅行售貨員問題的分支限界法
習題6-6 解旅行售貨員問題的分支限界法中保存已產生的排列樹
習題6-7 電路板排列問題的佇列式分支限界法
算法實現題6-1 最小長度電路板排列問題一（習題6-8）
算法實現題6-2 最小長度電路板排列問題二（習題6-9）
算法實現題6-3 最小權頂點覆蓋問題（習題6-10）
算法實現題6-4 無向圖的最大割問題（習題6-11）
算法實現題6-5 最小重量機器設計問題（習題6-12）
算法實現題6-6 運動員最佳匹配問題（習題6-13）
算法實現題6-7 n皇后問題（習題6-15）
算法實現題6-8 圓排列問題（習題6-16）
算法實現題6-9 布線問題（習題6-17）
算法實現題6-10 最佳調度問題（習題6-18）
算法實現題6-11 無優先權運算問題（習題6-19）
算法實現題6-12 世界名畫陳列館問題（習題6-21）
算法實現題6-13 騎士征途問題
算法實現題6-14 推箱子問題
算法實現題6-15 圖形變換問題
算法實現題6-16 行列變換問題
算法實現題6-17 重排n2宮問題
算法實現題6-18 最長距離問題
第7章 機率算法
習題7-1 模擬常態分配隨機變數
習題7-2 隨機抽樣算法
習題7-3 隨機產生m個整數
習題7-4 集合大小的機率算法
習題7-5 生日問題
習題7-6 易驗證問題的拉斯維加斯算法
習題7-7 用數組模擬有序鍊表
習題7-8 O（n3/2）舍伍德型排序算法
習題7-9 n後問題解的存在性
習題7-11 整數因子分解算法
習題7-12 非蒙特卡羅算法的例子
習題7-13 重複3次的蒙特卡羅算法
習題7-14 集合隨機元素算法
習題7-15 由蒙特卡羅算法構造拉斯維加斯算法
習題7-16 產生素數算法
習題7-19 矩陣方程問題
算法實現題7-1 模平方根問題（習題7-10）
算法實現題7-2 素數測試問題（習題7-17）
算法實現題7-3 集合相等問題（習題7-18）
算法實現題7-4 逆矩陣問題（習題7-20）
算法實現題7-5 多項式乘積問題（習題7-21）
算法實現題7-6 皇后控制問題
算法實現題7-7 3SAT問題
算法實現題7-8 戰車問題
算法實現題7-9 圓排列問題
算法實現題7-10 騎士控制問題
算法實現題7-11 騎士對攻問題
第8章 NP完全性理論
習題8-1 RAM和RASP程式
習題8-2 RAM和RASP程式的複雜性
習題8-3 計算nn的RAM程式
習題8-4 沒有MULT和DIV指令的RAM程式
習題8-5 MULT和DIV指令的計算能力
習題8-6 RAM和RASP的空間複雜性
習題8-7 行列式的直線式程式
習題8-8 求和的3帶圖靈機
習題8-9 模擬RAM指令
習題8-10 計算22n的RAM程式
習題8-11 計算g（m,n）的程式
習題8-12 圖靈機模擬RAM的時間上界
習題8-13 圖的同構問題
習題8-14 哈密頓迴路
習題8-15 P類語言的封閉性
習題8-16 NP類語言的封閉性
習題8-17 語言的2O（nk）時間判定算法
習題8-18 P？CO-NP
習題8-19 NP≠CO-NP
習題8-20 重言布爾表達式
習題8-21 關係？p的傳遞性
習題8-22 L？p？
習題8-23 語言的完全性
習題8-24 ？的CO-NP完全性
習題8-25 判定重言式的CO-NP完全性
習題8-26 析取範式的可滿足性
習題8-27 2SAT問題的線性時間算法
習題8-28 整數規劃問題
習題8-29 劃分問題
習題8-30 最長簡單迴路問題
第9章 近似算法
習題9-1 平面圖著色問題的絕對近似算法
習題9-2 最優程式存儲問題
習題9-4 樹的最優頂點覆蓋
習題9-5 頂點覆蓋算法的性能比
習題9-6 團的常數性能比近似算法
習題9-9 售貨員問題的常數性能比近似算法
習題9-10 瓶頸旅行售貨員問題
習題9-11 最優旅行售貨員迴路不自相交
習題9-14 集合覆蓋問題的實例
習題9-16 多機調度問題的近似算法
習題9-17 LPT算法的最壞情況實例
習題9-18 多機調度問題的多項式時間近似算法
算法實現題9-1 旅行售貨員問題的近似算法（習題9-9）
算法實現題9-2 可滿足問題的近似算法（習題9-20）
算法實現題9-3 最大可滿足問題的近似算法（習題9-21）
算法實現題9-4 子集和問題的近似算法（習題9-15）
算法實現題9-5 子集和問題的完全多項式時間近似算法
算法實現題9-6 實現算法greedySetCover（習題9-13）
算法實現題9-7 裝箱問題的近似算法First Fit（習題9-19）
算法實現題9-8 裝箱問題的近似算法Best Fit（習題9-19）
算法實現題9-9 裝箱問題的近似算法First Fit Decreasing（習題9-19）
算法實現題9-10 裝箱問題的近似算法Best Fit Decreasing（習題9-19）
算法實現題9-11 裝箱問題的近似算法Next Fit
第10章 算法最佳化策略
習題10-1 算法obst的正確性
習題10-2 矩陣連乘問題的O（n2）時間算法
習題10-6 貨物儲運問題的費用
習題10-7 Garsia算法
算法實現題10-1 貨物儲運問題（習題10-3）
算法實現題10-2 石子合併問題（習題10-4）
算法實現題10-3 最大運輸費用貨物儲運問題（習題10-5）
算法實現題10-4 五邊形問題
算法實現題10-5 區間圖最短路問題（習題10-8）
算法實現題10-6 圓弧區間最短路問題（習題10-9）
算法實現題10-7 雙機調度問題（習題10-10）
算法實現題10-8 離線最小值問題（習題10-11）
算法實現題10-9 最近公共祖先問題（習題10-12）
算法實現題10-10 達爾文晶片問題
算法實現題10-11 多柱Hanoi塔問題
算法實現題10-12 線性時間Huffman算法
算法實現題10-13 單機調度問題
算法實現題10-14 最大費用單機調度問題
算法實現題10-15 飛機加油問題
參考文獻
