簡 介

中文名: 算法的樂趣
作者: 王曉華
圖書分類: 軟件
資源格式: EPUB
版本: 文字版
出版社: 人民郵電出版社
書號: 9787115385376
發行時間: 2015年4月
地區: 大陸
語言: 簡體中文
簡介:

網盤 【算法的樂趣】
網盤 【算法的樂趣】
網盤 【算法的樂趣】
內容簡介
算法之大，大到可以囊括宇宙萬物的運行規律；算法之小，小到寥寥數行代碼即可展現一個神奇的功能。算法的應用和樂趣在生活中無處不在：
歷法和二十四節氣計算使用的是霍納法則和求解一元高次方程的牛頓迭代法；
音頻播放器跳動的實時頻譜背後是離散傅立葉變換算法；
DOS時代著名的PCX圖像文件格式使用的是簡單有效的RLE壓縮算法；
RSA加密算法的光環之下是樸實的歐幾裡德算法、蒙哥馬利算法和米勒-拉賓算法；
井字棋、黑白棋、五子棋和俄羅斯方塊游戲背後是各種有趣的AI算法；
華容道游戲求解的簡單窮舉算法中還蘊藏著對棋盤狀態的哈希算法；
遺傳算法神秘不可測，但用遺傳算法求解0-1背包問題只用了60多行代碼……
一本書帶你走進色彩缤紛的算法世界，讓你盡享算法的樂趣。
.

作者簡介
王曉華
2005年畢業於華中科技大學，目前在中興通訊上海研發中心從事光纖接入網通訊設備開發，擔任EPON（以太網無源光網絡）業務軟件開發經理，參與開發的PON設備在全球部署過億線，為數億家庭提供寬帶接入服務。
業余時間喜歡研究算法和寫作博客（http://blog.csdn.net/orbit），最大的樂趣就是用程序解決生活中的問題：
為了方便使用Visual Studio 6.0開發軟件，曾特意編寫並開源了一個tabbar插件；
為了文檔安全，開發了一個基於layerFSD技術的透明文件加密系統；
使用Source Insight軟件覺得不習慣，於是以外掛的形式開發了TabSiPlus插件……
算法可以做的事情還有很多，期待我們會有更多發現！

