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