第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