算法 — 數學應用與競賽案例解析

本書共13章，依次講述程序設計基礎、算法基礎、排序、查找、搜索、字符串匹配、圖論、動態規劃、高級數據結構、數論、組合數學、計算幾何基礎、博弈論。 書中提供了大量習題和答案供讀者學習使用。 本書可作為高等學校電腦相關專業算法設計類課程的教材，也可供對算法設計、程序設計競賽感興趣的讀者自學使用。

目錄

 

 

第1章程序設計基礎1

1.1程序設計語言入門1

1.1.1基本數據類型2

1.1.2順序結構程序設計2

1.1.3條件結構程序設計3

1.1.4循環結構7

1.1.5數組12

1.1.6函數18

1.1.7指針20

1.1.8結構體22

1.2數據結構入門（基礎）27

1.2.1棧28

1.2.2隊列29

1.2.3鏈隊30

第2章算法基礎33

2.1遞歸算法33

2.1.1遞歸算法概述33

2.1.2漢諾塔問題33

2.1.3n皇後問題35

2.2分治算法37

2.2.1分治算法概述37

2.2.2計數問題38

2.2.3歸並排序40

2.3枚舉41

2.3.1木棒三角形42

2.3.2四大湖問題43

2.4貪心44

2.4.1砝碼稱重44

2.4.2石頭剪刀布45

2.4.3馬馳愛釣魚48

2.5模擬50

2.5.1猜數50

2.5.2敵兵布陣52

第3章排序55

3.1冒泡排序57

3.1.1冒泡排序的基本原理57

3.1.2冒泡排序的算法步驟57

3.1.3冒泡排序的基本算法實現57

3.1.4冒泡排序的優化58

3.2快速排序59

3.2.1快速排序的基本原理59

3.2.2快速排序算法的步驟59

3.2.3快速排序的基本算法實現59

3.3其他排序60

3.4實例演示60

3.4.1出現次數超過一半的數60

3.4.2獎學金發放62

3.4.3魔法照片63

3.4.4輸出前k大的數65

3.4.5不重復地輸出數66

3.4.6單詞排序67

3.4.7快速排序68

3.4.8第k個數70

第4章查找72

4.1查找的概念72

4.2順序查找算法72

4.2.1順序查找算法的概念72

4.2.2順序查找算法的步驟72

4.2.3順序查找算法的實現73

4.3折半查找算法73

4.3.1折半查找算法的基本思想73

4.3.2折半查找算法的步驟73

4.3.3折半查找算法的實現73

4.4實例演示74

4.4.1丟瓶蓋74

4.4.2查找最接近的元素75

4.4.3油田合並77

第5章搜索79

5.1基本搜索算法79

5.1.1遞歸與迭代79

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

5.1.3回溯84

5.2搜索算法的一些優化85

5.2.1剪枝函數85

5.2.2雙向廣度搜索85

5.3實例演示85

5.3.1寶石游戲85

5.3.2騎士移動89

5.3.3Tetravex游戲93

5.3.4集合分解96

第6章字符串匹配99

6.1BF算法99

6.2RK算法99

6.3KMP算法100

6.4BM算法102

6.5Sunday算法103

6.6實例演示104

6.6.1最低三元字符串104

6.6.2從左側刪除107

6.6.3字母刪除109

6.6.4潛伏者111

6.6.5處女座與復讀機113

6.6.6縮寫117

第7章圖論119

7.1最短路徑介紹119

7.2最小生成樹121

7.2.1Kruskal算法121

7.2.2Prim算法122

7.3樹的直徑與最近公共祖先123

7.3.1樹的直徑123

7.3.2最近公共祖先123

7.4基環樹125

7.4.1定義125

7.4.2一般的題型125

7.4.3一般解題思路125

7.5Tarjan算法與無向圖和有向圖連通性125

7.5.1Tarjan算法與無向圖連通性125

7.5.2Tarjan算法與有向圖連通性126

7.6二分圖127

7.6.1定義127

7.6.2辨別二分圖127

7.6.3充要條件128

7.6.4二分圖最大匹配129

7.6.5判別129

7.7實例演示130

7.7.1黑與白130

7.7.2迷宮132

7.7.3最短網絡133

7.7.4暢通工程135

