算法：數(shù)學應用與競賽案例解析

第1章程序設計基礎1
1.1程序設計語言入門1
1.1.1基本數(shù)據(jù)類型2
1.1.2順序結構程序設計2
1.1.3條件結構程序設計3
1.1.4循環(huán)結構7
1.1.5數(shù)組12
1.1.6函數(shù)18
1.1.7指針20
1.1.8結構體22
1.2數(shù)據(jù)結構入門（基礎）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計數(shù)問題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猜數(shù)50
2.5.2敵兵布陣52
第3章排序55
3.1冒泡排序57
3.1.1冒泡排序的基本原理57
3.1.2冒泡排序的算法步驟57
3.1.3冒泡排序的基本算法實現(xiàn)57
3.1.4冒泡排序的優(yōu)化58
3.2快速排序59
3.2.1快速排序的基本原理59
3.2.2快速排序算法的步驟59
3.2.3快速排序的基本算法實現(xiàn)59
3.3其他排序60
3.4實例演示60
3.4.1出現(xiàn)次數(shù)超過一半的數(shù)60
3.4.2獎學金發(fā)放62
3.4.3魔法照片63
3.4.4輸出前k大的數(shù)65
3.4.5不重復地輸出數(shù)66
3.4.6單詞排序67
3.4.7快速排序68
3.4.8第k個數(shù)70
第4章查找72
4.1查找的概念72
4.2順序查找算法72
4.2.1順序查找算法的概念72
4.2.2順序查找算法的步驟72
4.2.3順序查找算法的實現(xiàn)73
4.3折半查找算法73
4.3.1折半查找算法的基本思想73
4.3.2折半查找算法的步驟73
4.3.3折半查找算法的實現(xiàn)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深度優(yōu)先搜索與廣度優(yōu)先搜索81
5.1.3回溯84
5.2搜索算法的一些優(yōu)化85
5.2.1剪枝函數(shù)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基環(huán)樹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最短網(wǎng)絡133
7.7.4暢通工程135
7.7.5城市公交137
7.7.6趣味象棋140
第8章動態(tài)規(guī)劃143
8.1基本思想145
8.2基本概念145
8.3基本原理146
8.3.1最優(yōu)化原理146
8.3.2無后效性146
8.4一般步驟146
8.5實例演示147
8.5.1數(shù)字三角形147
8.5.2括號匹配150
8.5.3背包問題151
8.5.4骨灰級玩家考證篇154
8.5.5猴子游戲157
第9章高級數(shù)據(jù)結構159
9.1三種常用高級數(shù)據(jù)結構159
9.1.1線段樹159
9.1.2并查集162
9.1.3樹狀數(shù)組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無線網(wǎng)絡188
第10章數(shù)論192
10.1質數(shù)查找192
10.2快速乘方194
10.3最大公約數(shù)196
10.4最小公倍數(shù)196
10.5模冪運算197
10.6斐波那契數(shù)列198
10.6.1斐波那契數(shù)列(遞歸實現(xiàn))199
10.6.2斐波那契數(shù)列2(遞推實現(xiàn))200
10.6.3爬樓梯201
10.6.4一只小蜜蜂202
10.6.5骨牌鋪方格203
10.7歐拉函數(shù)205
10.7.1概念205
10.7.2性質205
10.7.3實現(xiàn)方法205
10.8實例演示207
10.8.1歐拉函數(shù)例題207
10.8.2阿里巴巴的寶藏208
第11章組合數(shù)學211
11.1基本計數(shù)定理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你能找到多少個整數(shù)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不可重組合數(shù)244
11.4.2可重復組合數(shù)244
11.4.3不相鄰組合數(shù)244
11.4.4組合數(shù)的常用公式245
11.4.5求組合數(shù)的方法245
11.4.6車248
11.4.7壁畫250
11.4.8二項式252
11.4.9集合的劃分254
11.5組合數(shù)取模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卡特蘭數(shù)列269
11.6.1卡特蘭數(shù)的公式269
11.6.2卡特蘭數(shù)的應用270
11.6.3卡特蘭數(shù)的實現(xiàn)270
11.6.4小濤叔叔的禮物271
11.6.5號碼連接游戲272
11.6.6李嵩的作業(yè)274
11.7斯特林數(shù)277
11.7.1第一類斯特林數(shù)277
11.7.2第二類斯特林數(shù)278
11.7.3二進制斯特林數(shù)280
11.8母函數(shù)282
11.8.1方形硬幣（母函數(shù)）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嚴格優(yōu)勢策略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