ACM-ICPC 基本算法

滕國文、李昊

  • 出版商: 清華大學
  • 出版日期: 2018-09-01
  • 定價: $234
  • 售價: 8.5$199
  • 語言: 簡體中文
  • ISBN: 7302503133
  • ISBN-13: 9787302503132

下單後立即進貨 (約4週~6週)

  • ACM-ICPC 基本算法-preview-1
  • ACM-ICPC 基本算法-preview-2
  • ACM-ICPC 基本算法-preview-3
ACM-ICPC 基本算法-preview-1

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

相關主題

商品描述

《ACM-ICPC基本算法》簡要介紹了ACM-ICPC(ACM國際大學生程序設計競賽)、算法和算法設計的基礎知識,重點講解算法設計方法,給出了ACM-ICPC中常用的10種算法設計方法:求值法、遞推法、遞歸法、枚舉法、模擬法、分治法、貪心法、回溯法、構造法和動態規劃法。本書針對每種程序設計方法,首先闡述該方法的基本思想,然後通過典型例題進行詳細講解,最後通過實戰訓練予以鞏固和提高。   本書註重ACM-ICPC的基本算法,思想高度概括、例題深入淺出、實戰耐人尋味。本書可作為ACM國際大學生程序設計競賽和中學青少年信息學奧林匹克競賽的指導書,也可作為IT技術人員和電腦編程愛好者的參考書。

目錄大綱

  目  錄

  

  

  

  

 

第1章  ACM與算法概述 1

1.1  ACM-ICPC簡介 1

1.1.1  歷史 1

1.1.2  比賽規則 2

1.1.3  區域和全球決賽 2

1.2  算法與問題求解 2

1.2.1  算法的定義 3

1.2.2  問題求解 3

1.3  算法的特性 5

1.3.1  算法的要素 5

1.3.2  算法的基本特性 6

1.4  算法的描述 6

1.4.1  基本控制結構的描述 7

1.4.2  C算法描述的約定 9

1.5  算法分析 11

1.5.1  算法的評價標準 11

1.5.2  算法的時間復雜性 12

1.5.3  算法的空間復雜性 13

1.6  算法的優化 14

1.6.1  全局優化 14

1.6.2  局部優化 15

1.6.3  算法優化中的註意事項 16

第2章  求值法 18

2.1  算法設計思想 18

2.2  典型例題 18

2.2.1  求最大數 18

2.2.2  中位數和平均數 19

2.2.3  判斷閏年 20

2.2.4  素數 21

2.2.5  判斷天數 23

2.2.6  大整數階乘 24

2.3  實戰訓練 25

2.3.1  求年長者 25

2.3.2  一元二次方程求根 26

2.3.3  三角形的面積 26

2.3.4  最大公約數 26

2.3.5  求整數的位數 27

2.3.6  孿生素數 27

2.3.7  求圓的周長 27

2.3.8  階乘求和 28

2.3.9  計算圓周率 28

2.3.10  求閏年 29

2.3.11  連續自然數的平方和 29

2.3.12  大整數求和問題 29

2.3.13  公牛和母牛 30

2.3.14  十六進制的運算 30

2.3.15  親和數 31

2.4  小結 31

第3章  遞推法 32

3.1  算法設計思想 32

3.2  典型例題 33

3.2.1  兔子繁殖問題 33

3.2.2  最大公約數問題 34

3.2.3  猴子吃桃問題 35

3.2.4  楊輝三角問題 36

3.2.5  穿越沙漠問題 37

3.2.6  方格塗色問題 39

3.3  實戰訓練 40

3.3.1  求年齡 40

3.3.2  斐波那契數列求和 40

3.3.3  絕不後退 41

3.3.4  取數 41

3.3.5  王小二的刀 41

3.3.6  蜜蜂回家 42

3.3.7  富二代的生活費 42

3.3.8  平面分割問題 43

3.3.9  特殊性質的數 43

3.3.10  求天數 44

