程序設計競賽訓練營:基礎與數學概念

邱秋

  • 出版商: 人民郵電
  • 出版日期: 2022-03-01
  • 售價: $719
  • 貴賓價: 9.5$683
  • 語言: 簡體中文
  • 頁數: 455
  • ISBN: 7115578613
  • ISBN-13: 9787115578617
  • 立即出貨

  • 程序設計競賽訓練營:基礎與數學概念-preview-1
  • 程序設計競賽訓練營:基礎與數學概念-preview-2
程序設計競賽訓練營:基礎與數學概念-preview-1

買這商品的人也買了...

商品描述

本書是針對ACM主辦的國際大學生程序設計競賽的訓練指南,主要介紹程序設計和針對競賽訓練所需的基礎知識和基本數學概念,包括UVa OJ平臺的使用方法、C++的輸入輸出處理、C++庫實現所包含的數據結構、高級數據結構、字符串的處理和相關算法、排序與查找算法、代數、組合數學、數論、幾何等內容。本書在介紹基礎概念的基礎上,引入了眾多題目,以C++解題,針對部分題目給出參考代碼,方便參考和練習。

本書適合有意參加國際大學生程序設計競賽的本科生、研究生閱讀,對有意參加國際信息學奧林匹克競賽的中學生具有參考價值,也可作為電腦專業相關課程的參考教材。

作者簡介

邱秋,大学期间自学计算机技术,并于2004年和2006年分别取得了全国计算机技术与软件专业技术资格考试中的程序员和软件工程师的证书。对数据库技术感兴趣,在住院医师实习期间曾帮助科室开发了一款对肾衰竭腹膜透析患者进行健康随访的软件,在工作期间开发了数字营区、局域网考核等软件。爱好算法,酷爱读书。

目錄大綱

目錄

第 1章 準備 1

1.1 什麽是程序設計競賽 1

1.1.1 ACM-ICPC 1

1.1.2 Google Code Jam(GCJ) 1

1.1.3 TopCoder 2

1.1.4 CodeForces 2

1.1.5 IOI 2

1.2 如何使用UVa OJ 3

1.2.1 註冊 3

1.2.2 提交 3

1.3 如何選擇編程語言 6

1.4 輔助工具 6

1.3.1 UVa Arena 6

1.3.2 uHunt 6

1.3.3 uDebug 6

1.3.4 VirtualBox 6

1.3.5 Virtual Judge 7

1.3.6 洛谷 7

第 2章 入門 8

2.1 基本數據類型 8

2.1.1 整數的表示 8

2.1.2 浮點數的表示及精度 9

2.1.3 數據類型的取值範圍 12

2.2 格式化輸入 13

2.2.1 概述 13

2.2.2 標準輸入 14

2.2.3 字符串輸入 15

2.3 格式化輸出 18

2.3.1 概述 18

2.3.2 輸出對齊 20

2.3.3 整數輸出 20

2.3.4 實數輸出 21

2.3.5 緩沖區與輸入輸出同步 24

2.4 小結 26

第3章 數據結構 27

3.1 內置數組 27

3.1.1 順序記錄 27

3.1.2 游戲模擬 29

3.1.3 矩陣變換 30

3.1.4 約瑟夫問題 30

3.2 向量 34

3.3 棧 37

3.4 隊列及優先隊列 41

3.4.1 隊列 41

3.4.2 優先隊列 44

3.5 雙端隊列 46

3.6 映射 48

3.7 集合 52

3.8 位集 55

3.9 鏈表 58

3.10 二叉樹 59

3.11 範圍查詢 64

3.11.1 線段樹 64

3.11.2 二維線段樹 70

3.11.3 區間樹 76

3.11.4 樹狀數組 77

3.11.5 稀疏表 80

3.11.6 根號分塊 81

3.12 並查集 85

3.13 算法庫函數 87

3.13.1 accumulate和count、

 count_if 87

3.13.2 copy和reverse_copy 88

3.13.3 fill 88

3.13.4 iotac++11 89

3.13.5 max和min 89

3.13.6 max_element和min_element 90

3.13.7 memcpy和memset 90

3.14 小結 92

