圖書信息
出版社: 清華大學出版社; 第1版 (2009年11月1日)
叢書名: 算法藝術與信息學競賽
平裝: 225頁
正文語種: 簡體中文
開本: 16
ISBN: 9787302206088
條形碼: 9787302206088
尺寸: 25.8 x 18.4 x 1.2 cm
重量: 440 g
作者簡介
劉汝佳，1982年12月生，高中畢業於重慶市外國語學校。
2000年3月獲得NO12000全國青少年信息學奧林匹克競賽一等獎第四名，進入國家集訓隊，並因此保送到清華大學計算機科學與技術系。大一時獲2001年ACM/ICPC國際大學生程式設計競賽亞洲一上海賽區冠軍和2002年世界總決賽銀牌（世界第四），2005年獲學士學位，2008年獲碩士學位。
學生時代曾為中國計算機學會NOI科學委員會學生委員，擔任J012002-2008中國國家隊教練，並為NOI系列比賽命題十餘道。現為NOI競賽委員會委員，並在NOI 25周年時獲得中國計算機學會頒發的“特別貢獻獎”。
2004年至今共為ACM/ICPC亞洲賽區命題二十餘道，擔任6次裁判和2次命題總監，並應邀參加IOI和ACM/lCPC相關國際研討會，發表論文兩篇。
2004年初作為第一作者出版專著《算法藝術與信息學競賽》，2009年出版譯著《編程挑戰》。
多年來在全國二十餘個城市進行中學生競賽培訓工作，為北京、上海、吉隆坡等地的著名高校授課與宣講，並多次與TopCodet、百度和網易有道等知名企業合作舉辦比賽，讓更多的IT人才獲得展示自我的平台。
內容簡介
《算法競賽入門經典》是一本算法競賽的入門教材，把C/C++語言、算法和解題有機地結合在了一起，淡化理論，注重學習方法和實踐技巧。全書內容分為11章，包括程式設計入門、循環結構程式設計、數組和字元串、函式和遞歸、基礎題目選解、數據結構基礎、暴力求解法、高效算法設計、動態規劃初步、數學概念與方法、圖論模型與算法，覆蓋了算法競賽入門所需的主要知識點，並附有大量習題。書中的代碼規範、簡潔、易懂，不僅能幫助讀者理解算法原理，還能教會讀者很多實用的編程技巧。另外，書中包含的各種開發、測試和調試技巧也是在傳統的語言、算法類書籍中難以見到的。
《算法競賽入門經典》可作為全國青少年信息學奧林匹克聯賽（NOIP）的複賽教材及ACM國際大學生程式設計競賽。
目錄
第1部分 語言篇
第1章 程式設計入門1
1.1 算術表達式1
1.2 變數及其輸入3
1.3 順序結構程式設計6
1.4 分支結構程式設計9
1.5 小結與習題13
1.5.1 數據類型實驗13
1.5.2 scanf輸入格式實驗13
1.5.3 printf語句輸出實驗13
1.5.4 測測你的實踐能力14
1.5.5 小結14
1.5.6 上機練習15
第2章 循環結構程式設計16
2.1 for循環16
2.2 循環結構程式設計19
2.3 檔案操作23
2.4 小結與習題27
2.4.1 輸出技巧28
2.4.2 浮點數陷阱28
2.4.3 64位整數28
2.4.4 C++中的輸入輸出29
2.4.5 小結30
2.4.6 上機練習31
第3章 數組和字元串33
3.1 數組33
3.2 字元數組37
3.3 最長回文子串41
3.4 小結與習題45
3.4.1 必要的存儲量45
3.4.2 用ASCII編碼表示字元45
3.4.3 補碼錶示法46
3.4.4 重新實現庫函式47
3.4.5 字元串處理的常見問題47
3.4.6 關於輸入輸出47
3.4.7 I/O的效率47
3.4.8 小結49
3.4.9 上機練習50
第4章 函式和遞歸51
4.1 數學函式51
4.1.1 簡單函式的編寫51
4.1.2 使用結構體的函式52
4.1.3 套用舉例53
4.2 地址和指針56
4.2.1 變數交換56
4.2.2 調用棧57
4.2.3 用指針實現變數交換59
4.2.4 初學者易犯的錯誤61
4.3 遞歸62
4.3.1 遞歸定義62
4.3.2 遞歸函式63
4.3.3 C語言對遞歸的支持64
4.3.4 段錯誤與棧溢出66
4.4 本章小結67
4.4.1 小問題集錦67
4.4.2 小結68
第2部分 算法篇
第5章 基礎題目選解69
5.1 字元串69
5.1.1 WERTYU69
5.1.2 TeX括弧70
5.1.3 周期串71
5.2 高精度運算71
5.2.1 國小生算術72
5.2.2 階乘的精確值72
5.2.3 高精度運算類bign73
5.2.4 重載bign的常用運算符75
5.3 排序與檢索77
5.3.1 6174問題77
5.3.2 字母重排78
5.4 數學基礎81
5.4.1 Cantor的數表81
5.4.2 因子和階乘82
5.4.3 果園裡的樹84
5.4.4 多少塊土地86
5.5 訓練參考86
5.5.1 黑盒測試86
5.5.2 線上評測系統87
5.5.3 推薦題目88
第6章 數據結構基礎89
6.1 棧和佇列89
6.1.1 卡片遊戲89
6.1.2 鐵軌91
6.2 鍊表93
6.2.1 初步分析93
6.2.2 鏈式結構95
6.2.3 對比測試96
6.2.4 隨機數發生器98
6.3 二叉樹99
6.3.1 小球下落99
6.3.2 層次遍歷101
6.3.3 二叉樹重建105
6.4 圖106
6.4.1 黑白圖像107
6.4.2 走迷宮108
6.4.3 拓撲排序110
6.4.4 歐拉迴路111
6.5 訓練參考112
第7章 暴力求解法114
7.1 簡單枚舉114
7.1.1 除法114
7.1.2 最大乘積115
7.1.3 分數拆分115
7.1.4 雙基迴文數116
7.2 枚舉排列116
7.2.1 生成1～n的排列116
7.2.2 生成可重集的排列118
7.2.3 解答樹118
7.2.4 下一個排列119
7.3 子集生成120
7.3.1 增量構造法120
7.3.2 位向量法121
7.3.3 二進制法122
7.4 回溯法123
7.4.1 八皇后問題123
7.4.2 素數環126
7.4.3 困難的串127
7.4.4 頻寬128
7.5 隱式圖搜尋129
7.5.1 隱式樹的遍歷129
7.5.2 一般隱式圖的遍歷130
7.5.3 八數碼問題131
7.5.4 結點查找表133
7.6 訓練參考136
第8章 高效算法設計138
8.1 算法分析初步138
8.1.1 漸進時間複雜度138
8.1.2 上界分析140
8.1.3 分治法140
8.1.4 正確對待算法分析結果142
8.2 再談排序與檢索143
8.2.1 歸併排序143
8.2.2 快速排序145
8.2.3 二分查找145
8.3 遞歸與分治148
8.3.1 棋盤覆蓋問題148
8.3.2 循環日程表問題149
8.3.3 巨人與鬼149
8.3.4 非線性方程求根150
8.3.5 最大值最小化151
8.4 貪心法151
8.4.1 最優裝載問題151
8.4.2 部分背包問題152
8.4.3 乘船問題152
8.4.4 選擇不相交區間152
8.4.5 區間選點問題153
8.4.6 區間覆蓋問題154
8.4.7 Huffman編碼154
8.5 訓練參考156
第3部分 競賽篇
第9章 動態規劃初步158
9.1 數字三角形158
9.1.1 問題描述與狀態定義158
9.1.2 記憶化搜尋與遞推159
9.2 DAG上的動態規劃161
9.2.1 DAG模型161
9.2.2 最長路及其字典序162
9.2.3 固定終點的最長路和最短路163
9.3 0-1背包問題167
9.3.1 多階段決策問題167
9.3.2 規劃方向168
9.3.3 滾動數組169
9.4 遞歸結構中的動態規劃170
9.4.1 表達式上的動態規劃170
9.4.2 凸多邊形上的動態規劃171
9.4.3 樹上的動態規劃171
9.5 集合上的動態規劃172
9.5.1 狀態及其轉移173
9.5.2 隱含的階段173
9.6 訓練參考174
第10章 數學概念與方法176
10.1 數論初步176
10.1.1 除法表達式176
10.1.2 無平方因子的數178
10.1.3 直線上的點179
10.1.4 同餘與模算術180
10.2 排列與組合182
10.2.1 楊輝三角與二項式定理182
10.2.2 數論中的計數問題184
10.2.3 編碼與解碼186
10.2.4 離散機率初步187
10.3 遞推關係188
10.3.1 漢諾塔188
10.3.2 Fibonacci數列189
10.3.3 Catalan數191
10.3.4 危險的組合192
10.3.5 統計n-k特殊集的數目193
10.4 訓練參考194
第11章 圖論模型與算法196
11.1 再談樹196
11.1.1 無根樹轉有根樹196
11.1.2 表達式樹197
11.1.3 最小生成樹199
11.1.4 並查集200
11.2 最短路問題201
11.2.1 Dijkstra算法202
11.2.2 稀疏圖的鄰接表203
11.2.3 使用優先佇列的Dijkstra算法204
11.2.4 Bellman-Ford算法205
11.2.5 Floyd算法206
11.3 網路流初步207
11.3.1 最大流問題207
11.3.2 增廣路算法208
11.3.3 最小割最大流定理210
11.3.4 最小費用最大流問題211
11.4 進一步學習的參考212
11.4.1 程式語言213
11.4.2 數據結構213
11.4.3 算法設計213
11.4.4 數學214
11.4.5 參賽指南214
11.5 訓練參考215
附錄A 開發環境與方法216
A.1 命令行216
A.1.1 檔案系統216
A.1.2 進程217
A.1.3 程式的執行217
A.1.4 重定向和管道218
A.1.5 常見命令218
A.2 作業系統腳本編程入門219
A.2.1 Windows下的批處理219
A.2.2 Linux下的Bash腳本220
A.2.3 再談隨機數221
A.3 編譯器和調試器221
A.3.1 gcc的安裝和測試221
A.3.2 常見編譯選項222
A.3.3 gdb簡介223
A.3.4 gdb的高級功能224
A.4 淺談IDE225
