算法：數(shù)學(xué)應(yīng)用與競(jìng)賽案例解析

第1章程序設(shè)計(jì)基礎(chǔ)1
1.1程序設(shè)計(jì)語(yǔ)言入門(mén)1
1.1.1基本數(shù)據(jù)類型2
1.1.2順序結(jié)構(gòu)程序設(shè)計(jì)2
1.1.3條件結(jié)構(gòu)程序設(shè)計(jì)3
1.1.4循環(huán)結(jié)構(gòu)7
1.1.5數(shù)組12
1.1.6函數(shù)18
1.1.7指針20
1.1.8結(jié)構(gòu)體22
1.2數(shù)據(jù)結(jié)構(gòu)入門(mén)（基礎(chǔ)）27
1.2.1棧28
1.2.2隊(duì)列29
1.2.3鏈隊(duì)30
第2章算法基礎(chǔ)33
2.1遞歸算法33
2.1.1遞歸算法概述33
2.1.2漢諾塔問(wèn)題33
2.1.3n皇后問(wèn)題35
2.2分治算法37
2.2.1分治算法概述37
2.2.2計(jì)數(shù)問(wèn)題38
2.2.3歸并排序40
2.3枚舉41
2.3.1木棒三角形42
2.3.2四大湖問(wèn)題43
2.4貪心44
2.4.1砝碼稱重44
2.4.2石頭剪刀布45
2.4.3馬馳愛(ài)釣魚(yú)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冒泡排序的基本算法實(shí)現(xiàn)57
3.1.4冒泡排序的優(yōu)化58
3.2快速排序59
3.2.1快速排序的基本原理59
3.2.2快速排序算法的步驟59
3.2.3快速排序的基本算法實(shí)現(xiàn)59
3.3其他排序60
3.4實(shí)例演示60
3.4.1出現(xiàn)次數(shù)超過(guò)一半的數(shù)60
3.4.2獎(jiǎng)學(xué)金發(fā)放62
3.4.3魔法照片63
3.4.4輸出前k大的數(shù)65
3.4.5不重復(fù)地輸出數(shù)66
3.4.6單詞排序67
3.4.7快速排序68
3.4.8第k個(gè)數(shù)70
第4章查找72
4.1查找的概念72
4.2順序查找算法72
4.2.1順序查找算法的概念72
4.2.2順序查找算法的步驟72
4.2.3順序查找算法的實(shí)現(xiàn)73
4.3折半查找算法73
4.3.1折半查找算法的基本思想73
4.3.2折半查找算法的步驟73
4.3.3折半查找算法的實(shí)現(xiàn)73
4.4實(shí)例演示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實(shí)例演示85
5.3.1寶石游戲85
5.3.2騎士移動(dòng)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實(shí)例演示104
6.6.1最低三元字符串104
6.6.2從左側(cè)刪除107
6.6.3字母刪除109
6.6.4潛伏者111
6.6.5處女座與復(fù)讀機(jī)113
6.6.6縮寫(xiě)117
第7章圖論119
7.1最短路徑介紹119
7.2最小生成樹(shù)121
7.2.1Kruskal算法121
7.2.2Prim算法122
7.3樹(shù)的直徑與最近公共祖先123
7.3.1樹(shù)的直徑123
7.3.2最近公共祖先123
7.4基環(huán)樹(shù)125
7.4.1定義125
7.4.2一般的題型125
7.4.3一般解題思路125
7.5Tarjan算法與無(wú)向圖和有向圖連通性125
7.5.1Tarjan算法與無(wú)向圖連通性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實(shí)例演示130
7.7.1黑與白130
7.7.2迷宮132
7.7.3最短網(wǎng)絡(luò)133
7.7.4暢通工程135
7.7.5城市公交137
7.7.6趣味象棋140
第8章動(dòng)態(tài)規(guī)劃143
8.1基本思想145
8.2基本概念145
8.3基本原理146
8.3.1最優(yōu)化原理146
8.3.2無(wú)后效性146
8.4一般步驟146
8.5實(shí)例演示147
8.5.1數(shù)字三角形147
8.5.2括號(hào)匹配150
8.5.3背包問(wèn)題151
8.5.4骨灰級(jí)玩家考證篇154
8.5.5猴子游戲157
第9章高級(jí)數(shù)據(jù)結(jié)構(gòu)159
9.1三種常用高級(jí)數(shù)據(jù)結(jié)構(gòu)159
9.1.1線段樹(shù)159
9.1.2并查集162
9.1.3樹(shù)狀數(shù)組167
9.2紅黑樹(shù)172
9.2.1紅黑樹(shù)的調(diào)整策略173
9.2.2參考程序179
9.3實(shí)例演示183
9.3.1人工湖公路183
9.3.2宗教信仰問(wèn)題186
9.3.3無(wú)線網(wǎng)絡(luò)188
第10章數(shù)論192
10.1質(zhì)數(shù)查找192
10.2快速乘方194
10.3最大公約數(shù)196
10.4最小公倍數(shù)196
10.5模冪運(yùn)算197
10.6斐波那契數(shù)列198
10.6.1斐波那契數(shù)列(遞歸實(shí)現(xiàn))199
10.6.2斐波那契數(shù)列2(遞推實(shí)現(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性質(zhì)205
10.7.3實(shí)現(xiàn)方法205
10.8實(shí)例演示207
10.8.1歐拉函數(shù)例題207
10.8.2阿里巴巴的寶藏208
第11章組合數(shù)學(xué)211
11.1基本計(jì)數(shù)定理211
11.1.1加法原理與乘法原理211
11.1.2抽屜原理（鴿巢原理）214
11.2容斥原理219
11.2.1原理概述219
11.2.2常見(jiàn)應(yīng)用219
11.2.3矩形并的面積222
11.2.42月29日223
11.2.5跳蚤226
11.2.6幫助蟬228
11.2.7你能找到多少個(gè)整數(shù)231
11.3排列233
11.3.1可重復(fù)排列233
11.3.2不可重復(fù)排列233
11.3.3不全相異元素的選排列235
11.3.4不全相異元素的全排列235
11.3.5錯(cuò)位排列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可重復(fù)組合數(shù)244
11.4.3不相鄰組合數(shù)244
11.4.4組合數(shù)的常用公式245
11.4.5求組合數(shù)的方法245
11.4.6車248
11.4.7壁畫(huà)250
11.4.8二項(xiàng)式252
11.4.9集合的劃分254
11.5組合數(shù)取模255
11.5.1遞推打表255
11.5.2盧卡斯定理255
11.5.3盧卡斯定理擴(kuò)展256
11.5.4孤獨(dú)的李雷259
11.5.5走格子的騎士261
11.5.6組合問(wèn)題262
11.5.7問(wèn)題制造者264
11.5.8抽獎(jiǎng)游戲267
11.6卡特蘭數(shù)列269
11.6.1卡特蘭數(shù)的公式269
11.6.2卡特蘭數(shù)的應(yīng)用270
11.6.3卡特蘭數(shù)的實(shí)現(xiàn)270
11.6.4小濤叔叔的禮物271
11.6.5號(hào)碼連接游戲272
11.6.6李嵩的作業(yè)274
11.7斯特林?jǐn)?shù)277
11.7.1第一類斯特林?jǐn)?shù)277
11.7.2第二類斯特林?jǐn)?shù)278
11.7.3二進(jìn)制斯特林?jǐn)?shù)280
11.8母函數(shù)282
11.8.1方形硬幣（母函數(shù)）282
11.8.2尋找拉希德284
11.8.3排列組合286
第12章計(jì)算幾何基礎(chǔ)289
12.1矢量289
12.1.1矢量的概念289
12.1.2矢量加減法289
12.1.3矢量叉積289
12.1.4矢量叉積的應(yīng)用290
12.2包含關(guān)系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博弈論的基本構(gòu)成要素304
13.1.1零和博弈304
13.1.2嚴(yán)格優(yōu)勢(shì)策略305
13.1.3囚徒困境305
13.1.4智豬博弈305
13.1.5納什均衡306
13.2最小最大問(wèn)題306
13.3尼姆博弈307
13.4巴什博弈310
13.5斐波那契博弈311
參考文獻(xiàn)313