滿額折
商品簡介
作者簡介
序
目次
相關商品
商品簡介
本書是與“十二五”普通高等教育本科國家級規劃教材《計算機算法設計與分析（第5版）》配套的輔助教材和國家精品課程教材，分別對主教材中的算法分析題和算法實現題給出了解答或解題思路提示。為了提高學生靈活運用算法設計策略解決實際問題的能力，本書還將主教材中的許多習題改造成算法實現題，要求學生設計出求解算法並上機實現。本書教學資料包含各章算法實現題、測試數據和答案，可在華信教育資源網免費註冊下載。本書內容豐富，理論聯繫實際，可作為高等學校計算機科學與技術、軟件工程、信息安全、信息與計算科學等專業本科生和研究生學習計算機算法設計的輔助教材，也是工程技術人員和自學者的參考書。
作者簡介
王曉東，男，1957年出生，山東人，中共黨員，現任福建工程學院副院長，教授，博士生導師，福建省計算機學會理事長。先後擔任福州大學計算機系主任、數學與計算機科學學院院長，2007年8月起擔任泉州師範學院副院長。主講課程：算法與數據結構、算法設計與分析、文獻閱讀與選題報告。
序
前 言
一些著名的計算機科學家在有關計算機科學教育的論述中認為，計算機科學是一種創造性思維活動，其教育必須面向設計。“計算機算法設計與分析”正是一門面向設計，且處於計算機學科核心地位的教育課程。通過對計算機算法系統的學習與研究，理解掌握算法設計的主要方法，培養對算法的計算複雜性正確分析的能力，為獨立設計算法和對算法進行複雜性分析奠定堅實的理論基礎，對每一位從事計算機系統結構、系統軟件和應用軟件研究與開發的科技工作者都是非常重要和必不可少的。課程結合我國高等學校教育工作的現狀，追蹤國際計算機科學技術的發展水平，更新了教學內容和教學方法，以算法設計策略為知識單元，在內容選材、深度把握、系統性和可用性方面進行了精心設計，力圖適合高校本科生教學對學時數和知識結構的要求。
本書是“十二五”普通高等教育本科國家級規劃教材《計算機算法設計與分析（第5版）》（ISBN 978-7-121-34439-8）配套的輔助教材，對《計算機算法設計與分析（第5版）》一書中的全部習題做了詳盡的解答，旨在讓使用該書的教師更容易教，學生更容易學。為了便於對照閱讀，本書的章序與《計算機算法設計與分析（第5版）》一書的章序保持一致，且一一對應。
本書的內容是對《計算機算法設計與分析（第5版）》的較深入的擴展，許多教材中無法講述的較深入的主題通過習題的形式展現出來。為了加強學生靈活運用算法設計策略解決實際問題的能力，本書將主教材中的許多習題改造成算法實現題，要求學生不僅設計出解決具體問題的算法，而且能上機實現。作者的教學實踐反映出這類算法實現題的教學效果非常好。作者還結合國家精品課程建設，建立了“算法設計與分析”教學網站。國家精品資源共享課地址：http://www.icourses.cn/sCourse/course_2535.html。歡迎廣大讀者訪問作者的教學網站並提出寶貴意見。
在本書編寫過程中，福州大學“211工程”計算機與信息工程重點學科實驗室為本書的寫作提供了優良的設備與工作環境。電子工業出版社負責本書編輯出版工作的全體同仁為本書的出版付出了大量辛勤勞動，他們認真細緻、一絲不苟的工作精神保證了本書的出版質量。在此，謹向每位曾經關心和支持本書編寫工作的各方面人士表示衷心的謝意！
作 者
一些著名的計算機科學家在有關計算機科學教育的論述中認為，計算機科學是一種創造性思維活動，其教育必須面向設計。“計算機算法設計與分析”正是一門面向設計，且處於計算機學科核心地位的教育課程。通過對計算機算法系統的學習與研究，理解掌握算法設計的主要方法，培養對算法的計算複雜性正確分析的能力，為獨立設計算法和對算法進行複雜性分析奠定堅實的理論基礎，對每一位從事計算機系統結構、系統軟件和應用軟件研究與開發的科技工作者都是非常重要和必不可少的。課程結合我國高等學校教育工作的現狀，追蹤國際計算機科學技術的發展水平，更新了教學內容和教學方法，以算法設計策略為知識單元，在內容選材、深度把握、系統性和可用性方面進行了精心設計，力圖適合高校本科生教學對學時數和知識結構的要求。
本書是“十二五”普通高等教育本科國家級規劃教材《計算機算法設計與分析（第5版）》（ISBN 978-7-121-34439-8）配套的輔助教材，對《計算機算法設計與分析（第5版）》一書中的全部習題做了詳盡的解答，旨在讓使用該書的教師更容易教，學生更容易學。為了便於對照閱讀，本書的章序與《計算機算法設計與分析（第5版）》一書的章序保持一致，且一一對應。
本書的內容是對《計算機算法設計與分析（第5版）》的較深入的擴展，許多教材中無法講述的較深入的主題通過習題的形式展現出來。為了加強學生靈活運用算法設計策略解決實際問題的能力，本書將主教材中的許多習題改造成算法實現題，要求學生不僅設計出解決具體問題的算法，而且能上機實現。作者的教學實踐反映出這類算法實現題的教學效果非常好。作者還結合國家精品課程建設，建立了“算法設計與分析”教學網站。國家精品資源共享課地址：http://www.icourses.cn/sCourse/course_2535.html。歡迎廣大讀者訪問作者的教學網站並提出寶貴意見。
在本書編寫過程中，福州大學“211工程”計算機與信息工程重點學科實驗室為本書的寫作提供了優良的設備與工作環境。電子工業出版社負責本書編輯出版工作的全體同仁為本書的出版付出了大量辛勤勞動，他們認真細緻、一絲不苟的工作精神保證了本書的出版質量。在此，謹向每位曾經關心和支持本書編寫工作的各方面人士表示衷心的謝意！
作 者
目次
目 錄
第1章 算法概述 1
算法分析題1 1
1-1 函數的漸近表達式 1
1-2 O(1)和O(2)的區別 1
1-3 按漸近階排列表達式 1
1-4 算法效率 1
1-5 硬件效率 1
1-6 函數漸近階 2
1-7 n!的階 2
1-8 3n+1問題 2
1-9 平均情況下的計算時間複雜性 2
算法實現題1 3
1-1 統計數字問題 3
1-2 字典序問題 4
1-3 最多約數問題 4
1-4 金幣陣列問題 6
1-5 最大間隙問題 8
第2章 遞歸與分治策略 11
算法分析題2 11
2-1 證明Hanoi塔問題的遞歸算法與非遞歸算法實際上是一回事 11
2-2 判斷這7個算法的正確性 12
2-3 改寫二分搜索算法 15
2-4 大整數乘法的O(nmlog(3/2))算法 16
2-5 5次n/3位整數的乘法 16
2-6 矩陣乘法 18
2-7 多項式乘積 18
2-8 O(1)空間子數組換位算法 19
2-9 O(1)空間合併算法 21
2-10 段合併排序算法 27
2-11 自然合併排序算法 28
2-12 第k小元素問題的計算時間下界 29
2-13 非增序快速排序算法 31
2-14 構造Gray碼的分治算法 31
2-15 網球循環賽日程表 32
2-16 二叉樹T的前序、中序和後序序列 35
算法實現題2 36
2-1 眾數問題 36
2-2 馬的Hamilton周遊路線問題 37
2-3 半數集問題 44
2-4 半數單集問題 46
2-5 有重複元素的排列問題 46
2-6 排列的字典序問題 47
2-7 集合劃分問題 49
2-8 集合劃分問題 50
2-9 雙色Hanoi塔問題 51
2-10 標準二維表問題 52
2-11 整數因子分解問題 53
第3章 動態規劃 54
算法分析題3 54
3-1 最長單調遞增子序列 54
3-2 最長單調遞增子序列的O(nlogn)算法 54
3-3 整數線性規劃問題 55
3-4 二維0-1背包問題 56
3-5 Ackermann函數 57
算法實現題3 59
3-1 獨立任務最優調度問題 59
3-2 最優批處理問題 61
3-3 石子合併問題 67
3-4 數字三角形問題 68
3-5 乘法表問題 69
3-6 租用遊艇問題 70
3-7 汽車加油行駛問題 70
3-8 最小m段和問題 71
3-9 圈乘運算問題 72
3-10 最大長方體問題 78
3-11 正則表達式匹配問題 79
3-12 雙調旅行售貨員問題 83
3-13 最大k乘積問題 84
3-14 最少費用購物問題 86
3-15 收集樣本問題 87
3-16 最優時間表問題 89
3-17 字符串比較問題 89
3-18 有向樹k中值問題 90
3-19 有向樹獨立k中值問題 94
3-20 有向直線m中值問題 98
3-21 有向直線2中值問題 101
3-22 樹的最大連通分支問題 103
3-23 直線k中值問題 105
3-24 直線k覆蓋問題 109
3-25 m處理器問題 113
第4章 貪心算法 116
算法分析題4 116
4-1 程序最優存儲問題 116
4-2 最優裝載問題的貪心算法 116
4-3 Fibonacci序列的哈夫曼編碼 116
4-4 最優前綴碼的編碼序列 117
算法實現題4 117
4-1 會場安排問題 117
4-2 最優合併問題 118
4-3 磁帶最優存儲問題 118
4-4 磁盤文件最優存儲問題 119
4-5 程序存儲問題 120
4-6 最優服務次序問題 120
4-7 多處最優服務次序問題 121
4-8 d森林問題 122
4-9 虛擬汽車加油問題 123
4-10 區間覆蓋問題 124
4-11 刪數問題 124
4-12 磁帶最大利用率問題 125
4-13 非單位時間任務安排問題 126
4-14 多元Huffman編碼問題 127
4-15 最優分解問題 128
第5章 回溯法 130
算法分析題5 130
5-1 裝載問題改進回溯法1 130
5-2 裝載問題改進回溯法2 131
5-3 0-1背包問題的最優解 132
5-4 最大團問題的迭代回溯法 134
5-5 旅行售貨員問題的費用上界 135
5-6 旅行售貨員問題的上界函數 136
算法實現題5 137
5-1 子集和問題 137
5-2 最小長度電路板排列問題 138
5-3 最小重量機器設計問題 140
5-4 運動員最佳配對問題 141
5-5 無分隔符字典問題 142
5-6 無和集問題 144
5-7 n色方柱問題 145
5-8 整數變換問題 150
5-9 拉丁矩陣問題 151
5-10 排列寶石問題 152
5-11 重複拉丁矩陣問題 154
5-12 羅密歐與朱麗葉的迷宮問題 156
5-13 工作分配問題 158
5-14 佈線問題 159
5-15 最佳調度問題 160
5-16 無優先級運算問題 161
5-17 世界名畫陳列館問題 163
5-18 世界名畫陳列館問題（不重複監視） 166
5-19 算m點問題 169
5-20 部落衛隊問題 171
5-21 子集樹問題 173
5-22 0-1背包問題 174
5-23 排列樹問題 176
5-24 一般解空間搜索問題 177
5-25 最短加法鏈問題 179
第6章 分支限界法 185
算法分析題6 185
6-1 0-1背包問題的棧式分支限界法 185
6-2 釋放結點空間的隊列式分支限界法 187
6-3 及時刪除不用的結點 188
6-4 用最大堆存儲活結點的優先隊列式分支限界法 189
6-5 釋放結點空間的優先隊列式分支限界法 192
6-6 團頂點數的上界 194
6-7 團頂點數改進的上界 194
6-8 修改解旅行售貨員問題的分支限界法 195
6-9 試修改解旅行售貨員問題的分支限界法，使得算法保存已產生的排列樹 197
6-10 電路板排列問題的隊列式分支限界法 199
算法實現題6 201
6-1 最小長度電路板排列問題 201
6-2 最小權頂點覆蓋問題 203
6-3 無向圖的最大割問題 206
6-4 最小重量機器設計問題 209
6-5 運動員最佳配對問題 212
6-6 n後問題 214
6-7 佈線問題 216
6-8 最佳調度問題 218
6-9 無優先級運算問題 220
6-10 世界名畫陳列館問題 223
6-11 子集空間樹問題 226
6-12 排列空間樹問題 229
6-13 一般解空間的隊列式分支限界法 232
6-14 子集空間樹問題 236
6-15 排列空間樹問題 241
6-16 一般解空間的優先隊列式分支限界法 246
6-17 推箱子問題 250
第7章 概率算法 256
算法分析題7 256
7-1 模擬正態分佈隨機變量 256
7-2 隨機抽樣算法 256
7-3 隨機產生m個整數 257
7-4 集合大小的概率算法 258
7-5 生日問題 258
7-6 易驗證問題的拉斯維加斯算法 259
7-7 用數組模擬有序鏈表 260
7-8 O(n3/2)舍伍德型排序算法 260
7-9 n後問題解的存在性 260
7-10 整數因子分解算法 262
7-11 非蒙特卡羅算法的例子 262
7-12 重複3次的蒙特卡羅算法 263
7-13 集合隨機元素算法 263
7-14 由蒙特卡羅算法構造拉斯維加斯算法 265
7-15 產生素數算法 265
7-16 矩陣方程問題 265
算法實現題7 266
7-1 模平方根問題 266
7-2 素數測試問題 268
7-3 集合相等問題 269
7-4 逆矩陣問題 269
7-5 多項式乘積問題 270
7-6 皇后控制問題 270
7-7 3-SAT問題 274
7-8 戰車問題 275
第8章 線性規劃與網絡流 278
算法分析題8 278
8-1 線性規劃可行區域無界的例子 278
8-2 單源最短路與線性規劃 278
8-3 網絡最大流與線性規劃 279
8-4 最小費用流與線性規劃 279
8-5 運輸計劃問題 279
8-6 單純形算法 280
8-7 邊連通度問題 281
8-8 有向無環網絡的最大流 281
8-9 無向網絡的最大流 281
8-10 最大流更新算法 282
8-11 混合圖歐拉回路問題 282
8-12 單源最短路與最小費用流 282
8-13 中國郵路問題 282
算法實現題8 283
8-1 飛行員配對方案問題 283
8-2 太空飛行計劃問題 284
8-3 最小路徑覆蓋問題 285
8-4 魔術球問題 286
8-5 圓桌問題 287
8-6 最長遞增子序列問題 287
8-7 試題庫問題 290
8-8 機器人路徑規劃問題 291
8-9 方格取數問題 294
8-10 餐巾計劃問題 298
8-11 航空路線問題 299
8-12 軟件補丁問題 300
8-13 星際轉移問題 301
8-14 孤島營救問題 302
8-15 汽車加油行駛問題 304
8-16 數字梯形問題 307
8-17 運輸問題 311
8-18 分配工作問題 314
8-19 負載平衡問題 315
8-20 最長k可重區間集問題 317
第1章 算法概述 1
算法分析題1 1
1-1 函數的漸近表達式 1
1-2 O(1)和O(2)的區別 1
1-3 按漸近階排列表達式 1
1-4 算法效率 1
1-5 硬件效率 1
1-6 函數漸近階 2
1-7 n!的階 2
1-8 3n+1問題 2
1-9 平均情況下的計算時間複雜性 2
算法實現題1 3
1-1 統計數字問題 3
1-2 字典序問題 4
1-3 最多約數問題 4
1-4 金幣陣列問題 6
1-5 最大間隙問題 8
第2章 遞歸與分治策略 11
算法分析題2 11
2-1 證明Hanoi塔問題的遞歸算法與非遞歸算法實際上是一回事 11
2-2 判斷這7個算法的正確性 12
2-3 改寫二分搜索算法 15
2-4 大整數乘法的O(nmlog(3/2))算法 16
2-5 5次n/3位整數的乘法 16
2-6 矩陣乘法 18
2-7 多項式乘積 18
2-8 O(1)空間子數組換位算法 19
2-9 O(1)空間合併算法 21
2-10 段合併排序算法 27
2-11 自然合併排序算法 28
2-12 第k小元素問題的計算時間下界 29
2-13 非增序快速排序算法 31
2-14 構造Gray碼的分治算法 31
2-15 網球循環賽日程表 32
2-16 二叉樹T的前序、中序和後序序列 35
算法實現題2 36
2-1 眾數問題 36
2-2 馬的Hamilton周遊路線問題 37
2-3 半數集問題 44
2-4 半數單集問題 46
2-5 有重複元素的排列問題 46
2-6 排列的字典序問題 47
2-7 集合劃分問題 49
2-8 集合劃分問題 50
2-9 雙色Hanoi塔問題 51
2-10 標準二維表問題 52
2-11 整數因子分解問題 53
第3章 動態規劃 54
算法分析題3 54
3-1 最長單調遞增子序列 54
3-2 最長單調遞增子序列的O(nlogn)算法 54
3-3 整數線性規劃問題 55
3-4 二維0-1背包問題 56
3-5 Ackermann函數 57
算法實現題3 59
3-1 獨立任務最優調度問題 59
3-2 最優批處理問題 61
3-3 石子合併問題 67
3-4 數字三角形問題 68
3-5 乘法表問題 69
3-6 租用遊艇問題 70
3-7 汽車加油行駛問題 70
3-8 最小m段和問題 71
3-9 圈乘運算問題 72
3-10 最大長方體問題 78
3-11 正則表達式匹配問題 79
3-12 雙調旅行售貨員問題 83
3-13 最大k乘積問題 84
3-14 最少費用購物問題 86
3-15 收集樣本問題 87
3-16 最優時間表問題 89
3-17 字符串比較問題 89
3-18 有向樹k中值問題 90
3-19 有向樹獨立k中值問題 94
3-20 有向直線m中值問題 98
3-21 有向直線2中值問題 101
3-22 樹的最大連通分支問題 103
3-23 直線k中值問題 105
3-24 直線k覆蓋問題 109
3-25 m處理器問題 113
第4章 貪心算法 116
算法分析題4 116
4-1 程序最優存儲問題 116
4-2 最優裝載問題的貪心算法 116
4-3 Fibonacci序列的哈夫曼編碼 116
4-4 最優前綴碼的編碼序列 117
算法實現題4 117
4-1 會場安排問題 117
4-2 最優合併問題 118
4-3 磁帶最優存儲問題 118
4-4 磁盤文件最優存儲問題 119
4-5 程序存儲問題 120
4-6 最優服務次序問題 120
4-7 多處最優服務次序問題 121
4-8 d森林問題 122
4-9 虛擬汽車加油問題 123
4-10 區間覆蓋問題 124
4-11 刪數問題 124
4-12 磁帶最大利用率問題 125
4-13 非單位時間任務安排問題 126
4-14 多元Huffman編碼問題 127
4-15 最優分解問題 128
第5章 回溯法 130
算法分析題5 130
5-1 裝載問題改進回溯法1 130
5-2 裝載問題改進回溯法2 131
5-3 0-1背包問題的最優解 132
5-4 最大團問題的迭代回溯法 134
5-5 旅行售貨員問題的費用上界 135
5-6 旅行售貨員問題的上界函數 136
算法實現題5 137
5-1 子集和問題 137
5-2 最小長度電路板排列問題 138
5-3 最小重量機器設計問題 140
5-4 運動員最佳配對問題 141
5-5 無分隔符字典問題 142
5-6 無和集問題 144
5-7 n色方柱問題 145
5-8 整數變換問題 150
5-9 拉丁矩陣問題 151
5-10 排列寶石問題 152
5-11 重複拉丁矩陣問題 154
5-12 羅密歐與朱麗葉的迷宮問題 156
5-13 工作分配問題 158
5-14 佈線問題 159
5-15 最佳調度問題 160
5-16 無優先級運算問題 161
5-17 世界名畫陳列館問題 163
5-18 世界名畫陳列館問題（不重複監視） 166
5-19 算m點問題 169
5-20 部落衛隊問題 171
5-21 子集樹問題 173
5-22 0-1背包問題 174
5-23 排列樹問題 176
5-24 一般解空間搜索問題 177
5-25 最短加法鏈問題 179
第6章 分支限界法 185
算法分析題6 185
6-1 0-1背包問題的棧式分支限界法 185
6-2 釋放結點空間的隊列式分支限界法 187
6-3 及時刪除不用的結點 188
6-4 用最大堆存儲活結點的優先隊列式分支限界法 189
6-5 釋放結點空間的優先隊列式分支限界法 192
6-6 團頂點數的上界 194
6-7 團頂點數改進的上界 194
6-8 修改解旅行售貨員問題的分支限界法 195
6-9 試修改解旅行售貨員問題的分支限界法，使得算法保存已產生的排列樹 197
6-10 電路板排列問題的隊列式分支限界法 199
算法實現題6 201
6-1 最小長度電路板排列問題 201
6-2 最小權頂點覆蓋問題 203
6-3 無向圖的最大割問題 206
6-4 最小重量機器設計問題 209
6-5 運動員最佳配對問題 212
6-6 n後問題 214
6-7 佈線問題 216
6-8 最佳調度問題 218
6-9 無優先級運算問題 220
6-10 世界名畫陳列館問題 223
6-11 子集空間樹問題 226
6-12 排列空間樹問題 229
6-13 一般解空間的隊列式分支限界法 232
6-14 子集空間樹問題 236
6-15 排列空間樹問題 241
6-16 一般解空間的優先隊列式分支限界法 246
6-17 推箱子問題 250
第7章 概率算法 256
算法分析題7 256
7-1 模擬正態分佈隨機變量 256
7-2 隨機抽樣算法 256
7-3 隨機產生m個整數 257
7-4 集合大小的概率算法 258
7-5 生日問題 258
7-6 易驗證問題的拉斯維加斯算法 259
7-7 用數組模擬有序鏈表 260
7-8 O(n3/2)舍伍德型排序算法 260
7-9 n後問題解的存在性 260
7-10 整數因子分解算法 262
7-11 非蒙特卡羅算法的例子 262
7-12 重複3次的蒙特卡羅算法 263
7-13 集合隨機元素算法 263
7-14 由蒙特卡羅算法構造拉斯維加斯算法 265
7-15 產生素數算法 265
7-16 矩陣方程問題 265
算法實現題7 266
7-1 模平方根問題 266
7-2 素數測試問題 268
7-3 集合相等問題 269
7-4 逆矩陣問題 269
7-5 多項式乘積問題 270
7-6 皇后控制問題 270
7-7 3-SAT問題 274
7-8 戰車問題 275
第8章 線性規劃與網絡流 278
算法分析題8 278
8-1 線性規劃可行區域無界的例子 278
8-2 單源最短路與線性規劃 278
8-3 網絡最大流與線性規劃 279
8-4 最小費用流與線性規劃 279
8-5 運輸計劃問題 279
8-6 單純形算法 280
8-7 邊連通度問題 281
8-8 有向無環網絡的最大流 281
8-9 無向網絡的最大流 281
8-10 最大流更新算法 282
8-11 混合圖歐拉回路問題 282
8-12 單源最短路與最小費用流 282
8-13 中國郵路問題 282
算法實現題8 283
8-1 飛行員配對方案問題 283
8-2 太空飛行計劃問題 284
8-3 最小路徑覆蓋問題 285
8-4 魔術球問題 286
8-5 圓桌問題 287
8-6 最長遞增子序列問題 287
8-7 試題庫問題 290
8-8 機器人路徑規劃問題 291
8-9 方格取數問題 294
8-10 餐巾計劃問題 298
8-11 航空路線問題 299
8-12 軟件補丁問題 300
8-13 星際轉移問題 301
8-14 孤島營救問題 302
8-15 汽車加油行駛問題 304
8-16 數字梯形問題 307
8-17 運輸問題 311
8-18 分配工作問題 314
8-19 負載平衡問題 315
8-20 最長k可重區間集問題 317
今日66折
您曾經瀏覽過的商品
購物須知
大陸出版品因裝訂品質及貨運條件與台灣出版品落差甚大，除封面破損、內頁脫落等較嚴重的狀態，其餘商品將正常出貨。
特別提醒：部分書籍附贈之內容(如音頻mp3或影片dvd等)已無實體光碟提供，需以QR CODE 連結至當地網站註冊“並通過驗證程序”，方可下載使用。
無現貨庫存之簡體書，將向海外調貨：
海外有庫存之書籍，等候約45個工作天;
海外無庫存之書籍，平均作業時間約60個工作天，然不保證確定可調到貨，尚請見諒。
為了保護您的權益，「三民網路書店」提供會員七日商品鑑賞期(收到商品為起始日)。
若要辦理退貨，請在商品鑑賞期內寄回，且商品必須是全新狀態與完整包裝(商品、附件、發票、隨貨贈品等)否則恕不接受退貨。