算法的樂趣

第1章 程序員與算法　　1 1.1 什么是算法　　2 1.2 程序員必須要會算法嗎　　2 1.2.1 一個隊列引發(fā)的慘案　　3 1.2.2 我的第一個算法　　5 1.3 算法的樂趣在哪里　　7 1.4 算法與代碼　　8 1.5 總結　　9 1.6 參考資料　　9 第2章 算法設計的基礎　　10 2.1 程序的基本結構　　10 2.1.1 順序執(zhí)行　　10 2.1.2 循環(huán)結構　　11 2.1.3 分支和跳轉結構　　13 2.2 算法實現(xiàn)與數(shù)據(jù)結構　　16 2.2.1 基本數(shù)據(jù)結構在算法設計中的應用　　16 2.2.2 復雜數(shù)據(jù)結構在算法設計中的應用　　19 2.3 數(shù)據(jù)結構和數(shù)學模型與算法的關系　　24 2.4 總結　　25 2.5 參考資料　　25 第3章 算法設計的常用思想　　26 3.1 貪婪法　　26 3.1.1 貪婪法的基本思想　　27 3.1.2 貪婪法的例子：0-1 背包問題　　27 3.2 分治法　　30 3.2.1 分治法的基本思想　　30 3.2.2 遞歸和分治，一對好朋友　　31 3.2.3 分治法的例子：大整數(shù)Karatsuba 乘法算法　　32 3.3 動態(tài)規(guī)劃　　34 3.3.1 動態(tài)規(guī)劃的基本思想　　34 3.3.2 動態(tài)規(guī)劃法的例子：字符串的編輯距離　　37 3.4 解空間的窮舉搜索　　40 3.4.1 解空間的定義　　41 3.4.2 窮舉解空間的策略　　42 3.4.3 窮舉搜索的例子：Google 方程式　　44 3.5 總結　　46 3.6 參考資料　　46 第4章 阿拉伯數(shù)字與中文數(shù)字　　47 4.1 中文數(shù)字的特點　　47 4.1.1 中文數(shù)字的權位和小節(jié)　　48 4.1.2 中文數(shù)字的零　　48 4.2 阿拉伯數(shù)字轉中文數(shù)字　　49 4.2.1 一個轉換示例　　49 4.2.2 轉換算法設計　　49 4.2.3 算法實現(xiàn)　　50 4.2.4 中文大寫數(shù)字　　51 4.3 中文數(shù)字轉阿拉伯數(shù)字　　52 4.3.1 轉換的基本方法　　52 4.3.2 算法實現(xiàn)　　52 4.4 數(shù)字轉換的測試用例　　54 4.5 總結　　55 4.6 參考資料　　55 第5章 三個水桶等分8 升水的問題　　56 5.1 問題與求解思路　　57 5.2 建立數(shù)學模型　　58 5.2.1 狀態(tài)的數(shù)學模型與狀態(tài)樹　　58 5.2.2 倒水動作的數(shù)學模型　　59 5.3 搜索算法　　60 5.3.1 狀態(tài)樹的遍歷　　60 5.3.2 剪枝和重復狀態(tài)判斷　　61 5.4 算法實現(xiàn)　　62 5.5 總結　　64 5.6 參考資料　　64 第6章 妖怪與和尚過河問題　　65 6.1 問題與求解思路　　66 6.2 建立數(shù)學模型　　66 6.2.1 狀態(tài)的數(shù)學模型與狀態(tài)樹　　67 6.2.2 過河動作的數(shù)學模型　　67 6.3 搜索算法　　69 6.3.1 狀態(tài)樹的遍歷　　70 6.3.2 剪枝和重復狀態(tài)判斷　　70 6.4 算法實現(xiàn)　　71 6.5 總結　　72 6.6 參考資料　　73 第7章 穩(wěn)定匹配與舞伴問題　　 74 7.1 穩(wěn)定匹配問題　　74 7.1.1 什么是穩(wěn)定匹配　　74 7.1.2 Gale-Shapley 算法原理　　75 7.2 Gale-Shapley 算法的應用實例　　77 7.2.1 算法實現(xiàn)　　77 7.2.2 改進優(yōu)化：空間換時間　　80 7.3 有多少穩(wěn)定匹配　　81 7.3.1 窮舉所有的完美匹配　　 81 7.3.2 不穩(wěn)定因素的判斷算法　　 82 7.3.3 窮舉的結果　　 84 7.4 二部圖與二分匹配　　 84 7.4.1 最大匹配與匈牙利算法　　 85 7.4.2 帶權匹配與Kuhn-Munkres算法　　 88 7.5 總結　　 93 7.6 參考資料　　 94 第8章 愛因斯坦的思考題　　 95 8.1 問題的答案　　 96 8.2 分析問題的數(shù)學模型　　 96 8.2.1 基本模型定義　　 96 8.2.2 線索模型定義　　 98 8.3 算法設計　　 99 8.3.1 窮舉所有的組合結果　　 99 8.3.2 利用線索判定結果的正確性　　 101 8.4 總結　　 103 8.5 參考資料　　 104 第9章 項目管理與圖的拓撲排序　　 105 9.1 AOV 網(wǎng)和AOE 網(wǎng)　　 107 9.2 拓撲排序　　 108 9.2.1 拓撲排序的基本過程　　 108 9.2.2 按照活動開始時間排序　　 108 9.3 關鍵路徑算法　　 111 9.3.1 什么是關鍵路徑　　 112 9.3.2 計算關鍵路徑的算法　　 113 9.4 總結　　 116 9.5 參考資料　　 116 第10章 RLE 壓縮算法與PCX 圖像文件格式　　 117 10.1 RLE 壓縮算法　　 117 10.1.1 連續(xù)重復數(shù)據(jù)的處理　　 117 10.1.2 連續(xù)非重復數(shù)據(jù)的處理　　 118 10.1.3 算法實現(xiàn)　　118 10.2 RLE 與PCX 圖像文件格式　　121 10.2.1 PCX 圖像文件格式　　121 10.2.2 PCX_RLE 算法　　122 10.2.3 256 色PCX 文件的解碼和顯示　　123 10.3 總結　　124 10.4 參考資料　　125 第11章 算法與歷法　　126 11.1 格里歷（公歷）生成算法　　126 11.1.1 格里歷的歷法規(guī)則　　126 11.1.2 今天星期幾　　127 11.1.3 生成日歷的算法　　131 11.1.4 日歷變更那點事兒　　132 11.2 二十四節(jié)氣的天文學計算　　134 11.2.1 二十四節(jié)氣的起源　　134 11.2.2 二十四節(jié)氣的天文學定義　　135 11.2.3 VSOP-82/87 行星理論　　137 11.2.4 誤差修正——章動　　141 11.2.5 誤差修正——光行差　　143 11.2.6 用牛頓迭代法計算二十四節(jié)氣　　144 11.3 農歷朔日（新月）的天文學計算　　146 11.3.1 日月合朔的天文學定義　　147 11.3.2 ELP-2000/82 月球理論　　147 11.3.3 誤差修正——地球軌道離心率修正　　149 11.3.4 誤差修正——黃經攝動　　149 11.3.5 月球地心視黃經和最后的修正——地球章動　　150 11.3.6 用牛頓迭代法計算日月合朔　　151 11.4 農歷的生成算法　　152 11.4.1 中國農歷的起源與歷法規(guī)則　　153 11.4.2 中國農歷的推算　　157 11.4.3 一個簡單的“年歷” 　　165 11.5 總結　　166 11.6 參考資料　　167 第12章 實驗數(shù)據(jù)與曲線擬合　　168 12.1 曲線擬合　　168 12.1.1 曲線擬合的定義　　168 12.1.2 簡單線性數(shù)據(jù)擬合的例子　　168 12.2 最小二乘法曲線擬合　　169 12.2.1 最小二乘法原理　　170 12.2.2 高斯消元法求解方程組　　171 12.2.3 最小二乘法解決“速度與加速度”實驗　　172 12.3 三次樣條曲線擬合　　173 12.3.1 插值函數(shù)　　174 12.3.2 樣條函數(shù)的定義　　174 12.3.3 邊界條件　　175 12.3.4 推導三次樣條函數(shù)　　176 12.3.5 追趕法求解方程組　　179 12.3.6 三次樣條曲線擬合算法實現(xiàn)　　181 12.3.7 三次樣條曲線擬合的效果　　183 12.4 總結　　184 12.5 參考資料　　184 第13章 非線性方程與牛頓迭代法　　185 13.1 非線性方程求解的常用方法　　185 13.1.1 公式法　　185 13.1.2 二分逼近法　　186 13.2 牛頓迭代法的數(shù)學原理　　187 13.3 用牛頓迭代法求解非線性方程的實例　　188 13.3.1 導函數(shù)的求解與近似公式　　188 13.3.2 算法實現(xiàn)　　188 13.4 參考資料　　189 第14章 計算幾何與計算機圖形學　　190 14.1 計算幾何的基本算法　　190 14.1.1 點與矩形的關系　　190 14.1.2 點與圓的關系　　191 14.1.3 矢量的基礎知識　　191 14.1.4 點與直線的關系　　194 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 圓生成算法　　207 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 橢圓算法　　215 14.5 多邊形區(qū)域填充算法　　217 14.5.1 種子填充算法　　218 14.5.2 掃描線填充算法　　223 14.5.3 改進的掃描線填充算法　　229 14.5.4 邊界標志填充算法　　233 14.6 總結　　236 14.7 參考資料　　236 第15章 音頻頻譜和均衡器與傅里葉變換算法　　237 15.1 實時頻譜顯示的原理　　237 15.2 離散傅里葉變換　　238 15.2.1 什么是傅里葉變換　　239 15.2.2 傅里葉變換原理　　 239 15.2.3 快速傅里葉變換算法的實現(xiàn)　　 243 15.3 傅里葉變換與音頻播放的實時頻譜顯示　　 245 15.3.1 頻域數(shù)值的特點分析　　 245 15.3.2 從音頻數(shù)據(jù)到功率頻譜　　 246 15.3.3 音頻播放時實時頻譜顯示的例子　　 248 15.4 破解電話號碼的小把戲　　 251 15.4.1 撥號音的頻譜分析　　 251 15.4.2 根據(jù)頻譜數(shù)據(jù)反推電話號碼　　 252 15.5 離散傅里葉逆變換　　 253 15.5.1 快速傅里葉逆變換的推導　　 254 15.5.2 快速傅里葉逆變換的算法實現(xiàn)　　 254 15.6 利用傅里葉變換實現(xiàn)頻域均衡器　　 255 15.6.1 頻域均衡器的實現(xiàn)原理　　 255 15.6.2 頻域信號的增益與衰減　　 256 15.6.3 均衡器的實現(xiàn)——仿Foobar的18 段均衡器　　 258 15.7 總結　　 259 15.8 參考資料　　 259 第16章 全局最優(yōu)解與遺傳算法　　 260 16.1 遺傳算法的原理　　 260 16.1.1 遺傳算法的基本概念　　 261 16.1.2 遺傳算法的處理流程　　 262 16.2 遺傳算法求解0-1 背包問題　　 267 16.2.1 基因編碼和種群初始化　　 267 16.2.2 適應度函數(shù)　　 268 16.2.3 選擇算子設計與輪盤賭算法　　 268 16.2.4 交叉算子設計　　 270 16.2.5 變異算子設計　　 271 16.2.6 這就是遺傳算法　　 272 16.3 總結　　272 16.4 參考資料　　273 第17章 計算器程序與大整數(shù)計算　　274 17.1 哦，溢出了，出洋相的計算器程序　　274 17.2 大整數(shù)計算的原理　　275 17.2.1 大整數(shù)加法　　276 17.2.2 大整數(shù)減法　　278 17.2.3 大整數(shù)乘法　　279 17.2.4 大整數(shù)除法與模　　281 17.2.5 大整數(shù)乘方運算　　282 17.3 大整數(shù)類的使用　　283 17.3.1 與Windows的計算器程序一決高下　　283 17.3.2 最大公約數(shù)和最小公倍數(shù)　　284 17.3.3 用擴展歐幾里得算法求模的逆元　　286 17.4 總結　　288 17.5 參考資料　　288 第18章 RSA 算法——加密與簽名　　289 18.1 RSA 算法的開胃菜　　289 18.1.1 將模冪運算轉化為模乘運算　　290 18.1.2 模乘運算與蒙哥馬利算法　　291 18.1.3 模冪算法　　292 18.1.4 素數(shù)檢驗與米勒—拉賓算法　　292 18.2 RSA 算法原理　　295 18.2.1 RSA 算法的數(shù)學理論　　295 18.2.2 加密和解密算法　　296 18.2.3 RSA 算法的安全性　　297 18.3 數(shù)據(jù)塊分組加密　　297 18.3.1 字節(jié)流與大整數(shù)的轉換　　298 18.3.2 PCKS 與OAEP 加密填充模式　　298 18.3.3 數(shù)據(jù)加密算法實現(xiàn)　　300 18.3.4 數(shù)據(jù)解密算法實現(xiàn)　　301 18.4 RSA 簽名與身份驗證　　302 18.4.1 RSASSA-PKCS 與RSASSAPSS簽名填充模式　　302 18.4.2 簽名算法實現(xiàn)　　304 18.4.3 驗證簽名算法實現(xiàn)　　305 18.5 總結　　305 18.6 參考資料　　306 第19章 數(shù)獨游戲　　307 19.1 數(shù)獨游戲的規(guī)則與技巧　　307 19.1.1 數(shù)獨游戲的規(guī)則　　307 19.1.2 數(shù)獨游戲的常用技巧　　308 19.2 計算機求解數(shù)獨問題　　308 19.2.1 建立問題的數(shù)學模型　　310 19.2.2 算法實現(xiàn)　　311 19.2.3 與傳統(tǒng)窮舉方法的結果對比　　312 19.3 關于數(shù)獨的趣味話題　　312 19.3.1 數(shù)獨游戲有多少終盤　　313 19.3.2 史上最難的數(shù)獨游戲　　314 19.4 總結　　314 19.5 參考資料　　315 第20章 華容道游戲　　316 20.1 華容道游戲介紹　　316 20.2 自動求解的算法原理　　317 20.2.1 定義棋盤的局面　　317 20.2.2 算法思路　　319 20.3 自動求解的算法實現(xiàn)　　320 20.3.1 棋局狀態(tài)與Zobrist 哈希算法　　321 20.3.2 重復棋局和左右鏡像的處理　　323 20.3.3 正確結果的判斷條件　　325 20.3.4 武將棋子的移動　　325 20.3.5 棋局的搜索算法　　328 20.4 總結　　329 20.5 參考資料　　329 第21章 A*尋徑算法　　330 21.1 尋徑算法演示程序　　330 21.2 Dijkstra 算法　　331 21.2.1 Dijkstra 算法原理　　332 21.2.2 Dijkstra 算法實現(xiàn)　　332 21.2.3 Dijkstra 算法演示程序　　333 21.3 帶啟發(fā)的搜索算法——A*算法　　335 21.3.1 A*算法原理　　336 21.3.2 常用的距離評估函數(shù)　　337 21.3.3 A*算法實現(xiàn)　　340 21.4 總結　　342 21.5 參考資料　　342 第22章 俄羅斯方塊游戲　　343 22.1 俄羅斯方塊游戲規(guī)則　　343 22.2 俄羅斯方塊游戲人工智能的算法原理　　344 22.2.1 影響評價結果的因素　　345 22.2.2 常用的俄羅斯方塊游戲人工智能算法　　346 22.2.3 Pierre Dellacherie 評估算法　　347 22.3 Pierre Dellacherie 算法實現(xiàn)　　349 22.3.1 基本數(shù)學模型和數(shù)據(jù)結構定義　　350 22.3.2 算法實現(xiàn)　　352 22.4 總結　　358 22.5 參考資料　　358 第23章 博弈樹與棋類游戲　　359 23.1 棋類游戲的AI　　359 23.1.1 博弈與博弈樹　　360 23.1.2 極大極小值搜索算法　　361 23.1.3 負極大極搜索算法　　 362 23.1.4 “α-β”剪枝算法　　 363 23.1.5 估值函數(shù)　　 365 23.1.6 置換表與哈希函數(shù)　　 366 23.1.7 開局庫與終局庫　　 368 23.2 井字棋——最簡單的博弈游戲　　 368 23.2.1 棋盤與棋子的數(shù)學模型　　 369 23.2.2 估值函數(shù)與估值算法　　 370 23.2.3 如何產生走法（落子方法）　　 371 23.3 奧賽羅棋（黑白棋） 　　 373 23.3.1 棋盤與棋子的數(shù)學模型　　 374 23.3.2 估值函數(shù)與估值算法　　 377 23.3.3 搜索算法實現(xiàn)　　 380 23.3.4 最終結果　　 384 23.4 五子棋　　 385 23.4.1 棋盤與棋子的數(shù)學模型　　 386 23.4.2 估值函數(shù)與估值算法　　 388 23.4.3 搜索算法實現(xiàn)　　 391 23.4.4 最終結果　　 393 23.5 總結　　 393 23.6 參考資料　　 393   附錄A 算法設計的常用技巧　　 395 A.1 數(shù)組下標處理　　 395 A.2 一重循環(huán)實現(xiàn)兩重循環(huán)的功能　　 396 A.3 棋盤（迷宮）類算法方向遍歷　　 396 A.4 代碼的一致性處理技巧　　 397 A.5 鏈表和數(shù)組的配合使用　　 398 A.6 “以空間換時間”的常用技巧　　 399 A.7 利用表驅動避免長長的switch-case 　　 400 附錄B 一個棋類游戲的設計框架　　 401 B.1 代碼框架的整體結構　　 401 B.2 代碼框架的使用方法　　 403