第1章 算法概述 1
1.1 引言 1
1.1.1 算法的描述 2
1.1.2 算法的特性 2
1.1.3 為什么學(xué)習(xí)算法 3
1.2 算法的設(shè)計(jì) 5
1.3 算法的分析 8
1.3.1 正確性分析 9
1.3.2 時(shí)空效率分析 10
1.3.3 時(shí)空特性分析 13
1.4 解決問題的一般步驟 13
1.5 小結(jié) 15
1.6 習(xí)題 16
第2章 遞歸與分治策略 17
2.1 遞歸算法 18
2.1.1 遞歸的概念 18
2.1.2 具有遞歸特性的問題 19
2.1.3 遞歸算法分析 22
2.2 分治策略 28
2.2.1 分治法的基本步驟 28
2.2.2 分治法的適用條件 29
2.2.3 二分搜索技術(shù) 29
2.2.4 棋盤覆蓋問題 30
2.2.5 快速排序 33
2.2.6 大整數(shù)乘法 36
2.2.7 矩陣乘法 39
2.3 ACM經(jīng)典問題解析 45
2.3.1 蜂窩問題
(難度：★☆☆☆☆) 45
2.3.2 Humble Numbers
(難度：★★☆☆☆) 46
2.3.3 Copying Books
(難度：★★★☆☆) 48
2.3.4 Fractal(難度：★★★☆☆) 51
2.3.5 TOYS(難度：★★☆☆☆) 53
2.3.6 Cable master
(難度：★★☆☆☆) 56
2.4 小結(jié) 58
2.5 習(xí)題 59
第3章 動(dòng)態(tài)規(guī)劃 62
3.1 何謂動(dòng)態(tài)規(guī)劃 63
3.1.1 動(dòng)態(tài)規(guī)劃的基本思想 63
3.1.2 設(shè)計(jì)動(dòng)態(tài)規(guī)劃法的步驟 63
3.1.3 動(dòng)態(tài)規(guī)劃問題的特征 63
3.1.4 動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系 64
3.2 矩陣連乘積問題 65
3.2.1 分析最優(yōu)解的結(jié)構(gòu) 67
3.2.2 建立遞歸關(guān)系 68
3.2.3 計(jì)算最優(yōu)值 69
3.2.4 構(gòu)造最優(yōu)解 71
3.3 動(dòng)態(tài)規(guī)劃算法的基本要素 72
3.3.1 最優(yōu)子結(jié)構(gòu) 72
3.3.2 重疊子問題 72
3.3.3 備忘錄方法 73
3.4 最長(zhǎng)公共子序列 75
3.4.1 最長(zhǎng)公共子序列的結(jié)構(gòu) 75
3.4.2 子問題的遞歸結(jié)構(gòu) 76
3.4.3 計(jì)算最優(yōu)值 76
3.4.4 構(gòu)造最長(zhǎng)公共子序列 78
3.5 最大子段和 78
3.5.1 遞歸關(guān)系分析 78
3.5.2 算法實(shí)現(xiàn) 79
3.6 0-1背包問題 80
3.6.1 遞歸關(guān)系分析 81
3.6.2 算法實(shí)現(xiàn) 81
3.7 ACM經(jīng)典問題解析 83
3.7.1 數(shù)塔(難度：★★☆☆☆) 83
3.7.2 免費(fèi)餡餅
(難度：★★★☆☆) 84
3.7.3 Dividing
(難度：★★★☆☆) 86
3.7.4 Win the Bonus
(難度：★★★★☆) 88
3.7.5 Monkey and Banana
(難度：★★★★☆) 90
3.7.6 Railroad(難度：★★★★☆) 93
3.8 小結(jié) 96
3.9 習(xí)題 97
第4章 貪心算法 101
4.1 活動(dòng)安排問題 102
4.2 貪心算法的理論基礎(chǔ) 104
4.2.1 貪心算法的基本思想 105
4.2.2 貪心算法的基本要素 105
4.2.3 貪心算法的基本步驟 106
4.3 刪數(shù)問題 107
4.3.1 貪心策略選擇 107
4.3.2 最優(yōu)子結(jié)構(gòu) 107
4.3.3 算法實(shí)現(xiàn) 107
4.3.4 復(fù)雜度分析 108
4.4 背包問題 109
4.4.1 最優(yōu)子結(jié)構(gòu)性質(zhì) 109
4.4.2 貪心選擇性質(zhì) 110
4.4.3 算法實(shí)現(xiàn) 110
4.4.4 復(fù)雜度分析 112
4.5 最優(yōu)裝載問題 112
4.5.1 貪心選擇性質(zhì) 113
4.5.2 最優(yōu)子結(jié)構(gòu)性質(zhì) 113
4.5.3 算法實(shí)現(xiàn) 113
4.5.4 復(fù)雜度分析 114
4.6 單源最短路徑 115
4.6.1 算法基本思想 115
4.6.2 貪心選擇性質(zhì) 116
4.6.3 最優(yōu)子結(jié)構(gòu)性質(zhì) 117
4.6.4 Dijkstra算法實(shí)現(xiàn) 117
4.6.5 復(fù)雜度分析 119
4.7 多處最優(yōu)服務(wù)次序問題 120
4.7.1 貪心選擇策略 120
4.7.2 貪心選擇性質(zhì) 120
4.7.3 最優(yōu)子結(jié)構(gòu)性質(zhì) 120
4.7.4 算法實(shí)現(xiàn) 121
4.7.5 復(fù)雜度分析 122
4.8 ACM經(jīng)典問題解析 122
4.8.1 Fat Mouse Trade
(難度：★★☆☆☆) 122
4.8.2 Sorting the Photos
(難度：★★★☆☆) 124
4.8.3 Moving Tables
(難度：★★★☆☆) 126
4.8.4 Box of Bricks
(難度：★★★★☆) 127
4.8.5 Wooden Sticks
(難度：★★★★☆) 128
4.8.6 釣魚問題
(難度：★★★★☆) 130
4.8.7 樹形DP問題
(難度：★★★★☆) 133
4.8.8 Frogs' Neighborhood
(難度：★★★☆☆) 135
4.9 小結(jié) 137
4.10 習(xí)題 138
第5章 回溯法 140
5.1 回溯法的基本思想 140
5.1.1 問題的解空間 141
5.1.2 搜索的解空間 143
5.1.3 回溯的基本步驟 144
5.1.4 回溯法實(shí)現(xiàn) 145
5.2 圖的m著色問題 147
5.2.1 問題的解空間 147
5.2.2 確定約束條件 148
5.2.3 搜索解空間 148
5.2.4 代碼實(shí)現(xiàn) 148
5.2.5 算法時(shí)間復(fù)雜度分析 150
5.3 n皇后問題 150
5.3.1 解空間 151
5.3.2 約束條件 151
5.3.3 搜索過程 151
5.3.4 算法的時(shí)間復(fù)雜度分析 154
5.4 裝載問題 154
5.4.1 問題的解空間 154
5.4.2 約束條件 154
5.4.3 限界條件 154
5.4.4 搜索過程 155
5.4.5 算法效率分析 157
5.5 0-1背包問題 157
5.5.1 解空間 157
5.5.2 約束條件 157
5.5.3 限界條件 157
5.5.4 搜索過程 158
5.5.5 算法效率分析 160
5.6 旅行商問題 160
5.6.1 解空間 161
5.6.2 約束條件 161
5.6.3 限界條件 161
5.6.4 搜索解空間 161
5.6.5 時(shí)間復(fù)雜度分析 163
5.7 批處理流水作業(yè)調(diào)度問題 163
5.7.1 解空間 163
5.7.2 約束條件 164
5.7.3 限界條件 164
5.7.4 搜索過程 164
5.7.5 時(shí)間復(fù)雜度分析 166
5.8 ACM經(jīng)典問題解析 166
5.8.1 Dreisam Equations
(難度：★★★☆☆) 166
5.8.2 A Plug for UNIX
(難度：★★★☆☆) 170
5.8.3 回文構(gòu)詞檢測(cè)(Anagram Checker)
(難度：★★☆☆☆) 174
5.8.4 Unshuffle
(難度：★★★☆☆) 178
5.9 小結(jié) 181
5.10 習(xí)題 181
第6章 分支限界算法 183
6.1 分支限界法的基本理論 184
6.1.1 分支限界法的搜索策略 184
6.1.2 分支結(jié)點(diǎn)的選擇 185
6.1.3 限界函數(shù) 185
6.2 單源最短路徑問題 186
6.2.1 問題描述 186
6.2.2 算法描述與設(shè)計(jì) 186
6.2.3 算法實(shí)現(xiàn) 188
6.3 裝載問題 190
6.3.1 問題描述 190
6.3.2 算法設(shè)計(jì)與實(shí)現(xiàn) 191
6.4 0-1背包問題 196
6.4.1 問題描述 196
6.4.2 算法描述與設(shè)計(jì) 196
6.4.3 算法實(shí)現(xiàn) 198
6.5 旅行商問題 202
6.5.1 問題描述 202
6.5.2 算法描述與設(shè)計(jì) 203
6.5.3 算法實(shí)現(xiàn) 204
6.7 ACM經(jīng)典問題 209
6.7.1 布線問題
(難度：★★★☆☆) 209
6.7.2 方格調(diào)整問題
(難度：★★★☆☆) 212
6.7.3 旅行售貨員問題
(難度：★★★☆☆) 213
6.7.4 Grandpa's Estate
(難度：★★★☆☆) 216
6.7.5 Find The Multiple
(難度：★★★☆☆) 218
6.8 小結(jié) 220
6.9 習(xí)題 220
第7章 圖的搜索算法 222
7.1 圖的廣度優(yōu)先搜索遍歷 224
7.1.1 算法描述與分析 224
7.1.2 程序?qū)崿F(xiàn) 227
7.2 圖的深度優(yōu)先搜索遍歷 232
7.2.1 算法描述與分析 232
7.2.2 程序?qū)崿F(xiàn) 234
7.2.3 有向無圈圖的拓?fù)渑判?237
7.3 有向圖的強(qiáng)連通分支 244
7.3.1 算法描述與分析 244
7.3.2 程序?qū)崿F(xiàn) 247
7.4 無向圖的雙連通分支 250
7.4.1 算法描述與分析 250
7.4.2 程序?qū)崿F(xiàn) 254
7.5 流網(wǎng)絡(luò)與最大流問題 256
7.5.1 算法描述與分析 256
7.5.2 程序?qū)崿F(xiàn) 263
7.6 ACM經(jīng)典問題解析 265
7.6.1 Is It A Tree?
(難度：★★★☆☆) 265
7.6.2 Stockbroker Grapevine
(難度：★★★☆☆) 267
7.6.3 A Plug for UNIX
(難度：★★★☆☆) 269
7.7 小結(jié) 273
7.8 習(xí)題 273
第8章 公鑰加密算法 281
8.1 RSA公鑰密碼算法 283
8.1.1 算法描述 283
8.1.2 快速模冪算法 284
8.1.3 素?cái)?shù)的生成 285
8.1.4 擴(kuò)展歐幾里得算法 288
8.2 因子分解算法 290
8.2.1 Pollard's p-1法 290
8.2.2 Pollard's rho法 291
8.3 離散對(duì)數(shù)密碼算法 293
8.3.1 Diffie-Hellman密鑰交換
協(xié)議 293
8.3.2 ElGamal公鑰密碼算法 294
8.4 離散對(duì)數(shù)算法 295
8.4.1 小步/大步法 295
8.4.2 Pohlig-Hellman法 297
8.5 ACM的經(jīng)典問題 299
8.5.1 簡(jiǎn)單的加密算法
(難度：★★☆☆☆) 299
8.5.2 古代密碼
(難度：★★★☆☆) 300
8.6 小結(jié) 302