3.3.11  上樓梯 44

3.3.12  開獎 44

3.3.13  月之數 45

3.3.14  洗牌 45

3.3.15  飛躍懸崖 46

3.4  小結 46

第4章  遞歸法 47

4.1  算法設計思想 47

4.2  典型例題 47

4.2.1  母牛繁殖問題 47

4.2.2  輸出各位數字 48

4.2.3  最大值問題 49

4.2.4  計算x的n次冪 51

4.2.5  數組逆置 52

4.2.6  漢諾塔問題 53

4.3  實戰訓練 54

4.3.1  遞歸取數 54

4.3.2  遞歸拆數 55

4.3.3  求素數之積 55

4.3.4  反轉字符串 56

4.3.5  公共子序列 56

4.3.6  賣鴨子 56

4.3.7  進制轉換 57

4.3.8  角谷定理 57

4.3.9  楊輝三角 58

4.3.10  質因數分解 58

4.3.11  全排列 58

4.3.12  特殊性質的數 59

4.3.13  放盤子 59

4.3.14  無序劃分 60

4.3.15  迴文數 60

4.4  小結 60

第5章  枚舉法 62

5.1  算法設計思想 62

5.2  典型例題 62

5.2.1  百雞問題 62

5.2.2  水仙花數 63

5.2.3  完數 64

5.2.4  可逆素數 65

5.2.5  串匹配問題 67

5.2.6  最小公倍數問題 69

5.2.7  獄吏問題 71

5.3  實戰訓練 72

5.3.1  素數篩選問題 72

5.3.2  紙幣換硬幣 73

5.3.3  勾股數問題 73

5.3.4  生理周期問題 73

5.3.5  構造比例數 74

5.3.6  自守數 75

5.3.7  誰是竊賊 75

5.3.8  獨特的數 76

5.3.9  握手問題 76

5.3.10  趣味數學 77

5.3.11  暴力枚舉之絕對值 77

5.3.12  迴文數 78

5.3.13  逆序對數 79

5.3.14  放牧 79

5.3.15  餐廳點餐 80

5.4  小結 81

第6章  模擬法 82

6.1  算法設計思想 82

6.2  典型例題 82

6.2.1  電梯問題 82

6.2.2  撲克洗牌問題 83

6.2.3  進站時間模擬 85

6.2.4  消息隊列 86

6.2.5  清除雜草 89

6.2.6  機器人的指令 92

6.3  實戰訓練 93

6.3.1  報數問題 93

6.3.2  無限次冪 94

6.3.3  金幣工資 95

6.3.4  進制轉換 95

6.3.5  卡片魔術 96

6.3.6  木棍上的螞蟻 96

6.3.7  串聯數字 97

6.3.8  多連塊覆蓋問題 98

6.3.9  括號表達式 99

6.3.10  假幣問題 100

6.3.11  會議安排 101

6.3.12  取火柴游戲 102

6.3.13  取石子游戲 103

6.3.14  偽造的美元 103

6.3.15  HTML瀏覽器 104

6.4  小結 105

第7章  分治法 106

7.1  算法設計思想 106

7.2  典型例題 106

7.2.1  折半查找 106

7.2.2  金塊問題 108

7.2.3  尋找第二的問題 110

7.2.4  歸並排序 112

7.2.5  大整數乘法 114

7.2.6  二叉樹遍歷 115

7.3  實戰訓練 118

7.3.1  數組二分求和 118

7.3.2  子序列最大值 118

7.3.3  棋盤覆蓋 118

7.3.4  最接近點對問題 120

7.3.5  第k小元素問題 120

7.3.6  循環賽日程表問題 121

7.3.7  找假幣問題 121

7.3.8  n階分形 122

7.3.9  m叉樹問題 122

7.3.10  電話查重 123

7.3.11  樹的有效點對 124

7.3.12  迴文串交換 125

7.3.13  史密斯數 125

7.3.14  矩陣乘積 126

7.3.15  士兵排隊問題 126

