《算法競賽入門經典（第二版）》pdf

下載下傳位址：網盤下載下傳

内容簡介  · · · · · ·

《算法競賽入門經典（第2版）》是一本算法競賽的入門與提高教材，把C/C++語言、算法和解題有機地結合在一起，淡化理論，注重學習方法和實踐技巧。全書内容分為12 章，包括程式設計入門、循環結構程式設計、數組和字元串、函數和遞歸、C++與STL入門、資料結構基礎、暴力求解法、高效算法設計、動态規劃初步、數學概念與方法、圖論模型與算法、進階專題等内容，覆寫了算法競賽入門和提高所需的主要知識點，并含有大量例題和習題。書中的代碼規範、簡潔、易懂，不僅能幫助讀者了解算法原理，還能教會讀者很多實用的程式設計技巧；書中包含的各種開發、測試和調試技巧也是傳統的語言、算法類書籍中難以見到的。

《算法競賽入門經典（第2版）》可作為全國青少年資訊學奧林匹克聯賽（NOIP）複賽教材、全國青少年資訊學奧林匹克競賽（NOI）和ACM國際大學生程式設計競賽（ACM/ICPC）的訓練資料，也可作為IT工程師與科研人員的參考用書。

作者簡介  · · · · · ·

劉汝佳，1982年12月生，高中畢業于重慶市外國語學校。2000年3月獲得NOI2000全國青少年資訊學奧林匹克競賽一等獎第四名，進入國家集訓隊，并是以保送到清華大學計算機科學與技術系。大一時獲2001年ACM/ICPC國際大學生程式設計競賽亞洲-上海賽區冠軍和2002年世界總決賽銀牌（世界第四），2005年獲學士學位，2008年獲碩士學位。

學生時代曾為中國計算機學會NOI科學委員會學生委員，擔任IOI2002-2008中國國家隊教練，并為NOI系列比賽命題十餘道。現為NOI競賽委員會委員，并在NOI 25周年時獲得中國計算機學會頒發的“特别貢獻獎”。

2004年至今共為ACM/ICPC亞洲賽區命題二十餘道，擔任6次裁判和2次命題總監，并應邀參加IOI和ACM/ICPC相關國際研讨會，發表論文兩篇。

2004年初作為第一作者出版專著《算法藝術與資訊學競賽》，2009年出版譯著《程式設計挑戰》，2009年出版《算法競賽入門經典》，2012年出版《算法競賽入門經典——訓練指南》。

多年來在全國二十餘個城市進行中學生競賽教育訓練工作，為北京、上海、吉隆坡等地的著名高校授課與宣講，并多次與TopCoder、百度和網易有道等知名企業合作舉辦比賽，讓更多的IT人才獲得展示自我的平台。

目錄  · · · · · ·

第1部分　語言篇

第1章　程式設計入門 1

1.1 算術表達式 1

1.2 變量及其輸入 3

1.3 順序結構程式設計 6

1.4 分支結構程式設計 9

1.5 注解與習題 13

1.5.1 C語言、C99、C11及其他 13

1.5.2 資料類型與輸入格式 14

1.5.3 習題 15

1.5.4 小結 16

第2章　循環結構程式設計 18

2.1 for循環 18

2.2 while循環和do-while循環 22

2.3 循環的代價 25

2.4 算法競賽中的輸入輸出架構 27

2.5 注解與習題 34

2.5.1 習題 34

2.5.2 小結 36

第3章　數組和字元串 37

3.1 數組 37

3.2 字元數組 41

3.3 競賽題目選講 45

3.4 注解與習題 53

3.4.1 進位制與整數表示 54

3.4.2 思考題 55

3.4.3 黑盒測試和線上評測系統 55

3.4.4 例題一覽與習題 56

3.4.5 小結 59

第4章　函數和遞歸 61

4.1 自定義函數和結構體 61

4.2 函數調用與參數傳遞 65

4.2.1 形參與實參 65

4.2.2 調用棧 66

4.2.3 用指針作參數 69

4.2.4 初學者易犯的錯誤 71

4.2.5 數組作為參數和傳回值 71

4.2.6 把函數作為函數的參數 73

4.3 遞歸 74

4.3.1 遞歸定義 74

4.3.2 遞歸函數 75

4.3.3 C語言對遞歸的支援 75

4.3.4 段錯誤與棧溢出 77

4.4 競賽題目選講 79

4.5 注解與習題 92

4.5.1 頭檔案、副作用及其他 93

4.5.2 例題一覽和習題 95

4.5.3 小結 99

第5章　 C++與STL入門 100

5.1 從C到C++ 100

5.1.1 C++版架構 101

5.1.2 引用 102

5.1.3 字元串 103

5.1.4 再談結構體 105

5.1.5 模闆 106

5.2 STL初步 108

5.2.1 排序與檢索 108

5.2.2 不定長數組：vector 109

5.2.3 集合：set 112

5.2.4 映射：map 113

5.2.5 棧、隊列與優先隊列 115

5.2.6 測試STL 120

5.3 應用：大整數類 123

5.3.1 大整數類BigInteger 124

5.3.2 四則運算 125

5.3.3 比較運算符 126

5.4 競賽題目舉例 127

5.5 習題 134

第2部分　基礎篇

第6章　資料結構基礎 139

6.1 再談棧和隊列 139

6.2 連結清單 143