8.7 習(xí)題 303
第9章 P和NP問題淺析 304
9.1 決策問題和優(yōu)化問題 305
9.2 何謂P類和NP類問題 306
9.2.1 P類問題 306
9.2.2 NP類問題 307
9.3 (確定性)圖靈機(jī) 307
9.3.1 圖靈機(jī)的定義 307
9.3.2 k帶圖靈機(jī)形式化描述 308
9.3.3 圖靈機(jī)計(jì)算實(shí)例 308
9.4 非確定性圖靈機(jī) 311
9.4.1 非確定性圖靈機(jī)定義 311
9.4.2 非確定性圖靈機(jī)形式化
描述 312
9.4.3 非確定性圖靈機(jī)計(jì)算實(shí)例 312
9.4.4 非確定性算法 313
9.4.5 NP類問題的定義 314
9.4.6 NP難(NP-hard) 315
9.5 NP完全問題P* 315
9.5.1 定義 316
9.5.2 多項(xiàng)式時(shí)間規(guī)約 316
9.5.3 庫克定理 318
9.5.4 3-SAT問題 320
9.5.5 NP完全問題的近似算法 321
9.6 NP難問題的近似算法* 332
9.6.1 旅行商問題的近似算法 333
9.6.2 背包問題的近似算法 339
9.7 小結(jié) 342
9.8 習(xí)題 343
附錄A 求和 345
附錄B 數(shù)論入門 352
參考文獻(xiàn) 356