7.7.5城市公交137

7.7.6趣味象棋140

第8章動態規劃143

8.1基本思想145

8.2基本概念145

8.3基本原理146

8.3.1最優化原理146

8.3.2無後效性146

8.4一般步驟146

8.5實例演示147

8.5.1數字三角形147

8.5.2括號匹配150

8.5.3背包問題151

8.5.4骨灰級玩家考證篇154

8.5.5猴子游戲157

第9章高級數據結構159

9.1三種常用高級數據結構159

9.1.1線段樹159

9.1.2並查集162

9.1.3樹狀數組167

9.2紅黑樹172

9.2.1紅黑樹的調整策略173

9.2.2參考程序179

9.3實例演示183

9.3.1人工湖公路183

9.3.2宗教信仰問題186

9.3.3無線網絡188

第10章數論192

10.1質數查找192

10.2快速乘方194

10.3最大公約數196

10.4最小公倍數196

10.5模冪運算197

10.6斐波那契數列198

10.6.1斐波那契數列(遞歸實現)199

10.6.2斐波那契數列2(遞推實現)200

10.6.3爬樓梯201

10.6.4一隻小蜜蜂202

10.6.5骨牌鋪方格203

10.7歐拉函數205

10.7.1概念205

10.7.2性質205

10.7.3實現方法205

10.8實例演示207

10.8.1歐拉函數例題207

10.8.2阿裡巴巴的寶藏208

第11章組合數學211

11.1基本計數定理211

11.1.1加法原理與乘法原理211

11.1.2抽屜原理（鴿巢原理）214

11.2容斥原理219

11.2.1原理概述219

11.2.2常見應用219

11.2.3矩形並的面積222

11.2.42月29日223

11.2.5跳蚤226

11.2.6幫助蟬228

11.2.7你能找到多少個整數231

11.3排列233

11.3.1可重復排列233

11.3.2不可重復排列233

11.3.3不全相異元素的選排列235

11.3.4不全相異元素的全排列235

11.3.5錯位排列235

11.3.6圓排列235

11.3.7卡片排列236

11.3.8瘋狂外星人238

11.3.9重排列得到2的冪239

11.3.10permutation（排列）241

11.4組合244

11.4.1不可重組合數244

11.4.2可重復組合數244

11.4.3不相鄰組合數244

11.4.4組合數的常用公式245

11.4.5求組合數的方法245

11.4.6車248

11.4.7壁畫250

11.4.8二項式252

11.4.9集合的劃分254

11.5組合數取模255

11.5.1遞推打表255

11.5.2盧卡斯定理255

11.5.3盧卡斯定理擴展256

11.5.4孤獨的李雷259

11.5.5走格子的騎士261

11.5.6組合問題262

11.5.7問題製造者264

11.5.8抽獎游戲267

11.6卡特蘭數列269

11.6.1卡特蘭數的公式269

11.6.2卡特蘭數的應用270

11.6.3卡特蘭數的實現270

11.6.4小濤叔叔的禮物271

11.6.5號碼連接游戲272

11.6.6李嵩的作業274

11.7斯特林數277

11.7.1第一類斯特林數277

11.7.2第二類斯特林數278

11.7.3二進制斯特林數280

11.8母函數282

11.8.1方形硬幣（母函數）282

11.8.2尋找拉希德284

11.8.3排列組合286

第12章計算幾何基礎289

12.1矢量289

12.1.1矢量的概念289

12.1.2矢量加減法289

12.1.3矢量叉積289

12.1.4矢量叉積的應用290

12.2包含關系291

12.2.1判斷圖形是否包含在矩形中291

12.2.2判斷圖形是否包含在多邊形中291

12.2.3判斷圖形是否包含在圓中294

12.2.4飛行員294

12.3凸包299

12.3.1凸包的概念299

12.3.2凸包的求法299

12.3.3捕野豬301

第13章博弈論304

13.1博弈論的基本構成要素304

13.1.1零和博弈304

13.1.2嚴格優勢策略305

13.1.3囚徒困境305

13.1.4智豬博弈305

13.1.5納什均衡306

13.2最小最大問題306

13.3尼姆博弈307

13.4巴什博弈310

13.5斐波那契博弈311

參考文獻313