目錄

第1章基礎算法1

1.1分治算法1

1.2遞歸算法8

1.3枚舉算法14

1.4貪心算法20第2章排序、查找算法29

2.1基本排序算法29

2.1.1插入排序29

2.1.2冒泡排序29

2.1.3快速排序30

2.1.4其他排序30

2.2基本查找算法31

2.2.1順序查找31

2.2.2折半查找31

2.3實例分析32

2.4小結57第3章數據結構基礎58

3.1常用數據結構簡介58

3.1.1線段樹簡介58

3.1.2並查集簡介58

3.1.3樹狀數組簡介58

3.2實例分析59第4章字符串80

4.1字符串匹配80

4.1.1樸素的字符串匹配算法80

4.1.2KMP算法81

4.1.3其他匹配算法81

4.2實例分析81

4.3小結97第5章搜索算法98

5.1基本搜索算法98

5.1.1遞歸與迭代98

5.1.2深度優先搜索與廣度優先搜索98

5.1.3回溯98

5.2搜索算法的一些優化99

5.2.1剪枝函數99

5.2.2雙向廣度搜索99

5.3實例分析99

5.4小結121第6章圖論算法122

6.1短路徑122

6.1.1Dijkstra算法122

6.1.2Floyd算法123

6.1.3BellmanFord算法123

6.2小生成樹124

6.2.1Kruskal算法125

6.2.2Prim算法126

6.3匹配——匈牙利算法127

6.4權匹配問題128

6.4.1理論基礎128

6.4.2基本思想129

6.4.3樣例代碼129

6.5割點、割邊以及連通分量131

6.5.1理論基礎131

6.5.2求割點132

6.5.3求強連通分量133

6.6網絡流135

6.6.1理論基礎135

6.6.2流問題135

6.6.3小費用流問題137

6.7實例分析138

6.8小結166第7章動態規劃算法167

7.1基本思想169

7.2基本概念169

7.3基本原理170

7.3.1化原理170

7.3.2無後效性170

7.4基本步驟170

7.5經典例子171

7.6實例分析175

7.7小結200第8章計算幾何基礎201

8.1矢量201

8.1.1矢量的概念201

8.1.2矢量加減法201

8.1.3矢量叉積201

8.1.4矢量叉積的應用201

8.2包含關繫203

8.2.1判斷圖形是否包含在矩形中203

8.2.2判斷圖形是否包含在多邊形中203

8.2.3判斷圖形是否包含在圓中 206

8.3凸包206

8.3.1凸包的概念206

8.3.2凸包的求法206

8.4實例分析208第9章數論233

9.1基本數學算法233

9.1.1素數篩選233

9.1.2公約數233

9.1.3快速乘方234

9.2實例分析234附錄A綜合訓練題264

A.1Lucky Bird264

A.2Josephus’Problem265

A.3Counter Strike267

A.4Gauss Elimination270

A.5The Math Problem271

A.6Mobile Phones272

A.7Japan275

A.8骨灰級玩家考證篇277

A.9括號匹配280

A.10食物鏈282