目錄:
第1章 程序員與算法 1
1.1 什麼是算法 2
1.2 程序員必須要會算法嗎 2
1.2.1 一個隊列引發的慘案 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 順序執行 10
2.1.2 循環結構 11
2.1.3 分支和跳轉結構 13
2.2 算法實現與數據結構 16
2.2.1 基本數據結構在算法設計中的應用 16
2.2.2 復雜數據結構在算法設計中的應用 19
2.3 數據結構和數學模型與算法的關系 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 分治法的例子：大整數Karatsuba 乘法算法 32
3.3 動態規劃 34
3.3.1 動態規劃的基本思想 34
3.3.2 動態規劃法的例子：字符串的編輯距離 37
3.4 解空間的窮舉搜索 40
3.4.1 解空間的定義 41
3.4.2 窮舉解空間的策略 42
3.4.3 窮舉搜索的例子：Google 方程式 44
3.5 總結 46
3.6 參考資料 46
第4章 阿拉伯數字與中文數字 47
4.1 中文數字的特點 47
4.1.1 中文數字的權位和小節 48
4.1.2 中文數字的零 48
4.2 阿拉伯數字轉中文數字 49
4.2.1 一個轉換示例 49
4.2.2 轉換算法設計 49
4.2.3 算法實現 50
4.2.4 中文大寫數字 51
4.3 中文數字轉阿拉伯數字 52
4.3.1 轉換的基本方法 52
4.3.2 算法實現 52
4.4 數字轉換的測試用例 54
4.5 總結 55
4.6 參考資料 55
第5章 三個水桶等分8 升水的問題 56
5.1 問題與求解思路 57
5.2 建立數學模型 58
5.2.1 狀態的數學模型與狀態樹 58
5.2.2 倒水動作的數學模型 59
5.3 搜索算法 60
5.3.1 狀態樹的遍歷 60
5.3.2 剪枝和重復狀態判斷 61
5.4 算法實現 62
5.5 總結 64
5.6 參考資料 64
第6章 妖怪與和尚過河問題 65
6.1 問題與求解思路 66
6.2 建立數學模型 66
6.2.1 狀態的數學模型與狀態樹 67
6.2.2 過河動作的數學模型 67
6.3 搜索算法 69
6.3.1 狀態樹的遍歷 70
6.3.2 剪枝和重復狀態判斷 70
6.4 算法實現 71
6.5 總結 72
6.6 參考資料 73
第7章 穩定匹配與舞伴問題 74
7.1 穩定匹配問題 74
7.1.1 什麼是穩定匹配 74
7.1.2 Gale-Shapley 算法原理 75
7.2 Gale-Shapley 算法的應用實例 77
7.2.1 算法實現 77
7.2.2 改進優化：空間換時間 80
7.3 有多少穩定匹配 81
7.3.1 窮舉所有的完美匹配 81
7.3.2 不穩定因素的判斷算法 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 分析問題的數學模型 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 網和AOE 網 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 連續重復數據的處理 117
10.1.2 連續非重復數據的處理 118
10.1.3 算法實現 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 格裡歷的歷法規則 126
11.1.2 今天星期幾 127
11.1.3 生成日歷的算法 131
11.1.4 日歷變更那點事兒 132
11.2 二十四節氣的天文學計算 134
11.2.1 二十四節氣的起源 134
11.2.2 二十四節氣的天文學定義 135
11.2.3 VSOP-82/87 行星理論 137
11.2.4 誤差修正——章動 141
11.2.5 誤差修正——光行差 143
11.2.6 用牛頓迭代法計算二十四節氣 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 中國農歷的起源與歷法規則 153
11.4.2 中國農歷的推算 157
11.4.3 一個簡單的“年歷” 165
11.5 總結 166
11.6 參考資料 167
第12章 實驗數據與曲線擬合 168
12.1 曲線擬合 168
12.1.1 曲線擬合的定義 168
12.1.2 簡單線性數據擬合的例子 168
12.2 最小二乘法曲線擬合 169
12.2.1 最小二乘法原理 170
12.2.2 高斯消元法求解方程組 171
12.2.3 最小二乘法解決“速度與加速度”實驗 172
12.3 三次樣條曲線擬合 173
12.3.1 插值函數 174
12.3.2 樣條函數的定義 174
12.3.3 邊界條件 175
12.3.4 推導三次樣條函數 176
12.3.5 追趕法求解方程組 179
12.3.6 三次樣條曲線擬合算法實現 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 牛頓迭代法的數學原理 187
13.3 用牛頓迭代法求解非線性方程的實例 188
13.3.1 導函數的求解與近似公式 188
13.3.2 算法實現 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 數值微分法 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 多邊形區域填充算法 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 快速傅裡葉變換算法的實現 243
15.3 傅裡葉變換與音頻播放的實時頻譜顯示 245
15.3.1 頻域數值的特點分析 245
15.3.2 從音頻數據到功率頻譜 246
15.3.3 音頻播放時實時頻譜顯示的例子 248
15.4 破解電話號碼的小把戲 251
15.4.1 撥號音的頻譜分析 251
15.4.2 根據頻譜數據反推電話號碼 252
15.5 離散傅裡葉逆變換 253
15.5.1 快速傅裡葉逆變換的推導 254
15.5.2 快速傅裡葉逆變換的算法實現 254
15.6 利用傅裡葉變換實現頻域均衡器 255
15.6.1 頻域均衡器的實現原理 255
15.6.2 頻域信號的增益與衰減 256
15.6.3 均衡器的實現——仿Foobar的18 段均衡器 258
15.7 總結 259
15.8 參考資料 259
第16章 全局最優解與遺傳算法 260
16.1 遺傳算法的原理 260
16.1.1 遺傳算法的基本概念 261
16.1.2 遺傳算法的處理流程 262
16.2 遺傳算法求解0-1 背包問題 267
16.2.1 基因編碼和種群初始化 267
16.2.2 適應度函數 268
16.2.3 選擇算子設計與輪盤賭算法 268
16.2.4 交叉算子設計 270
16.2.5 變異算子設計 271
16.2.6 這就是遺傳算法 272
16.3 總結 272
16.4 參考資料 273
第17章 計算器程序與大整數計算 274
17.1 哦，溢出了，出洋相的計算器程序 274
17.2 大整數計算的原理 275
17.2.1 大整數加法 276
17.2.2 大整數減法 278
17.2.3 大整數乘法 279
17.2.4 大整數除法與模 281
17.2.5 大整數乘方運算 282
17.3 大整數類的使用 283
17.3.1 與Windows的計算器程序一決高下 283
17.3.2 最大公約數和最小公倍數 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 素數檢驗與米勒—拉賓算法 292
18.2 RSA 算法原理 295
18.2.1 RSA 算法的數學理論 295
18.2.2 加密和解密算法 296
18.2.3 RSA 算法的安全性 297
18.3 數據塊分組加密 297
18.3.1 字節流與大整數的轉換 298
18.3.2 PCKS 與OAEP 加密填充模式 298
18.3.3 數據加密算法實現 300
18.3.4 數據解密算法實現 301
18.4 RSA 簽名與身份驗證 302
18.4.1 RSASSA-PKCS 與RSASSAPSS簽名填充模式 302
18.4.2 簽名算法實現 304
18.4.3 驗證簽名算法實現 305
18.5 總結 305
18.6 參考資料 306
第19章 數獨游戲 307
19.1 數獨游戲的規則與技巧 307
19.1.1 數獨游戲的規則 307
19.1.2 數獨游戲的常用技巧 308
19.2 計算機求解數獨問題 308
19.2.1 建立問題的數學模型 310
19.2.2 算法實現 311
19.2.3 與傳統窮舉方法的結果對比 312
19.3 關於數獨的趣味話題 312
19.3.1 數獨游戲有多少終盤 313
19.3.2 史上最難的數獨游戲 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 自動求解的算法實現 320
20.3.1 棋局狀態與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 算法實現 332
21.2.3 Dijkstra 算法演示程序 333
21.3 帶啟發的搜索算法——A*算法 335
21.3.1 A*算法原理 336
21.3.2 常用的距離評估函數 337
21.3.3 A*算法實現 340
21.4 總結 342
21.5 參考資料 342
第22章 俄羅斯方塊游戲 343
22.1 俄羅斯方塊游戲規則 343
22.2 俄羅斯方塊游戲人工智能的算法原理 344
22.2.1 影響評價結果的因素 345
22.2.2 常用的俄羅斯方塊游戲人工智能算法 346
22.2.3 Pierre Dellacherie 評估算法 347
22.3 Pierre Dellacherie 算法實現 349
22.3.1 基本數學模型和數據結構定義 350
22.3.2 算法實現 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 估值函數 365
23.1.6 置換表與哈希函數 366
23.1.7 開局庫與終局庫 368
23.2 井字棋——最簡單的博弈游戲 368
23.2.1 棋盤與棋子的數學模型 369
23.2.2 估值函數與估值算法 370
23.2.3 如何產生走法(落子方法) 371
23.3 奧賽羅棋(黑白棋) 373
23.3.1 棋盤與棋子的數學模型 374
23.3.2 估值函數與估值算法 377
23.3.3 搜索算法實現 380
23.3.4 最終結果 384
23.4 五子棋 385
23.4.1 棋盤與棋子的數學模型 386
23.4.2 估值函數與估值算法 388
23.4.3 搜索算法實現 391
23.4.4 最終結果 393
23.5 總結 393
23.6 參考資料 393
附錄A 算法設計的常用技巧 395
A.1 數組下標處理 395
A.2 一重循環實現兩重循環的功能 396
A.3 棋盤(迷宮)類算法方向遍歷 396
A.4 代碼的一致性處理技巧 397
A.5 鏈表和數組的配合使用 398
A.6 “以空間換時間”的常用技巧 399
A.7 利用表驅動避免長長的switch-case 400
附錄B 一個棋類游戲的設計框架 401
B.1 代碼框架的整體結構 401
B.2 代碼框架的使用方法 403
.