算法的樂趣, 2/e

王晓华

硕士毕业于华中科技大学，曾任职于中兴通讯上海研发中心，担任软件工程师、开发经理和PON业务软件负责人，目前兼任步威软件技术有限公司CTO和Boolan软件技术首席咨询师。

前言 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算法實現 6

1.2.3 Bradley & Roth算法原理 8

1.2.4 Bradley & Roth算法實現 10

1.3 考眼力游戲與圖像求差 12

1.4 梯度算法與圖像清晰度 13

1.4.1 Brenner梯度函數 14

1.4.2 EVA梯度函數 15

1.4.3 Tenengrad梯度函數 16

1.4.4 Laplacian梯度函數 17

1.5 邊緣檢測與落雪效果 18

1.5.1 梯度函數與邊緣檢測 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 基本數據模型 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

3.2 貝葉斯理論 33

3.2.1 貝葉斯理論原理 34

3.2.2 貝葉斯分類器原理 34

3.2.3 貝葉斯理論的應用示例 34

3.2.4 貝葉斯理論的使用方法 35

3.3 垃圾郵件分類器原理 36

3.3.1 第 一步：準備工作 36

3.3.2 第二步：訓練分類器 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 算法實現 46

4.2.1 詞典及詞典匹配 46

4.2.2 正向最大匹配算法實現 47

4.2.3 逆向最大匹配算法實現 48

4.3 總結 50

4.4 參考資料 50

第5章 3個水桶等分8升水的問題 51

5.1 問題與求解思路 52

5.2 建立數學模型 53

5.2.1 狀態的數學模型與狀態樹 53

5.2.2 倒水動作的數學模型 54

5.3 搜索算法 55

5.3.1 狀態樹的遍歷 55

5.3.2 剪枝和重復狀態判斷 56

5.4 算法實現 57

5.5 總結 59

5.6 參考資料 59

第6章 妖怪與和尚過河問題 60

6.1 問題與求解思路 61

6.2 建立數學模型 61

6.2.1 狀態的數學模型與狀態樹 62

6.2.2 過河動作的數學模型 62

6.3 搜索算法 64

6.3.1 狀態樹的遍歷 65

6.3.2 剪枝和重復狀態判斷 66

6.4 算法實現 66

6.5 總結 68

6.6 參考資料 68

第7章 穩定匹配與舞伴問題 69

7.1 穩定匹配問題 69

7.1.1 什麽是穩定匹配 69

7.1.2 Gale-Shapley 算法原理 70

7.2 Gale-Shapley 算法的應用實例 72

7.2.1 算法實現 72

7.2.2 改進優化：空間換時間 75

7.3 有多少穩定匹配 76

7.3.1 窮舉所有的完美匹配 77

7.3.2 不穩定因素的判斷算法 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 分析問題的數學模型 92

8.2.1 基本模型定義 92

8.2.2 線索模型定義 94

8.3 算法設計 95

8.3.1 窮舉所有的組合結果 95

8.3.2 利用線索判定結果的正確性 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.3.2 計算關鍵路徑的算法 109

9.4 總結 112

9.5 參考資料 113

第 10章 限流算法與兩個桶 114

10.1 漏桶算法 114

10.2 令牌桶算法 117

10.2.1 原理 117

10.2.2 算法細節 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 格裡歷的歷法規則 123

11.1.2 今天星期幾 124

11.1.3 生成日歷的算法 129

11.1.4 日歷變更那點事兒 130

11.2 二十四節氣的天文學計算 132

11.2.1 二十四節氣的起源 132

11.2.2 二十四節氣的天文學定義 132

11.2.3 VSOP-82/87行星理論 135

11.2.4 誤差修正——章動 138

11.2.5 誤差修正——光行差 140

11.2.6 用牛頓迭代法計算二十四節氣 141

11.3 農歷朔日（新月）的天文學計算 144

11.3.1 日月合朔的天文學定義 144

11.3.2 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 中國農歷的起源與歷法規則 151

11.4.2 中國農歷的推算 156

11.4.3 一個簡單的“年歷” 164

11.5 總結 164

11.6 參考資料 165

第 12章 實驗數據與曲線擬合 166

12.1 曲線擬合 166

12.1.1 曲線擬合的定義 166

12.1.2 簡單線性數據擬合的例子 166

12.2 最小二乘法曲線擬合 167

12.2.1 最小二乘法原理 168

12.2.2 高斯消元法求解方程組 169

12.2.3 最小二乘法解決“速度與加速度”實驗 170

12.3 三次樣條曲線擬合 171

12.3.1 插值函數 172

12.3.2 樣條函數的定義 172

12.3.3 邊界條件 173

12.3.4 推導三次樣條函數 174

12.3.5 追趕法求解方程組 177

12.3.6 三次樣條曲線擬合算法實現 179

12.3.7 三次樣條曲線擬合的效果 181

12.4 總結 183

12.5 參考資料 183

第 13章 非線性方程與牛頓迭代法 184

13.1 非線性方程求解的常用方法 184

13.1.1 公式法 184

13.1.2 二分逼近法 185

13.2 牛頓迭代法的數學原理 186

13.3 用牛頓迭代法求解非線性方程的實例 187

13.3.1 導函數的求解與近似公式 187

13.3.2 算法實現 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 數值微分法 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.3.2 中點畫圓算法 209

14.3.3 改進的中點畫圓算法——Bresenham算法 210

14.3.4 正負判定畫圓法 211

14.4 橢圓生成算法 212

