《算法——數學套用與競賽案例解析》是2023年6月1日清華大學出版社出版的圖書，作者：俞經善、李一鳴、馮月春、謝濤、徐曉君、王慶月。
基本介紹
- 中文名：算法——數學套用與競賽案例解析
- 作者：俞經善、李一鳴、馮月春、謝濤、徐曉君、王慶月
- 出版時間：2023年6月1日
- 出版社：清華大學出版社
- ISBN：9787302628828
- 定價：99 元
- 印次：1-1
- 印刷日期：2023.06.07
內容簡介,圖書目錄,
內容簡介
本書共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
