鏈接：https://pan.baidu.com/s/1yifGwQUM6I0n439AyZJKyw?pwd=vrf0?

提取碼：vrf0

本書共13章，依次講述程序設(shè)計(jì)基礎(chǔ)、算法基礎(chǔ)、排序、查找、搜索、字符串匹配、圖論、動(dòng)態(tài)規(guī)劃、高級數(shù)據(jù)結(jié)構(gòu)、數(shù)論、組合數(shù)學(xué)、計(jì)算幾何基礎(chǔ)、博弈論。

書中提供了大量習(xí)題和答案供讀者學(xué)習(xí)使用。

本書可作為高等學(xué)校計(jì)算機(jī)相關(guān)專業(yè)算法設(shè)計(jì)類課程的教材，也可供對算法設(shè)計(jì)、程序設(shè)計(jì)競賽感興趣的讀者自學(xué)使用。

目錄

第1章程序設(shè)計(jì)基礎(chǔ)1

1.1程序設(shè)計(jì)語言入門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)入門（基礎(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漢諾塔問題33

2.1.3n皇后問題35

2.2分治算法37

2.2.1分治算法概述37

2.2.2計(jì)數(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冒泡排序的基本算法實(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ù)超過一半的數(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縮寫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實(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無后效性146

8.4一般步驟146

8.5實(shí)例演示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ù)結(jié)構(gòu)159

9.1三種常用高級數(shù)據(jù)結(jié)構(gòu)159

9.1.1線段樹159

9.1.2并查集162

9.1.3樹狀數(shù)組167

9.2紅黑樹172

9.2.1紅黑樹的調(diào)整策略173

9.2.2參考程序179

9.3實(shí)例演示183

9.3.1人工湖公路183

9.3.2宗教信仰問題186

9.3.3無線網(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常見應(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壁畫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組合問題262

11.5.7問題制造者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號碼連接游戲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)勢策略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

參考文獻(xiàn)313

查看全部↓

前言/序言

近幾年，在校學(xué)生以及在職者對與算法相關(guān)的知識(shí)越來越重視，但現(xiàn)有的針對初學(xué)者的算法書籍卻不多。本書根據(jù)算法的相關(guān)知識(shí)由淺入深地進(jìn)行介紹，提供了大量目前比較主流類型的題目并對其進(jìn)行解析。題目側(cè)重基礎(chǔ)，淺顯易懂，適合不同水平的讀者學(xué)習(xí)。

作為大學(xué)計(jì)算機(jī)類專業(yè)的教師，我們一直堅(jiān)持認(rèn)為學(xué)習(xí)的目的不僅僅是獲取知識(shí)，更重要的是具備分析問題和解決問題的能力。而算法是程序設(shè)計(jì)的靈魂，算法的選擇則代表著用程序設(shè)計(jì)解決具體問題的能力，因此算法的優(yōu)劣決定了用程序解決問題的效率。

算法設(shè)計(jì)是算法思維的體現(xiàn)，算法運(yùn)用不好的程序員，很難說是一名好的程序員。計(jì)算機(jī)類專業(yè)人才理應(yīng)具有一定的算法功底，擁有一定的算法思維，并且能利用這些思想有效地轉(zhuǎn)換為解決程序設(shè)計(jì)問題的能力。因此，本書特別強(qiáng)調(diào)算法實(shí)踐，通過對具體的例題、程序的算法解析，講解程序設(shè)計(jì)的思路和具體實(shí)現(xiàn)，并配有大量的課后習(xí)題以供練習(xí)。

本書依次講述程序設(shè)計(jì)基礎(chǔ)、算法基礎(chǔ)、排序、查找、搜索、字符串匹配、圖論、動(dòng)態(tài)規(guī)劃、高級數(shù)據(jù)結(jié)構(gòu)、數(shù)論、組合數(shù)學(xué)、計(jì)算幾何基礎(chǔ)、博弈論。

本書不僅講解這些算法的基本原理，還結(jié)合具體案例詳細(xì)介紹這些算法的應(yīng)用。本書涉及的程序設(shè)計(jì)問題將充分鍛煉讀者的思維能力和動(dòng)手能力，有助于讀者形成全面、靈活、縝密的思考習(xí)慣，從而提升讀者解決未知問題的能力。