ACM/ICPC程序设计与分析（C++实现）PDF电子书下载

第1章 ACM国际大学生程序设计竞赛简介 1

1.1 ACM国际大学生程序设计竞赛概况 1

1.2 ACM国际大学生程序设计竞赛组织形式简介 1

1.2.1 组队方式和比赛形式 1

1.2.2 竞赛环境 2

1.2.3 判题结果 2

1.2.4 递交与评判 2

1.3 程序设计对学生的要求 3

1.4 程序设计语言选择 3

1.5 ACM程序设计竞赛题形式 5

习题1 8

第2章 程序设计基础 9

2.1 程序设计概述 9

2.2 算法基础 9

2.2.1 算法概述 9

2.2.2 算法复杂性 10

2.2.3 演绎方法的使用 10

2.2.4 演绎法算法设计举例 11

2.3 程序设计的输入输出形式 13

2.4 C＋＋文件操作 15

2.5 输入输出格式控制 19

2.5.1 流基类ios层次图 19

2.5.2 非格式化抽取 20

2.5.3 操纵算子 20

2.6 排序 23

2.6.1 冒泡排序 23

2.6.2 快速排序 24

2.7 简单应用 25

2.7.1 转换十六进制数 25

2.7.2 颠倒原文 26

2.7.3 指定个数的整数求和 27

2.7.4 不指定个数的整数求和 28

习题2 30

第3章 程序设计简单问题 32

3.1 ACM/ICPC程序设计竞赛的题型 32

3.2 简单例子 32

3.2.1 空格字符与非空格字符统计 32

3.2.2 荷兰国旗问题 34

3.2.3 城市间的球面距离 36

3.2.4 合并电话簿 39

3.2.5 图书排序问题 42

习题3 44

第4章 高精度计算与代数计算 50

4.1 高精度计算 50

4.1.1 基本知识 50

4.1.2 高精度数据的处理方法 50

4.1.3 高精度四则运算的基本处理方法 54

4.2 高精度四则运算应用 59

4.2.1 A+B问题 59

4.2.2 公牛和母牛 59

4.2.3 A—B问题 61

4.2.4 计算余数问题 62

4.3 代数计算 65

4.4 实例研究 70

4.4.1 指数函数值 70

4.4.2 是金还是银 71

4.4.3 p倍和子集问题 74

4.4.4 杨辉三角形 76

4.4.5 黑白棋游戏 77

习题4 79

第5章 数论中的程序设计 85

5.1 从跳兽问题谈起 85

5.2 最大公因数与最小公倍数 86

5.2.1 公因数和最大公因数的概念 86

5.2.2 最小公倍数 87

5.2.3 欧几里得算法 87

5.3 利用欧几里得算法求整系数一次不定方程ax+by=c的解 88

5.4 求解模线性方程 90

5.4.1 模和同余 90

5.4.2 模线性方程 91

5.5 求mod m的逆元素算法 92

5.6 模线性方程组与中国剩余定理 93

5.7 模幂运算与素数测试 95

5.7.1 模幂运算 95

5.7.2 素数测试 96

5.8 二次剩余与Pell方程 97

5.8.1 二次剩余 97

5.8.2 Pell方程 98

5.9 实例研究 99

5.9.1 Magic Horse 99

5.9.2 阶乘问题 101

5.9.3 邮票问题 102

5.9.4 Josephus问题 104

5.9.5 负数进制转换 107

5.9.6 数塔问题 109

5.9.7 幸运数 111

5.9.8 哥德巴赫猜想 114

习题5 117

第6章 组合数学中的程序设计 123

6.1 组合数学中有关概念与公式 123

6.1.1 排列与组合及有关的生成算法 123

6.1.2 母函数 129

6.1.3 容斥原理与错排 131

6.1.4 P？lya定理 132

6.2 实例研究 134

6.2.1 蛋糕 134

6.2.2 杨辉三角形中的奇偶问题 136

6.2.3 足球赛票 140

6.2.4 棋盘格数 141

6.2.5 保险柜上锁 142

6.2.6 弹球游戏 143

6.2.7 最少砝码 144

6.2.8 环 146

6.2.9 珍珠项链 147

6.2.10 统计棋局数 150

习题6 154

第7章 动态规划 160

7.1 动态规划原理 160

7.2 实例研究 161

7.2.1 游船费问题 161

7.2.2 航线设置 164

7.2.3 复制书稿 166

7.2.4 括号序列 168

7.2.5 整数匹配问题 171

