ACM/ICPC程序设计与分析（C++实现）PDF|Epub|txt|kindle电子书版本网盘下载

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

习题18

第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

习题230

第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

习题344

第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

习题479

第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 Horse99

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

习题5117

第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

习题6154

第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

习题7181

第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

习题8211

第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

习题9257

第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

习题10305

第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

习题11341

第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

习题12375

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

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

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

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

参考文献397