14.4.1 中點畫橢圓算法 213

14.4.2 Bresenham橢圓生成算法 216

14.5 多邊形區域填充算法 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 快速傅里葉變換算法的實現 245

15.3 傅里葉變換與音頻播放的實時頻譜顯示 247

15.3.1 頻域數值的特點分析 247

15.3.2 從音頻數據到功率頻譜 248

15.3.3 音頻播放時實時頻譜顯示的例子 251

15.4 破解電話號碼的小把戲 253

15.4.1 撥號音的頻譜分析 253

15.4.2 根據頻譜數據反推電話號碼 255

15.5 離散傅里葉逆變換 256

15.5.1 快速傅里葉逆變換的推導 256

15.5.2 快速傅里葉逆變換的算法實現 257

15.6 利用傅里葉變換實現頻域均衡器 257

15.6.1 頻域均衡器的實現原理 258

15.6.2 頻域信號的增益與衰減 258

15.6.3 均衡器的實現——仿 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 適應度函數 271

16.2.3 選擇算子設計與輪盤賭算法 272

16.2.4 交叉算子設計 273

16.2.5 變異算子設計 274

16.2.6 這就是遺傳算法 275

16.3 總結 276

16.4 參考資料 276

第 17章 計算器程序與大整數計算 277

17.1 哦，溢出了，出洋相的計算器程序 277

17.2 大整數計算的原理 278

17.2.1 大整數加法 279

17.2.2 大整數減法 281

17.2.3 大整數乘法 283

17.2.4 大整數除法與模 284

17.2.5 大整數乘方運算 286

17.3 大整數類的使用 287

17.3.1 與 Windows的計算器程序一決高下 287

17.3.2 最大公約數和最小公倍數 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 素數檢驗與米勒 拉賓算法 296

18.2 RSA算法原理 299

18.2.1 RSA算法的數學理論 300

18.2.2 加密和解密算法 300

18.2.3 RSA 算法的安全性 301

18.3 數據塊分組加密 302

18.3.1 字節流與大整數的轉換 302

18.3.2 PCKS與OAEP加密填充模式 303

18.3.3 數據加密算法實現 305

18.3.4 數據解密算法實現 305

18.4 RSA 簽名與身份驗證 306

18.4.1 RSASSA-PKCS與RSASSA-PSS簽名填充模式 307

18.4.2 簽名算法實現 309

18.4.3 驗證簽名算法實現 309

18.5 總結 310

18.6 參考資料 311

第 19章 數獨游戲 312

19.1 數獨游戲的規則與技巧 312

19.1.1 數獨游戲的規則 312

19.1.2 數獨游戲的常用技巧 313

19.2 電腦求解數獨問題 314

19.2.1 建立問題的數學模型 315

19.2.2 算法實現 316

19.2.3 與傳統窮舉方法的結果對比 318

19.3 關於數獨的趣味話題 318

19.3.1 數獨游戲有多少終盤 318

19.3.2 史上最難的數獨游戲 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 自動求解的算法實現 326

20.3.1 棋局狀態與Zobrist哈希算法 326

20.3.2 重復棋局和左右鏡像的處理 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算法實現 338

21.2.3 Dijkstra算法演示程序 339

21.3 帶啟發的搜索算法——A*算法 341

21.3.1 A*算法原理 342

21.3.2 常用的距離評估函數 343

21.3.3 A*算法實現 346

21.4 總結 348

21.5 參考資料 348

第 22章 俄羅斯方塊游戲 349

22.1 俄羅斯方塊游戲規則 350

22.2 俄羅斯方塊游戲人工智能的算法原理 351

22.2.1 影響評價結果的因素 351

22.2.2 常用的俄羅斯方塊游戲人工智能算法 352

22.2.3 Pierre Dellacherie算法 353

22.3 Pierre Dellacherie算法實現 355

22.3.1 基本數學模型和數據結構定義 356

22.3.2 算法實現 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 估值函數 372

23.1.6 置換表與哈希函數 373

23.1.7 開局庫與終局庫 375

23.2 井字棋——最簡單的博弈游戲 376

23.2.1 棋盤與棋子的數學模型 376

23.2.2 估值函數與估值算法 377

23.2.3 如何產生走法（落子方法） 379

23.3 奧賽羅棋（黑白棋） 380

23.3.1 棋盤與棋子的數學模型 382

23.3.2 估值函數與估值算法 385

23.3.3 搜索算法實現 388

23.3.4 最終結果 392

23.4 五子棋 392

23.4.1 棋盤與棋子的數學模型 394

23.4.2 估值函數與估值算法 395

23.4.3 搜索算法實現 399

23.4.4 最終結果 400

23.5 總結 401

23.6 參考資料 401

第 24章 KNN算法與手寫數字識別 403

24.1 KNN算法原理 403

24.1.1 算法工作原理 404

24.1.2 來個例子，增加點感性認識 405

24.2 手寫數字識別程序設計 406

24.2.1 數字文件的格式 406

24.2.2 樣本和數據集的處理 408

24.2.3 訓練和測試數據 410

24.3 總結 411

24.4 參考資料 411

第 25章 有趣的變聲器 412

25.1 聲調的變化 412

25.2 聲調變化的算法實現 413

25.2.1 回顧DFT 413

25.2.2 改變聲調的原理 414

25.2.3 理解Stephan M. Bernsee算法實現 417

25.3 聲調變化的算法改進 421

25.3.1 支持多聲道音頻數據 421

25.3.2 算法效率改進 422

25.4 參考資料 422