6.3 樹和二叉樹 148

6.3.1 二叉樹的編号 148

6.3.2 二叉樹的層次周遊 150

6.3.3 二叉樹的遞歸周遊 155

6.3.4 非二叉樹 160

6.4 圖 162

6.4.1 用DFS求連通塊 162

6.4.2 用BFS求最短路 164

6.4.3 拓撲排序 167

6.4.4 歐拉回路 168

6.5 競賽題目選講 170

6.6 訓練參考 175

第7章　暴力求解法 182

7.1 簡單枚舉 182

7.2 枚舉排列 184

7.2.1 生成1~n的排列 184

7.2.2 生成可重集的排列 185

7.2.3 解答樹 186

7.2.4 下一個排列 187

7.3 子集生成 188

7.3.1 增量構造法 188

7.3.2 位向量法 188

7.3.3 二進制法 189

7.4 回溯法 191

7.4.1 八皇後問題 191

7.4.2 其他應用舉例 194

7.5 路徑尋找問題 198

7.6 疊代加深搜尋 206

7.7 競賽題目選講 209

7.8 訓練參考 213

第3部分　競賽篇

第8章　高效算法設計 220

8.1 算法分析初步 220

8.1.1 漸進時間複雜度 220

8.1.2 上界分析 222

8.1.3 分治法 223

8.1.4 正确對待算法分析結果 224

8.2 再談排序與檢索 225

8.2.1 歸并排序 225

8.2.2 快速排序 227

8.2.3 二分查找 227

8.3 遞歸與分治 229

8.4 貪心法 231

8.4.1 背包相關問題 231

8.4.2 區間相關問題 232

8.4.3 Huffman編碼 234

8.5 算法設計與優化政策 235

8.6 競賽題目選講 244

8.7 訓練參考 252

第9章　動态規劃初步 259

9.1 數字三角形 259

9.1.1 問題描述與狀态定義 259

9.1.2 記憶化搜尋與遞推 260

9.2 DAG上的動态規劃 262

9.2.1 DAG模型 262

9.2.2 最長路及其字典序 262

9.2.3 固定終點的最長路和最短路 264

9.2.4 小結與應用舉例 267

9.3 多階段決策問題 270

9.3.1 多段圖的最短路 270

9.3.2 0-1背包問題 271

9.4 更多經典模型 274

9.4.1 線性結構上的動态規劃 274

9.4.2 樹上的動态規劃 280

9.4.3 複雜狀态的動态規劃 284

9.5 競賽題目選講 290

9.6 訓練參考 303

第10章　數學概念與方法 310

10.1 數論初步 310

10.1.1 歐幾裡德算法和唯一分解定理 310

10.1.2 Eratosthenes篩法 312

10.1.3 擴充歐幾裡德算法 313

10.1.4 同餘與模算術 314

10.1.5 應用舉例 316

10.2 計數與機率基礎 318

10.2.1 楊輝三角與二項式定理 319

10.2.2 數論中的計數問題 321

10.2.3 編碼與解碼 323

10.2.4 離散機率初步 324

10.3 其他數學專題 327

10.3.1 遞推 327

10.3.2 數學期望 332

10.3.3 連續機率 334

10.4 競賽題目選講 336

10.5 訓練參考 341

第11章　圖論模型與算法 352

11.1 再談樹 352

11.1.1 無根樹轉有根樹 352

11.1.2 表達式樹 353

11.2 最小生成樹 355

11.2.1 Kruskal算法 356

11.2.2 競賽題目選解 358

11.3 最短路問題 359

11.3.1 Dijkstra算法 359

11.3.2 Bellman-Ford算法 363

11.3.3 Floyd算法 364

11.3.4 競賽題目選講 365

11.4 網絡流初步 366

11.4.1 最大流問題 366

11.4.2 增廣路算法 367

11.4.3 最小割最大流定理 369

11.4.4 最小費用最大流問題 370

11.4.5 應用舉例 372

11.5 競賽題目選講 375

11.6 訓練參考 379

11.7 總結與展望 384

第12章　進階專題 386

12.1 知識點選講 386

12.1.1 自動機 386

12.1.2 樹的經典問題和方法 392

12.1.3 可持久化資料結構 397

12.1.4 多邊形的布爾運算 399

12.2 難題選解 404

12.2.1 資料結構 404

12.2.2 網絡流 409

12.2.3 數學 411

12.2.4 幾何 415

12.2.5 非完美算法 419

12.2.6 雜題選講 423

12.3 小結與習題 446

附錄A 開發環境與方法 455

A.1 指令行 455

A.1.1 檔案系統 455

A.1.2 程序 456

A.1.3 程式的執行 456

A.1.4 重定向和管道 457

A.1.5 常見指令 457

A.2 作業系統腳本程式設計入門 458

A.2.1 Windows下的批處理 458

A.2.2 Linux下的Bash腳本 459

A.2.3 再談随機數 460

A.3 編譯器和調試器 460

A.3.1 gcc的安裝和測試 460

A.3.2 常見編譯選項 461

A.3.3 gdb簡介 462

A.3.4 gdb的進階功能 463

A.4 淺談IDE 464

主要參考書目 465

下載下傳位址： 網盤下載下傳 下載下傳位址： 網盤下載下傳

轉載于:https://www.cnblogs.com/long12365/p/9732114.html