圖書信息
【作者】 王曉華
【ISBN】 978-7-115-38537-6
【日期】 2015-04
圖書簡介
本書從一系列有趣的生活實例出發，全面介紹了構造算法的基礎方法及其廣泛套用，生動地展現了算法的趣味性和實用性。全書分為兩個部分，第一部分介紹了算法的概念、常用的算法結構以及實現方法，第二部分介紹了算法在各個領域的套用，如物理實驗、計算機圖形學、數字音頻處理等。其中，既有各種大名鼎鼎的算法，如神經網路、遺傳算法、離散傅立葉變換算法及各種插值算法，也有不起眼的排序和機率計算算法。講解淺顯易懂而不失深度和嚴謹，對程式設計師有很大的啟發意義。
目錄
第 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
