是一本算法競賽的入門與提高教材,把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競賽委員會委員,並在NOI25周年時獲得中國計算機學會頒發的「特別貢獻獎」。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.1C語言、C99、C11及其他13
1.5.2數據類型與輸入格式14
1.5.3習題15
1.5.4小結16
第2章 循環結構程序設計18
2.1for循環18
2.2while循環和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.3C語言對遞歸的支持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.1C++版框架101
5.1.2引用102
5.1.3字符串103
5.1.4再談結構體105
5.1.5模板106
5.2STL初步108
5.2.1排序與檢索108
5.2.2不定長數組:vector109
5.2.3集合:set112
5.2.4映射:map113
5.2.5棧、隊列與優先隊列115
5.2.6測試STL120
5.3應用:大整數類123
5.3.1大整數類BigInteger124
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.3Huffman編碼234
8.5算法設計與優化策略235
8.6競賽題目選講244
8.7訓練參考252
第9章 動態規划初步259
9.1數字三角形259
9.1.1問題描述與狀態定義259
9.1.2記憶化搜索與遞推260
9.2DAG上的動態規划262
9.2.1DAG模型262
9.2.2最長路及其字典序262
9.2.3固定終點的最長路和最短路264
9.2.4小結與應用舉例267
9.3多階段決策問題270
9.3.1多段圖的最短路270
9.3.20—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.2Eratosthenes篩法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.1Kruskal算法356
11.2.2競賽題目選解358
11.3最短路問題359
11.3.1Dijkstra算法359
11.3.2Bellman—Ford算法363
11.3.3Floyd算法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.1Windows下的批處理458
A.2.2Linux下的Bash腳本459
A.2.3再談隨機數460
A.3編譯器和調試器460
A.3.1gcc的安裝和測試460
A.3.2常見編譯選項461
A.3.3gdb簡介462
A.3.4gdb的高級功能463
A.4淺談IDE464
主要參考書目465
第1章 程序設計入門1
1.1算術表達式1
1.2變量及其輸入3
1.3順序結構程序設計6
1.4分支結構程序設計9
1.5注解與習題13
1.5.1C語言、C99、C11及其他13
1.5.2數據類型與輸入格式14
1.5.3習題15
1.5.4小結16
第2章 循環結構程序設計18
2.1for循環18
2.2while循環和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.3C語言對遞歸的支持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.1C++版框架101
5.1.2引用102
5.1.3字符串103
5.1.4再談結構體105
5.1.5模板106
5.2STL初步108
5.2.1排序與檢索108
5.2.2不定長數組:vector109
5.2.3集合:set112
5.2.4映射:map113
5.2.5棧、隊列與優先隊列115
5.2.6測試STL120
5.3應用:大整數類123
5.3.1大整數類BigInteger124
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.3Huffman編碼234
8.5算法設計與優化策略235
8.6競賽題目選講244
8.7訓練參考252
第9章 動態規划初步259
9.1數字三角形259
9.1.1問題描述與狀態定義259
9.1.2記憶化搜索與遞推260
9.2DAG上的動態規划262
9.2.1DAG模型262
9.2.2最長路及其字典序262
9.2.3固定終點的最長路和最短路264
9.2.4小結與應用舉例267
9.3多階段決策問題270
9.3.1多段圖的最短路270
9.3.20—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.2Eratosthenes篩法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.1Kruskal算法356
11.2.2競賽題目選解358
11.3最短路問題359
11.3.1Dijkstra算法359
11.3.2Bellman—Ford算法363
11.3.3Floyd算法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.1Windows下的批處理458
A.2.2Linux下的Bash腳本459
A.2.3再談隨機數460
A.3編譯器和調試器460
A.3.1gcc的安裝和測試460
A.3.2常見編譯選項461
A.3.3gdb簡介462
A.3.4gdb的高級功能463
A.4淺談IDE464
主要參考書目465
網路書店
類別
折扣
價格
-
新書87折$260