7.2.6 生日蛋糕 174

7.2.7 乘积最大 175

7.2.8 多边形计算 177

习题7 181

第8章 计算几何学 186

8.1 几何基本知识 186

8.1.1 矢量的概念 186

8.1.2 矢量加减法 186

8.1.3 矢量叉积 187

8.1.4 折线段的拐向判断 187

8.1.5 判断点是否在线段上 188

8.1.6 跨立试验与判断两线段是否相交 188

8.1.7 整数点与Pick定理 189

8.2 基本算法 190

8.3 凸包 193

8.3.1 凸包的概念与实例 193

8.3.2 Graham扫描法 194

8.3.3 Jarvis步进法 195

8.3.4 Graham扫描法与Jarvis步进法的程序实现 195

8.4 实例研究 200

8.4.1 有缺陷的卫星 200

8.4.2 篱笆 202

8.4.3 处于危险之中的飞行员 205

8.4.4 穿街走巷 206

8.4.5 三角形 209

习题8 211

第9章 搜索算法 216

9.1 广度优先搜索 216

9.1.1 广度优先搜索思想 216

9.1.2 广度优先搜索算法框架 217

9.1.3 广度优先搜索算法实现过程 217

9.2 深度优先搜索 218

9.2.1 深度优先搜索思想 218

9.2.2 深度优先搜索算法实现过程 218

9.2.3 子集树问题和排列树问题——DFS算法框架 219

9.3 双向广度优先算法 220

9.3.1 双向广度搜索的概念 220

9.3.2 双向广度搜索算法 221

9.4 A*算法 223

9.4.1 A*算法概述 223

9.4.2 A*算法框架 224

9.5 实例研究 225

9.5.1 数的划分 225

9.5.2 通信团体 226

9.5.3 惹事的青蛙 229

9.5.4 子集和问题 232

9.5.5 相异数字序列问题 235

9.5.6 方圆迷宫游戏 241

9.5.7 开关网络 245

9.5.8 油田 250

9.5.9 八数码问题 252

习题9 257

第10章 一般图论中的程序设计 265

10.1 图论算法基础 265

10.1.1 连通性 265

10.1.2 最小生成树 270

10.1.3 最短路径 274

10.1.4 有向图的传递闭包 278

10.1.5 回路问题 278

10.1.6 Bellman-Ford算法与负权回路 279

10.1.7 第n最短路径问题 279

10.2 实例研究 280

10.2.1 无向图的连通分支 280

10.2.2 兵家必争之地 281

10.2.3 交通要道 284

10.2.4 有向图的强连通分支 286

10.2.5 师生树 289

10.2.6 股票经纪人谣言传播 291

10.2.7 丛林小路 294

10.2.8 多边形游戏 297

10.2.9 救火车 299

10.2.10 游戏 302

10.2.11 酒厂选址 303

习题10 305

第11章 网络流与二分图 313

11.1 网络与流 314

11.1.1 网络流基本概念 314

11.1.2 增广路算法 315

11.1.3 求最大流的标号法——Ford-Fulkerson方法 317

11.2 二分图匹配 318

11.2.1 问题 318

11.2.2 二分图与匹配 318

11.2.3 二分图最大匹配问题网络流算法 319

11.2.4 二分图最大匹配问题的匈牙利算法 319

11.2.5 最小点覆盖与最小路径覆盖 322

11.2.6 二分图最优匹配 324

11.3 实例研究 326

11.3.1 物流运输问题 326

11.3.2 电力网络 328

11.3.3 课程 330

11.3.4 小行星 332

11.3.5 男生和女生 334

11.3.6 最小路径覆盖 336

11.3.7 运动员最佳匹配 338

习题11 341

第12章 杂例 349

12.1 常用的有关算法 349

12.2 实例研究 350

12.2.1 方圆游戏 350

12.2.2 删数游戏 351

12.2.3 雷达安装 353

12.2.4 友好数 356

12.2.5 移动火柴 357

12.2.6 逆波兰式 359

12.2.7 分型 360

12.2.8 手机菜单 363

12.2.9 多项式构造问题 364

12.2.10 Petri网络模拟 366

12.2.11 奇异的结构 370

习题12 375

附录A 程序设计竞赛过程和PC2竞赛系统使用 383

附录B 八数码问题的C＋＋语言实现程序 386

B1 双向广度优先算法求解八数码问题的程序 386

B2 八数码问题的A*算法C＋＋语言实现程序 391

参考文献 397