第4章 字符串 93

4.1 編碼 93

4.2 字符串類 94

4.2.1 聲明 95

4.2.2 賦值 96

4.2.3 遍歷 96

4.2.4 連接與刪除 97

4.2.5 查找與替換 98

4.2.6 其他操作 99

4.3 字符串庫函數 99

4.4 字符串類應用 101

4.4.1 文本解析 101

4.4.2 語法分析 105

4.4.3 KMP匹配算法 108

4.4.4 擴展KMP匹配算法 114

4.4.5 Z算法 116

4.4.6 字符串的最小表示 117

4.5 字符串數據結構及應用 118

4.5.1 Trie 118

4.5.2 Aho-Corasick算法 119

4.5.3 後綴數組 124

4.5.4 最長公共子串 131

4.5.5 最長重復子串 134

4.5.6 Burrows-Wheeler變換 135

4.6 正則表達式 136

4.6.1 元字符 136

4.6.2 轉義字符 137

4.6.3 數量匹配符和分組 137

4.6.4 字符類和可選模式 137

4.6.5 斷言 138

4.6.6 正則表達式類 138

4.7 算法庫函數 139

4.7.1 lexicographical_compare 139

4.7.2 next_permutation和prev_

 permutation 140

4.7.3 replace 143

4.7.4 reverse 143

4.7.5 transform 144

4.8 小結 144

第5章 排序與查找 145

5.1 交換排序 145

5.1.1 冒泡排序 145

5.1.2 快速排序 146

5.1.3 中位數 147

5.2 插入排序 149

5.2.1 直接插入排序 149

5.2.2 希爾排序 149

5.3 選擇排序 150

5.3.1 直接選擇排序 150

5.3.2 堆排序 150

5.4 歸並排序 151

5.4.1 逆序對數 151

5.5 計數排序 153

5.6 基數排序 153

5.7 桶排序 155

5.8 查找 155

5.8.1 順序查找 155

5.8.2 二分查找 156

5.8.3 方程求近似解 157

5.8.4 最大值最小化問題 159

5.8.5 三分搜索 160

5.9 算法庫函數 162

5.9.1 binary_search 162

5.9.2 find 162

5.9.3 lower_bound和upper_bound 163

5.9.4 nth_element 167

5.9.5 partial_sort 168

5.9.6 sort 168

5.9.7 stable_sort 171

5.9.8 unique 172

5.10 小結 173

第6章 算術與代數 174

6.1 割雞焉用牛刀乎 174

6.2 他山之石,可以攻玉 180

6.3 高精度整數類的實現 182

6.4 進制及其轉換 190

6.4.1 R進制數轉換為十進制數 190

6.4.2 十進制數轉換為R進制數 191

6.4.3 任意進制數之間的相互轉換 192

6.4.4 羅馬計數法 193

6.5 實數 195

6.5.1 分數 195

6.5.2 連續分數 198

6.5.3 分數轉換為小數 198

6.5.4 小數轉換為分數 199

6.5.5 實數大小的比較 200

6.6 代數 201

6.6.1 多項式運算 201

6.6.2 高斯消元法 202

6.7 冪與對數 209

6.8 實數函數庫 211

6.9 小結 212

第7章 組合數學 213

7.1 計數原理 213

7.1.1 加法原理 213

7.1.2 乘法原理 214

7.2 排列與組合 216

7.2.1 康托展開和康托逆展開 217

7.2.2 方程的整數解個數 222

7.3 Pólya計數定理 223

7.3.1 基本概念 223

7.3.2 Burnside引理 228

7.3.3 Pólya計數定理 231

7.4 鴿籠原理 236

7.4.1 拉姆齊理論 238

7.5 容斥原理 238

7.5.1 錯排問題 239

7.6 初等數列 240

7.6.1 等差數列 240

7.6.2 等比數列 240

7.6.3 其他數列 240

7.7 計數序列 241

7.7.1 斐波那契數 241

7.7.2 卡特蘭數 245

7.7.3 歐拉數 248

7.7.4 斯特林數 248

7.7.5 調和級數 249

7.7.6 其他序列 250

7.8 概率論 251

