本书针对ACM程序竞赛出现比较多的16尽厚个方面的问题，通过案例的方式说明解决问题的方法。由于数据结构使用非常多，对不属于16个专门问题的知识我们也进行了介绍。 本书不是这些专门问题的教科书，所以对这些问题所涉及知识的介绍来自不多，主要是分析一个案例，介绍专属于ACM把钢资程序设计的方法和技巧。

• 书名 ACM程序设计培训教程
• 作者 吴昊
• ISBN 9787113076511
• 页数 269

基本信息

　　作者: 吴昊

　　ISBN: 9787113076511

　　页数: 269

　　定价: 28.00

　　出版社: 中国铁道

　　装帧: 平装

　　出版年: 2007年8月1日

图书目录

　　第1章 经典数据结构与算法……………………………………………………………1

　　1.1 线性表………………………………………………………………………………1

　　1.1.1 线性来自表的顺序存储结构……………………………………360百科………………1

　　倍王附饭层查1.1.2 插入操作……………………………………………………………………2

　　1.1微变钢则火天元他.3 删除操作……………………………………………………………………2

　　1.1.4 线性表的链式都验却因报护只派迅诗存储…………………………………………………………2

到蛋呼　　1.1.5 单链表………………………………………………………………………2

　　1.1.6 单链表的插入操作…………………………………………………………3

　　1.刘儿取露满那太换久1.7 单链表的删除操作…………………………………………………………3

　　1.1.8 循环链表…………………………庆现紧北翻反车周…………………………………………4

　　1.1.9 双向链表…………………书边办…………………………………息内色香木构………………5

　　1.1.10 双向链表的插入操作………………………齐轻包饭置室族破来质………………………………5

　　1.1.11 双向差通厚敌帮让处女管早客链表的删除操作……………………………………………联翻宣酸技普处概后唱…………5

　　1.1.12 静态链表……………东………………………………………………………5

　　1.2 栈………………………………………………………………………………………………5

　　1.2.1 顺序栈……………………………………一…………………………………6

　　1.2.2 链栈……………………………………………………………………首正下回里办从请光策………………………………9

　　l.3 队列…………………………………………………………………………………………10

　　1.3.1 链队列………………………………………………………………………10

　　1.3.2 循环队列……………………………………………………………………12

　　1.4 串的定义……………………………………………………………………………13

　　1.5 抽象数据类型串的实现……………………………………………………………14

　　1.5.1 定长顺序串…………………………………………………………………14

　　1.5.2 堆串…判垂食密金到映皮……………………………………………………………………………18

　　1.5.3 块链串……………………才茶静界建银氧型制代…………………………………………………24

　　1.6 查找的基本概念……………………溶两剂………………………………………………24

　　1.6.1 顺多方粮知席序查找法…………………………………………………………………25

　　1.6.2 折半查找法…………………………………………………………………26

　　1.制把太创6.3 分块查找法…………………………………………………………………27

　　1.6.4 基于树的查找法……………………………………………………………28

　　1.6.5 计算式查找法--哈希法…………………………………………………28

　　1.7 排序的基本概念……………………………………………………………………33

　　1.7.1 插入类排序…………………………………………………………………34

　　1.7.2 直接插入排序………………………………………………………………34

　　1.7.3 折半插入排序………………………………………………………………35

　　1.7.4 表插入排序…………………………………………………………………36

　　1.7.5 冒泡排序……………………………………………………………………39

　　1.7.6 快速排序……………………………………………………………………40

　　1.8 分配类排序…………………………………………………………………………41

　　1.8.1 多关键字排序………………………………………………………………42

　　1.8.2 链式基数排序………………………………………………………………42

　　1.8.3 基数排序的顺序表结构……………………………………………………45

　　1.8.4 各种排序方法的综合比较…………………………………………………46

　　第2章 蛮力法………………………………………………………………………47

　　2.1搜索所有的解空间…………………………………………………………………47

　　〖案例l〗假金币…………………………………………………………………47

　　〖案例2〗现在的时间是多少……………………………………………………49

　　2.2 搜索所有的路径……………………………………………………………………52

　　〖案例3〗矩阵……………………………………………………………………52

　　2.3 直接计算……………………………………………………………………………54

　　〖案例4〗数的长度………………………………………………………………54

　　2.4 模拟与仿真…………………………………………………………………………56

　　〖案例5〗冲撞的机器人…………………………………………………………56

　　第3章 贪心算法………………………………………………………………………61

　　3.1 构造法………………………………………………………………………………61

　　〖案例1〗订票……………………………………………………………………6I

　　3.2 反证法………………………………………………………………………………67

　　〖案例2〗电梯……………………………………………………………………68

　　3.3 调整法………………………………………………………………………………70

　　〖案例3〗水位……………………………………………………………………70

　　〖案例4〗埃及分数………………………………………………………………73

　　〖案例5〗数划分的研究…………………………………………………………74

　　第4章 背包问题………………………………………………………………………78

　　4.1 用贪心法解决背包问题……………………………………………………………78

　　〖案例1〗最佳装载………………………………………………………………78

　　4.2 回溯法解决背包问题………………………………………………………………81

　　〖案例2〗0/1背包…………………………………………………………………81

　　4.3 遗传算法解决背包问题……………………………………………………………86

　　〖案例3〗0/1背包……………………………………………………………86

　　4.4 动态规划解决背包问题……………………………………………………………94

　　〖案例4〗适配背包………………………………………………………………94

　　第5章回溯法………………………………………………………………………97

