算法的樂趣

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