基本介紹
- 中文名：ACM-ICPC基本算法
- 作者：滕國文、李昊
- 出版社：清華大學出版社
- 出版時間：2018年9月
- 定價：39 元
- ISBN：9787302503132
內容簡介,圖書目錄,
內容簡介
《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