7.4  小結 127

第8章  貪心法 128

8.1  算法設計思想 128

8.2  典型例題 129

8.2.1  找零錢問題 129

8.2.2  最優裝載 130

8.2.3  哈夫曼編碼 132

8.2.4  單源最短路徑 136

8.2.5  埃及分數問題 139

8.2.6  多機調度問題 141

8.3  實戰訓練 144

8.3.1  小船過河問題 144

8.3.2  紀念品分組 144

8.3.3  數列極差問題 145

8.3.4  函數求底問題 145

8.3.5  開心的金明 146

8.3.6  小明坐車問題 147

8.3.7  田忌賽馬 147

8.3.8  裝箱問題 148

8.3.9  刪數問題 148

8.3.10  移動紙牌問題 149

8.3.11  組合正整數 149

8.3.12  活動安排問題 150

8.3.13  多人接水問題1 150

8.3.14  多人接水問題2 151

8.3.15  搬桌子問題 151

8.4  小結 152

第9章  回溯法 153

9.1  算法設計思想 153

9.2  典型例題 153

9.2.1  八皇後問題 153

9.2.2  圖著色問題 155

9.2.3  橋本分數式 158

9.2.4  高逐位整除數 160

9.2.5  直尺刻度分佈問題 162

9.2.6  素數環問題 164

9.2.7  伯努利裝錯信封問題 167

9.3  實戰訓練 169

9.3.1  排列問題 169

9.3.2  低逐位整除數 169

9.3.3  子集問題 170

9.3.4  旅行售貨員問題 170

9.3.5  兩組均分問題 171

9.3.6  組合數問題 171

9.3.7  運動員最佳配對問題 172

9.3.8  任務最佳調度問題 172

9.3.9  迷宮問題 173

9.3.10  背包問題 174

9.3.11  翻幣問題 174

9.3.12  最長滑雪問題 175

9.3.13  流水線作業調度問題 175

9.3.14  組合三角形問題 176

9.3.15  情侶排列問題 176

9.4  小結 177

第10章  構造法 178

10.1  算法設計思想 178

10.2  典型例題 179

10.2.1  計算π值 179

10.2.2  求n的階乘 180

10.2.3  求第k大的數 181

10.2.4  比賽日程表 183

10.2.5  奇數階魔方 185

10.2.6  二叉樹操作 187

10.3  實戰訓練 189

10.3.1  自然數倒數求和 189

10.3.2  今夕是何日 189

10.3.3  計算e值 190

10.3.4  自數 190

10.3.5  火星人 191

10.3.6  整數平方後9位 192

10.3.7  構造等式 192

10.3.8  構造迴文字符串 192

10.3.9  開燈問題 193

10.3.10  “1”的個數 193

10.3.11  小明的煩惱 194

10.3.12  乒乓球賽 194

10.3.13  自然數拆分問題 195

10.3.14  集卡片贏大獎 195

10.3.15  括號匹配問題 196

10.4  小結 196

第11章  動態規劃法 198

11.1  算法設計思想 198

11.2  典型例題 199

11.2.1  數塔問題 199

11.2.2  矩陣連乘問題 201

11.2.3  最長公共子序列問題 205

11.2.4  最長上升子序列問題 207

11.2.5  陪審團問題 209

11.3  實戰訓練 212

11.3.1  最少硬幣問題 212

11.3.2  編輯距離問題 213

11.3.3  石子合並問題 213

11.3.4  最小m段和問題 214

11.3.5  最大長方體問題 214

11.3.6  最大k乘積問題 215

11.3.7  最少費用購物問題 215

11.3.8  最優時間表問題 216

11.3.9  矩形嵌套問題 217

11.3.10  導彈攔截問題 218

11.3.11  C小加問題 218

11.3.12  完全背包問題 219

11.3.13  分郵票問題 220

11.3.14  排列問題 220

11.3.15  完全覆蓋問題 221

11.4  小結 221

參考文獻 223