算法的樂趣（第2版）

前言 iii
致謝 vi
第 1章 圖像處理的幾個簡單算法 1
1.1 灰度（灰階）算法 1
1.1.1 平均值法 2
1.1.2 值法 2
1.1.3 （經驗）權重法 2
1.2 二值化（閾值）算法 3
1.2.1 Wellner 1993算法原理 4
1.2.2 Wellner 1993算法實現(xiàn) 6
1.2.3 Bradley & Roth算法原理 8
1.2.4 Bradley & Roth算法實現(xiàn) 10
1.3 考眼力游戲與圖像求差 12
1.4 梯度算法與圖像清晰度 13
1.4.1 Brenner梯度函數(shù) 14
1.4.2 EVA梯度函數(shù) 15
1.4.3 Tenengrad梯度函數(shù) 16
1.4.4 Laplacian梯度函數(shù) 17
1.5 邊緣檢測與落雪效果 18
1.5.1 梯度函數(shù)與邊緣檢測 19
1.5.2 研究積雪的效果 20
第 2章 分離軸算法與碰撞檢測 23
2.1 計算幾何基礎 23
2.1.1 向量的加法和減法 23
2.1.2 向量的點積 24
2.1.3 法向量 24
2.1.4 投影 25
2.2 分離軸定理 25
2.2.1 算法原理 26
2.2.2 基本數(shù)據(jù)模型 26
2.2.3 如何找分離軸 27
2.2.4 計算投影 29
2.2.5 后，碰撞檢測 30
2.3 總結 31
2.4 參考資料 31
第3章 垃圾郵件過濾與貝葉斯分類算法 32
3.1 貝葉斯定理 32
3.1.1 概率和條件概率 33
3.1.2 有多個條件時的條件概率 33
*.* 貝葉斯理論 33
*.*.1 貝葉斯理論原理 34
*.*.2 貝葉斯分類器原理 34
*.*.3 貝葉斯理論的應用示例 34
*.*.4 貝葉斯理論的使用方法 35
3.3 垃圾郵件分類器原理 36
3.3.1 第 一步：準備工作 36
3.*.* 第二步：訓練分類器 38
3.3.3 第三步：應用分類器 40
3.4 總結 42
3.5 參考資料 42
第4章 匹配算法——簡單的中文分詞算法 43
4.1 匹配算法 43
4.1.1 正向匹配算法 43
4.1.2 逆向匹配算法 45
4.1.3 算法分析 46
4.2 算法實現(xiàn) 46
4.2.1 詞典及詞典匹配 46
4.2.2 正向匹配算法實現(xiàn) 47
4.2.3 逆向匹配算法實現(xiàn) 48
4.3 總結 50
4.4 參考資料 50
第5章 3個水桶等分8升水的問題 51
5.1 問題與求解思路 52
5.2 建立數(shù)學模型 53
5.2.1 狀態(tài)的數(shù)學模型與狀態(tài)樹 53
5.2.2 倒水動作的數(shù)學模型 54
5.3 搜索算法 55
5.3.1 狀態(tài)樹的遍歷 55
5.*.* 剪枝和重復狀態(tài)判斷 56
5.4 算法實現(xiàn) 57
5.5 總結 59
5.6 參考資料 59
第6章 妖怪與和尚過河問題 60
6.1 問題與求解思路 61
6.2 建立數(shù)學模型 61
6.2.1 狀態(tài)的數(shù)學模型與狀態(tài)樹 62
6.2.2 過河動作的數(shù)學模型 62
6.3 搜索算法 64
6.3.1 狀態(tài)樹的遍歷 65
6.*.* 剪枝和重復狀態(tài)判斷 66
6.4 算法實現(xiàn) 66
6.5 總結 68
6.6 參考資料 68
第7章 穩(wěn)定匹配與舞伴問題 69
7.1 穩(wěn)定匹配問題 69
7.1.1 什么是穩(wěn)定匹配 69
7.1.2 Gale-Shapley 算法原理 70
7.2 Gale-Shapley 算法的應用實例 72
7.2.1 算法實現(xiàn) 72
7.2.2 改進優(yōu)化：空間換時間 75
7.3 有多少穩(wěn)定匹配 76
7.3.1 窮舉所有的完美匹配 77
7.*.* 不穩(wěn)定因素的判斷算法 78
7.3.3 窮舉的結果 79
7.4 二部圖與二分匹配 80
7.4.1 匹配與匈牙利算法 81
7.4.2 帶權匹配與Kuhn-Munkres算法 84
7.5 總結 89
7.6 參考資料 90
第8章 愛因斯坦的思考題 91
8.1 問題的答案 92
8.2 分析問題的數(shù)學模型 92
8.2.1 基本模型定義 92
8.2.2 線索模型定義 94
8.3 算法設計 95
8.3.1 窮舉所有的組合結果 95
8.*.* 利用線索判定結果的正確性 97
8.4 總結 99
8.5 參考資料 100
第9章 項目管理與圖的拓撲排序 101
9.1 AOV網和AOE網 103
9.2 拓撲排序 104
9.2.1 拓撲排序的基本過程 104
9.2.2 按照活動開始時間排序 104
9.3 關鍵路徑算法 107
9.3.1 什么是關鍵路徑 108
9.*.* 計算關鍵路徑的算法 109
9.4 總結 112
9.5 參考資料 113
第 10章 限流算法與兩個桶 114
10.1 漏桶算法 114
10.2 令牌桶算法 117
10.2.1 原理 117
10.2.2 算法細節(jié) 117
10.2.3 CRateLimiter類 119
10.2.4 測試CRateLimiter類 120
10.3 總結 122
10.4 參考資料 122
第 11章 算法與歷法 123
11.1 格里歷（公歷）生成算法 123
11.1.1 格里歷的歷法規(guī)則 123
11.1.2 今天星期幾 124
11.1.3 生成日歷的算法 129
11.1.4 日歷變更那點事兒 130
11.2 二十四節(jié)氣的天文學計算 132
11.2.1 二十四節(jié)氣的起源 132
11.2.2 二十四節(jié)氣的天文學定義 132
11.2.3 VSOP-82/87行星理論 135
11.2.4 誤差修正——章動 138
11.2.5 誤差修正——光行差 140
11.2.6 用牛頓迭代法計算二十四節(jié)氣 141
11.3 農歷朔日（新月）的天文學計算 144
11.3.1 日月合朔的天文學定義 144
11.*.* ELP-2000/82月球理論 145
11.3.3 誤差修正——地球軌道離心率修正 146
11.3.4 誤差修正——黃經攝動 147
11.3.5 月球地心視黃經和后的修正——地球章動 148
11.3.6 用牛頓迭代法計算日月合朔 149
11.4 農歷的生成算法 150
11.4.1 中國農歷的起源與歷法規(guī)則 151
11.4.2 中國農歷的推算 156
11.4.3 一個簡單的“年歷” 164
11.5 總結 164
11.6 參考資料 165
第 12章 實驗數(shù)據(jù)與曲線擬合 166
12.1 曲線擬合 166
12.1.1 曲線擬合的定義 166
12.1.2 簡單線性數(shù)據(jù)擬合的例子 166
12.2 小二乘法曲線擬合 167
12.2.1 小二乘法原理 168
12.2.2 高斯消元法求解方程組 169
12.2.3 小二乘法解決“速度與加速度”實驗 170
12.3 三次樣條曲線擬合 171
12.3.1 插值函數(shù) 172
12.*.* 樣條函數(shù)的定義 172
12.3.3 邊界條件 173
12.3.4 推導三次樣條函數(shù) 174
12.3.5 追趕法求解方程組 177
12.3.6 三次樣條曲線擬合算法實現(xiàn) 179
12.3.7 三次樣條曲線擬合的效果 181
12.4 總結 183
12.5 參考資料 183
第 13章 非線性方程與牛頓迭代法 184
13.1 非線性方程求解的常用方法 184
13.1.1 公式法 184
13.1.2 二分逼近法 185
1*.* 牛頓迭代法的數(shù)學原理 186
13.3 用牛頓迭代法求解非線性方程的實例 187
13.3.1 導函數(shù)的求解與近似公式 187
13.*.* 算法實現(xiàn) 188
13.4 參考資料 188
第 14章 計算幾何與計算機圖形學 189
14.1 計算幾何的基本算法 189
14.1.1 點與矩形的關系 190
14.1.2 點與圓的關系 190
14.1.3 矢量的基礎知識 191
14.1.4 點與直線的關系 193
14.1.5 直線與直線的關系 194
14.1.6 點與多邊形的關系 196
14.2 直線生成算法 199
14.2.1 什么是光柵掃描轉換 200
14.2.2 數(shù)值微分法 200
14.2.3 Bresenham算法 202
14.2.4 對稱直線生成算法 204
14.2.5 兩步算法 205
14.2.6 其他直線生成算法 207
14.3 圓生成算法 208
14.3.1 圓的八分對稱性 208
14.*.* 中點畫圓算法 209
14.3.3 改進的中點畫圓算法——Bresenham算法 210
14.3.4 正負判定畫圓法 211
14.4 橢圓生成算法 212
14.4.1 中點畫橢圓算法 213
14.4.2 Bresenham橢圓生成算法 216
14.5 多邊形區(qū)域填充算法 218
14.5.1 種子填充算法 219
14.5.2 掃描線填充算法 224
14.5.3 改進的掃描線填充算法 231
14.5.4 邊界標志填充算法 235
14.6 總結 238
14.7 參考資料 238
第 15章 音頻頻譜和均衡器與傅里葉變換算法 239
15.1 實時頻譜顯示的原理 239
15.2 離散傅里葉變換 240
15.2.1 什么是傅里葉變換 241
15.2.2 傅里葉變換原理 241
15.2.3 快速傅里葉變換算法的實現(xiàn) 245
15.3 傅里葉變換與音頻播放的實時頻譜顯示 247
15.3.1 頻域數(shù)值的特點分析 247
15.*.* 從音頻數(shù)據(jù)到功率頻譜 248
15.3.3 音頻播放時實時頻譜顯示的例子 251
15.4 破解電話號碼的小把戲 253
15.4.1 撥號音的頻譜分析 253
15.4.2 根據(jù)頻譜數(shù)據(jù)反推電話號碼 255
15.5 離散傅里葉逆變換 256
15.5.1 快速傅里葉逆變換的推導 256
15.5.2 快速傅里葉逆變換的算法實現(xiàn) 257
15.6 利用傅里葉變換實現(xiàn)頻域均衡器 257
15.6.1 頻域均衡器的實現(xiàn)原理 258
15.6.2 頻域信號的增益與衰減 258
15.6.3 均衡器的實現(xiàn)——仿 Foobar的18段均衡器 260
15.7 總結 261
15.8 參考資料 262
第 16章 全局解與遺傳算法 263
16.1 遺傳算法的原理 263
16.1.1 遺傳算法的基本概念 264
16.1.2 遺傳算法的處理流程 265
16.2 遺傳算法求解0-1背包問題 270
16.2.1 基因編碼和種群初始化 270
16.2.2 適應度函數(shù) 271
16.2.3 選擇算子設計與輪盤賭算法 272
16.2.4 交叉算子設計 273
16.2.5 變異算子設計 274
16.2.6 這就是遺傳算法 275
16.3 總結 276
16.4 參考資料 276
第 17章 計算器程序與大整數(shù)計算 277
17.1 哦，溢出了，出洋相的計算器程序 277
17.2 大整數(shù)計算的原理 278
17.2.1 大整數(shù)加法 279
17.2.2 大整數(shù)減法 281
17.2.3 大整數(shù)乘法 283
17.2.4 大整數(shù)除法與模 284
17.2.5 大整數(shù)乘方運算 286
17.3 大整數(shù)類的使用 287
17.3.1 與 Windows的計算器程序一決高下 287
17.*.* 公約數(shù)和小公倍數(shù) 287
17.3.3 用擴展歐幾里得算法求模的逆元 290
17.4 總結 292
17.5 參考資料 292
第 18章 RSA算法——加密與簽名 293
18.1 RSA 算法的開胃菜 293
18.1.1 將模冪運算轉化為模乘運算 294
18.1.2 模乘運算與蒙哥馬利算法 295
18.1.3 模冪算法 296
18.1.4 素數(shù)檢驗與米勒 拉賓算法 296
18.2 RSA算法原理 299
18.2.1 RSA算法的數(shù)學理論 300
18.2.2 加密和解密算法 300
18.2.3 RSA 算法的安全性 301
18.3 數(shù)據(jù)塊分組加密 302
18.3.1 字節(jié)流與大整數(shù)的轉換 302
18.*.* PCKS與OAEP加密填充模式 303
18.3.3 數(shù)據(jù)加密算法實現(xiàn) 305
18.3.4 數(shù)據(jù)解密算法實現(xiàn) 305
18.4 RSA 簽名與身份驗證 306
18.4.1 RSASSA-PKCS與RSASSA-PSS簽名填充模式 307
18.4.2 簽名算法實現(xiàn) 309
18.4.3 驗證簽名算法實現(xiàn) 309
18.5 總結 310
18.6 參考資料 311
第 19章 數(shù)獨游戲 312
19.1 數(shù)獨游戲的規(guī)則與技巧 312
19.1.1 數(shù)獨游戲的規(guī)則 312
19.1.2 數(shù)獨游戲的常用技巧 313
19.2 計算機求解數(shù)獨問題 314
19.2.1 建立問題的數(shù)學模型 315
19.2.2 算法實現(xiàn) 316
19.2.3 與傳統(tǒng)窮舉方法的結果對比 318
19.3 關于數(shù)獨的趣味話題 318
19.3.1 數(shù)獨游戲有多少終盤 318
19.*.* 難的數(shù)獨游戲 319
19.4 總結 320
19.5 參考資料 320
第 20章 華容道游戲 321
20.1 華容道游戲介紹 321
20.2 自動求解的算法原理 322
20.2.1 定義棋盤的局面 323
20.2.2 算法思路 324
20.3 自動求解的算法實現(xiàn) 326
20.3.1 棋局狀態(tài)與Zobrist哈希算法 326
20.*.* 重復棋局和左右鏡像的處理 329
20.3.3 正確結果的判斷條件 330
20.3.4 武將棋子的移動 331
20.3.5 棋局的搜索算法 333
20.4 總結 335
20.5 參考資料 335
第 21章 A*尋徑算法 336
21.1 尋徑算法演示程序 336
21.2 Dijkstra算法 338
21.2.1 Dijkstra算法原理 338
21.2.2 Dijkstra算法實現(xiàn) 338
21.2.3 Dijkstra算法演示程序 339
21.3 帶啟發(fā)的搜索算法——A*算法 341
21.3.1 A*算法原理 342
21.*.* 常用的距離評估函數(shù) 343
21.3.3 A*算法實現(xiàn) 346
21.4 總結 348
21.5 參考資料 348
第 22章 俄羅斯方塊游戲 349
22.1 俄羅斯方塊游戲規(guī)則 350
22.2 俄羅斯方塊游戲人工智能的算法原理 351
22.2.1 影響評價結果的因素 351
22.2.2 常用的俄羅斯方塊游戲人工智能算法 352
22.2.3 Pierre Dellacherie算法 353
22.3 Pierre Dellacherie算法實現(xiàn) 355
22.3.1 基本數(shù)學模型和數(shù)據(jù)結構定義 356
22.*.* 算法實現(xiàn) 358
22.4 總結 364
22.5 參考資料 365
第 23章 博弈樹與棋類游戲 366
23.1 棋類游戲的 AI 366
23.1.1 博弈與博弈樹 367
23.1.2 極大極小值算法 368
23.1.3 負極大值算法 369
23.1.4 “α-β”剪枝算法 370
23.1.5 估值函數(shù) 372
23.1.6 置換表與哈希函數(shù) 373
23.1.7 開局庫與終局庫 375
2*.* 井字棋——簡單的博弈游戲 376
2*.*.1 棋盤與棋子的數(shù)學模型 376
2*.*.2 估值函數(shù)與估值算法 377
2*.*.3 如何產生走法（落子方法） 379
23.3 奧賽羅棋（黑白棋） 380
23.3.1 棋盤與棋子的數(shù)學模型 382
23.*.* 估值函數(shù)與估值算法 385
23.3.3 搜索算法實現(xiàn) 388
23.3.4 終結果 392
23.4 五子棋 392
23.4.1 棋盤與棋子的數(shù)學模型 394
23.4.2 估值函數(shù)與估值算法 395
23.4.3 搜索算法實現(xiàn) 399
23.4.4 終結果 400
23.5 總結 401
23.6 參考資料 401
第 24章 KNN算法與手寫數(shù)字識別 403
24.1 KNN算法原理 403
24.1.1 算法工作原理 404
24.1.2 來個例子，增加點感性認識 405
24.2 手寫數(shù)字識別程序設計 406
24.2.1 數(shù)字文件的格式 406
24.2.2 樣本和數(shù)據(jù)集的處理 408
24.2.3 訓練和測試數(shù)據(jù) 410
24.3 總結 411
24.4 參考資料 411
第 25章 有趣的變聲器 412
25.1 聲調的變化 412
25.2 聲調變化的算法實現(xiàn) 413
25.2.1 回顧DFT 413
25.2.2 改變聲調的原理 414
25.2.3 理解Stephan M. Bernsee算法實現(xiàn) 417
25.3 聲調變化的算法改進 421
25.3.1 支持多聲道音頻數(shù)據(jù) 421
25.*.* 算法效率改進 422
25.4 參考資料 422