　　5.1 组合与数的问题……………………………………………………………………97

　　〖案例l〗组合问题………………………………………………………………97

　　〖案例2〗数的划分………………………………………………………………99

　　5.2 回溯法与搜索……………………………………………………………………101

　　〖案例3〗素数填表问题…………………………………………………………101

　　〖案例4〗八皇后问题……………………………………………………………105

　　第6章 动态规划……………………………………………………………………109

　　6.1 最优子结构………………………………………………………………………1 1 1

　　〖案例1〗拦截导弹………………………………………………………………1ll

　　6.2 应用动态规划的步骤……………………………………………………………113

　　〖案例2〗公共子序列……………………………………………………………113

　　〖案例3〗Uxuhul的表决…………………………………………………………115

　　第7章 DFS与BFS以及剪枝问题……………………………………………………119

　　7.1 深度优先遍历……………………………………………………………………119

　　〖案例l〗15数码难题……………………………………………………………120

　　〖案例2〗三角形大战……………………………………………………………121

　　7.2 宽度优先遍历……………………………………………………………………122

　　〖案例3〗蛇和梯子………………………………………………………………123

　　7.3 剪枝方法…………………………………………………………………………127

　　第8章 线性规划和整数规划…………………………………………………………129

　　8.1 简单线性规划……………………………………………………………………129

　　〖案例l〗炼金术…………………………………………………………………129

　　8.2 整数规划…………………………………………………………………………134

　　〖案例2〗装箱问题………………………………………………………………134

　　第9章 最小生成树…………………………………………………………………139

　　9.1 Prim算法…………………………………………………………………………………………………140

　　9.2 Kruskal算法………………………………………………………………………………………………143

　　9.3 Sollin算法…………………………………………………………………………………………………145

　　第10章 大数问题……………………………………………………………………146

　　10.1 大数的加减………………………………………………………………………146

　　〖案例1〗整数探究………………………………………………………………146

　　10.2 大数的乘积……………………………………………………………………148

　　〖案例2〗相连游戏………………………………………………………………148

　　〖案例3〗公牛的数学……………………………………………………………150

　　10.3 用FFT作大数乘法………………………………………………………………151

　　〖案例4〗X问题…………………………………………………………………152

　　10.4 任意精度计算……………………………………………………………………155

　　〖案例5〗幂……………………………………………………………………155

　　10.5 大数的除法………………………………………………………………………157

　　第11章 计算几何学…………………………………………………………………158

　　11.1 判断点是否在多边形中…………………………………………………………158

　　11.2 判断线段是否在多边形内………………………………………………………159

　　11.3 计算几何典型算法………………………………………………………………160

　　〖案例1〗计算周长问题…………………………………………………………161

　　〖案例2〗正方形问题……………………………………………………………162

　　〖案例3〗计算平面点集凸壳的算法……………………………………………163

　　第12章 着色问题与排队论……………………………………………………………167

　　12.1 着色问题…………………………………………………………………………168

　　12.1.1 顶点着色问题……………………………………………………………168

　　12.1.2 边着色问题………………………………………………………………177

　　12.2 排队论……………………………………………………………………………………………………179

　　第13章 组合数学……………………………………………………………………188

　　13.1 鸽巢原理…………………………………………………………………………188

　　13.2 容斥原理…………………………………………………………………………190

　　〖案例1〗棋盘覆盖问题…………………………………………………………192

　　〖案例2〗被毁坏的玉米地(Crop Circles)问题………………………………193

　　13.3 递推关系…………………………………………………………………………197

　　〖案例3〗Josephus问题…………………………………………………………197

　　〖案例4〗假币问题………………………………………………………………199

　　13.4 发生函数…………………………………………………………………………202

　　13.5 Polya定理………………………………………………………………………………………………204

　　第14章 概率论…………………………………………………………………………206

　　14.1 基本概念…………………………………………………………………………206

　　14.2 基本概率算法……………………………………………………………………208

　　〖案例1〗快速排序………………………………………………………………209

　　〖案例2〗八皇后问题……………………………………………………………210

　　14.3 蒙特卡罗(Monte Carlo)型概率算法…………………………………………214

　　第15章 凸包问题……………………………………………………………………217

　　15.1 穷举法解决凸包问题……………………………………………………………217

　　15.2 格雷厄姆扫描法解决凸包问题…………………………………………………218

　　15.3 分治法解决凸包问题……………………………………………………………220

　　15.4 蛮力法解决凸包问题……………………………………………………………222

　　15.5 Jarris步进法解决凸包问题………………………………………………………224

　　15.6 应用…………………………………………………………………………………………………………227

　　〖案例l〗果园篱笆………………………………………………………………227

　　〖案例2〗巨人和鬼………………………………………………………………232

　　第16章 数论问题……………………………………………………………………236

　　16.1 数的幂运算………………………………………………………………………236

　　〖案例l〗高级模运算……………………………………………………………236

　　16.2 欧拉定理的应用…………………………………………………………………238

　　〖案例2〗快乐2004……………………………………………………………239

　　〖案例3〗2x mod n=1……………………………………………………………240

　　16.3 素数测试…………………………………………………………………………243

　　〖案例4〗素数距离………………………………………………………………243

　　〖案例5〗素数测试………………………………………………………………246

　　16.4 Pell方程…………………………………………………………………………………………………250

　　〖案例6〗Smith问题……………………………………………………………250

　　附录A 排课时间表问题源代码………………………………………………………258

　　参考文献………………………………………………………………………………269