7.8.1 基本概念 251

7.8.2 條件概率和獨立事件 254

7.8.3 全概率公式與貝葉斯公式 256

7.8.4 隨機變量 260

7.8.5 期望 261

7.9 博弈論 269

7.9.1 Nim游戲 270

7.9.2 Sprague-Grundy定理 272

7.9.3 Nim游戲和Sprague-Grundy定理

 擴展 273

7.9.4 PN態分析 278

7.10 小結 282

第8章 數論 283

8.1 素數 283

8.1.1 素數判定 284

8.1.2 米勒-拉賓素性測試 285

8.1.3 高斯素數 287

8.1.4 生成素數序列 288

8.1.5 素因子分解 291

8.2 整除性 292

8.2.1 最大公約數 292

8.2.2 擴展歐幾里得算法 295

8.2.3 線性同餘方程 297

8.2.4 最小公倍數 298

8.2.5 歐拉函數 299

8.2.6 莫比烏斯函數 303

8.3 模算術 305

8.3.1 整數拆分 306

8.3.2 可樂兌換 306

8.3.3 模運算規則 306

8.3.4 模的逆元 307

8.3.5 離散對數 309

8.3.6 中國剩餘定理 310

8.3.7 波拉德ρ啟發式因子分解

 算法 311

8.4 日期和時間轉換 313

8.4.1 日期轉換 313

8.4.2 時間轉換 317

8.5 小結 318

第9章 幾何 319

9.1 點 319

9.2 直線 320

9.2.1 直線的表示 320

9.2.2 直線間關系 321

9.2.3 相互垂直的兩條直線交點 322

9.3 坐標和坐標系變換 322

9.3.1 平移 322

9.3.2 旋轉 323

9.3.3 縮放 325

9.4 三角形 329

9.4.1 勾股定理 329

9.4.2 三角函數 331

9.4.3 正弦定理 332

9.4.4 餘弦定理 332

9.4.5 三角形面積 334

9.4.6 三角函數庫 336

9.4.7 臺球碰撞問題 337

9.5 多邊形 339

9.5.1 矩形 339

9.5.2 四邊形和正多邊形 341

9.6 圓 341

9.6.1 圓的周長和麵積 342

9.6.2 圓的切線 343

9.6.3 三角形的內切圓與外接圓 345

9.6.4 圓與圓的位置關系 347

9.6.5 最小圓覆蓋 351

9.7 小結 352

第 10章 計算幾何 353

10.1 基本概念 353

10.1.1 線段 353

10.1.2 多邊形 353

10.2 幾何對象間的關系 354

10.2.1 向量、內積和外積 354

10.2.2 點和直線的關系 356

10.2.3 確定線段轉動方向 358

10.2.4 確定線段是否相交 359

10.2.5 點的投影 362

10.2.6 點的映像 364

10.2.7 點和直線間距離 364

10.2.8 點和線段間距離 365

10.2.9 線段和線段間距離 366

10.2.10 點和多邊形的關系 366

10.2.11 直線和圓的交點 369

10.2.12 圓和圓的交點 370

10.2.13 圓的切點 370

10.3 掃描線算法 371

10.4 坐標離散化 373

10.4.1 最大化矩形問題 376

10.4.2 矩形並的面積 377

10.4.3 矩形並的周長 379

10.5 凸包 383

10.5.1 Graham掃描法 383

10.5.2 Jarvis步進法 387

10.5.3 Andrew合並法 389

10.5.4 Melkman算法 391

10.6 公式及定理應用 392

10.6.1 Pick定理 392

10.6.2 多邊形面積 393

10.6.3 多邊形重心 393

10.6.4 三維幾何體的錶面積和體積 395

10.7 半平面交問題 396

10.7.1 凸多邊形切分 396

10.7.2 多邊形內核 401

10.8 最近點對問題 402

10.9 最遠點對問題 405

10.10 三維空間計算幾何 409

10.10.1 點 410

10.10.2 直線 411

10.10.3 平面 414

10.10.2 三維凸包 419

10.11 小結 423

附錄 425

1 ASCII表 425

2 C++運算符優先級 426

3 習題索引 426

參考資料 427