本書針對ACM程式競賽出現比較多的16個方面的問題，通過案例的方式說明解決問題的方法。由於數據結構使用非常多，對不屬於16個專門問題的知識我們也進行了介紹。 本書不是這些專門問題的教科書，所以對這些問題所涉及知識的介紹不多，主要是分析一個案例，介紹專屬於ACM程式設計的方法和技巧。
基本介紹
- 書名：ACM程式設計培訓教程
- 作者：吳昊
- ISBN：9787113076511
- 頁數：269
基本信息,圖書目錄,
基本信息
作者: 吳昊
ISBN: 9787113076511
頁數: 269
定價: 28.00
出版社: 中國鐵道
裝幀: 平裝
出版年: 2007年8月1日
圖書目錄
第1章 經典數據結構與算法……………………………………………………………1
1.1 線性表………………………………………………………………………………1
1.1.1 線性表的順序存儲結構……………………………………………………1
1.1.2 插入操作……………………………………………………………………2
1.1.3 刪除操作……………………………………………………………………2
1.1.4 線性表的鏈式存儲…………………………………………………………2
1.1.5 單鍊表………………………………………………………………………2
1.1.6 單鍊表的插入操作…………………………………………………………3
1.1.7 單鍊表的刪除操作…………………………………………………………3
1.1.8 循環鍊表……………………………………………………………………4
1.1.9 雙向鍊表……………………………………………………………………5
1.1.10 雙向鍊表的插入操作………………………………………………………5
1.1.11 雙向鍊表的刪除操作………………………………………………………5
1.1.12 靜態鍊表……………………………………………………………………5
1.2 棧………………………………………………………………………………………………5
1.2.1 順序棧……………………………………一…………………………………6
1.2.2 鏈棧……………………………………………………………………………………………………9
l.3 佇列…………………………………………………………………………………………10
1.3.1 鏈佇列………………………………………………………………………10
1.3.2 循環佇列……………………………………………………………………12
1.4 串的定義……………………………………………………………………………13
1.5 抽象數據類型串的實現……………………………………………………………14
1.5.1 定長順序串…………………………………………………………………14
1.5.2 堆串………………………………………………………………………………18
1.5.3 塊鏈串………………………………………………………………………24
1.6 查找的基本概念……………………………………………………………………24
1.6.1 順序查找法…………………………………………………………………25
1.6.2 折半查找法…………………………………………………………………26
1.6.3 分塊查找法…………………………………………………………………27
1.6.4 基於樹的查找法……………………………………………………………28
1.6.5 計算式查找法——哈希法…………………………………………………28
1.7 排序的基本概念……………………………………………………………………33
1.7.1 插入類排序…………………………………………………………………34
1.7.2 直接插入排序………………………………………………………………34
1.7.3 折半插入排序………………………………………………………………35
1.7.4 表插入排序…………………………………………………………………36
1.7.5 冒泡排序……………………………………………………………………39
1.7.6 快速排序……………………………………………………………………40
1.8 分配類排序…………………………………………………………………………41
1.8.1 多關鍵字排序………………………………………………………………42
1.8.2 鏈式基數排序………………………………………………………………42
1.8.3 基數排序的順序表結構……………………………………………………45
1.8.4 各種排序方法的綜合比較…………………………………………………46
第2章 蠻力法………………………………………………………………………47
2.1搜尋所有的解空間…………………………………………………………………47
〖案例l〗假金幣…………………………………………………………………47
〖案例2〗現在的時間是多少……………………………………………………49
2.2 搜尋所有的路徑……………………………………………………………………52
〖案例3〗矩陣……………………………………………………………………52
2.3 直接計算……………………………………………………………………………54
〖案例4〗數的長度………………………………………………………………54
2.4 模擬與仿真…………………………………………………………………………56
〖案例5〗衝撞的機器人…………………………………………………………56
第3章 貪心算法………………………………………………………………………61
3.1 構造法………………………………………………………………………………61
〖案例1〗訂票……………………………………………………………………6I
3.2 反證法………………………………………………………………………………67
〖案例2〗電梯……………………………………………………………………68
3.3 調整法………………………………………………………………………………70
〖案例3〗水位……………………………………………………………………70
〖案例4〗埃及分數………………………………………………………………73
〖案例5〗數劃分的研究…………………………………………………………74
第4章 背包問題………………………………………………………………………78
4.1 用貪心法解決背包問題……………………………………………………………78
〖案例1〗最佳裝載………………………………………………………………78
4.2 回溯法解決背包問題………………………………………………………………81
〖案例2〗0/1背包…………………………………………………………………81
4.3 遺傳算法解決背包問題……………………………………………………………86
〖案例3〗0/1背包……………………………………………………………86
4.4 動態規劃解決背包問題……………………………………………………………94
〖案例4〗適配背包………………………………………………………………94
第5章回溯法………………………………………………………………………97
5.1 組合與數的問題……………………………………………………………………97
〖案例l〗組合問題………………………………………………………………97
〖案例2〗數的劃分………………………………………………………………99
5.2 回溯法與搜尋……………………………………………………………………101
〖案例3〗素數填表問題…………………………………………………………101
〖案例4〗八皇后問題……………………………………………………………105
第6章 動態規劃……………………………………………………………………109
6.1 最優子結構………………………………………………………………………1 1 1
〖案例1〗攔截飛彈………………………………………………………………1ll
6.2 套用動態規劃的步驟……………………………………………………………113
〖案例2〗公共子序列……………………………………………………………113
〖案例3〗Uxuhul的表決…………………………………………………………115
第7章 DFS與BFS以及剪枝問題……………………………………………………119
7.1 深度優先遍歷……………………………………………………………………119
〖案例l〗15數碼難題……………………………………………………………120
〖案例2〗三角形大戰……………………………………………………………121
7.2 寬度優先遍歷……………………………………………………………………122
〖案例3〗蛇和梯子………………………………………………………………123
7.3 剪枝方法…………………………………………………………………………127
第8章 線性規劃和整數規劃…………………………………………………………129
8.1 簡單線性規劃……………………………………………………………………129
〖案例l〗鍊金術…………………………………………………………………129
8.2 整數規劃…………………………………………………………………………134
〖案例2〗裝箱問題………………………………………………………………134
第9章 最小生成樹…………………………………………………………………139
9.1 Prim算法…………………………………………………………………………………………………140
9.2 Kruskal算法………………………………………………………………………………………………143
9.3 Sollin算法…………………………………………………………………………………………………145
第10章 大數問題……………………………………………………………………146
10.1 大數的加減………………………………………………………………………146
〖案例1〗整數探究………………………………………………………………146
10.2 大數的乘積……………………………………………………………………148
〖案例2〗相連遊戲………………………………………………………………148
〖案例3〗公牛的數學……………………………………………………………150
10.3 用FFT作大數乘法………………………………………………………………151
〖案例4〗X問題…………………………………………………………………152
10.4 任意精度計算……………………………………………………………………155
〖案例5〗冪……………………………………………………………………155
10.5 大數的除法………………………………………………………………………157
第11章 計算幾何學…………………………………………………………………158
11.1 判斷點是否在多邊形中…………………………………………………………158
11.2 判斷線段是否在多邊形內………………………………………………………159
11.3 計算幾何典型算法………………………………………………………………160
〖案例1〗計算周長問題…………………………………………………………161
〖案例2〗正方形問題……………………………………………………………162
〖案例3〗計算平麵點集凸殼的算法……………………………………………163
第12章 著色問題與排隊論……………………………………………………………167
12.1 著色問題…………………………………………………………………………168
12.1.1 頂點著色問題……………………………………………………………168
12.1.2 邊著色問題………………………………………………………………177
12.2 排隊論……………………………………………………………………………………………………179
第13章 組合數學……………………………………………………………………188
13.1 鴿巢原理…………………………………………………………………………188
13.2 容斥原理…………………………………………………………………………190
〖案例1〗棋盤覆蓋問題…………………………………………………………192
〖案例2〗被毀壞的玉米地(Crop Circles)問題………………………………193
13.3 遞推關係…………………………………………………………………………197
〖案例3〗Josephus問題…………………………………………………………197
〖案例4〗假幣問題………………………………………………………………199
13.4 發生函式…………………………………………………………………………202
13.5 Polya定理………………………………………………………………………………………………204
第14章 機率論…………………………………………………………………………206
14.1 基本概念…………………………………………………………………………206
14.2 基本機率算法……………………………………………………………………208
〖案例1〗快速排序………………………………………………………………209
〖案例2〗八皇后問題……………………………………………………………210
14.3 蒙特卡羅(Monte Carlo)型機率算法…………………………………………214
第15章 凸包問題……………………………………………………………………217
15.1 窮舉法解決凸包問題……………………………………………………………217
15.2 格雷厄姆掃描法解決凸包問題…………………………………………………218
15.3 分治法解決凸包問題……………………………………………………………220
15.4 蠻力法解決凸包問題……………………………………………………………222
15.5 Jarris步進法解決凸包問題………………………………………………………224
15.6 套用…………………………………………………………………………………………………………227
〖案例l〗果園籬笆………………………………………………………………227
〖案例2〗巨人和鬼………………………………………………………………232
第16章 數論問題……………………………………………………………………236
16.1 數的冪運算………………………………………………………………………236
〖案例l〗高級模運算……………………………………………………………236
16.2 歐拉定理的套用…………………………………………………………………238
〖案例2〗快樂2004……………………………………………………………239
〖案例3〗2x mod n=1……………………………………………………………240
16.3 素數測試…………………………………………………………………………243
〖案例4〗素數距離………………………………………………………………243
〖案例5〗素數測試………………………………………………………………246
16.4 Pell方程…………………………………………………………………………………………………250
〖案例6〗Smith問題……………………………………………………………250
附錄A 排課時間表問題原始碼………………………………………………………258
參考文獻………………………………………………………………………………269
