本书从ACM-ICPC程序设计竞赛等各种程序设计竞赛的试题进行了分析和整理,并精选出典型试题进行分类解析,既可用于高校算法、程序设计课程的实验和教学,也可以用于竞赛选手的系统训练。
封面图
目录
- 前言
- 第1章求解Ad Hoc类问题的编程实验 1
- 1.1机理分析法的实验范例 1
- 1.2统计分析法的实验范例 5
- 1.3相关题库 9
- 第2章模拟法的编程实验 31
- 2.1直叙式模拟的实验范例 31
- 2.2筛选法模拟的实验范例 46
- 2.3构造法模拟的实验范例 56
- 2.4相关题库 60
- 第3章数论的编程实验 72
- 3.1素数运算的实验范例 72
- 3.1.1使用筛法生成素数 72
- 3.1.2测试大素数 79
- 3.2求解不定方程和同余的实验范例 82
- 3.2.1计算最大公约数和不定方程 82
- 3.2.2计算同余方程和同余方程组 89
- 3.2.3计算多项式同余方程 99
- 3.3特殊的同余式的实验范例 102
- 3.3.1威尔逊定理和费马小定理 102
- 3.3.2伪素数 105
- 3.3.3欧拉定理 112
- 3.4积性函数的实验范例 116
- 3.4.1欧拉φ函数φ(n) 116
- 3.4.2莫比乌斯函数μ(n) 121
- 3.4.3完全数和梅森素数 124
- 3.5高斯素数的实验范例 129
- 3.6相关题库 135
- 第4章组合分析的编程实验 152
- 4.1生成排列的实验范例 152
- 4.1.1按字典序思想生成下一个排列 152
- 4.1.2按字典序思想生成所有排列 154
- 4.2排列组合计数的实验范例 156
- 4.2.1一般的排列组合计数公式 156
- 4.2.2两种特殊的排列组合计数公式 167
- 4.2.3多重集的排列数和组合数 174
- 4.3鸽笼原理与容斥原理的实验范例 178
- 4.3.1利用鸽笼原理求解存在性问题 178
- 4.3.2容斥原理应用实验 180
- 4.3.3Ramsey定理的应用 188
- 4.4Pólya计数公式的实验范例 190
- 4.5生成函数与递推关系的实验范例 201
- 4.5.1幂级数型生成函数 201
- 4.5.2指数型生成函数 204
- 4.5.3递推关系 207
- 4.6快速傅里叶变换的实验范例 211
- 4.7相关题库 216
- 第5章贪心法的编程实验 229
- 5.1体验贪心法内涵的实验范例 229
- 5.1.1贪心法的经典问题 229
- 5.1.2体验贪心法内涵 236
- 5.2利用数据有序化进行贪心选择的实验范例 241
- 5.3在综合性的P类问题中使用贪心法的实验范例 249
- 5.4相关题库 255
- 第6章动态规划方法的编程实验 265
- 6.1线性DP的实验范例 266
- 6.1.1初步体验线性DP问题 266
- 6.1.2子集和问题 270
- 6.1.3最长公共子序列问题 271
- 6.1.4最长递增子序列问题 273
- 6.20-1背包问题 280
- 6.2.1基本的0-1背包问题 280
- 6.2.2完全背包 281
- 6.2.3多重背包 285
- 6.2.4混合背包 287
- 6.2.5二维背包 292
- 6.2.6分组背包 294
- 6.2.7有依赖的背包 298
- 6.3树形DP的实验范例 300
- 6.4状态压缩DP的实验范例 305
- 6.5单调优化1D/1D DP的实验范例 309
- 6.5.1经典模型1:利用决策代价函数w的单调性优化 310
- 6.5.2经典模型2:利用决策区间下界的单调性优化 313
- 6.5.3经典模型3:利用最优决策点的凸性优化 318
- 6.6相关题库 322
- 第7章高级数据结构的编程实验 353
- 7.1后缀数组的实验范例 353
- 7.1.1使用倍增算法计算名次数组和后缀数组 353
- 7.1.2计算最长公共前缀 356
- 7.1.3后缀数组的应用 357
- 7.2线段树的实验范例 370
- 7.2.1线段树的基本概念和基本操作 370
- 7.2.2线段树单点更新的维护 372
- 7.2.3线段树子区间更新的维护 375
- 7.3处理特殊图的实验范例 387
- 7.3.1计算欧拉图 387
- 7.3.2计算哈密顿图 393
- 7.3.3计算最大独立集 402
- 7.3.4计算割点、桥和双连通分支 406
- 7.4相关题库 414
- 第8章计算几何的编程实验 433
- 8.1点线面运算的实验范例 433
- 8.1.1计算点积和叉积 433
- 8.1.2计算线段交 440
- 8.1.3利用欧拉公式计算多面体 449
- 8.2利用扫描线算法计算矩形的并的面积的实验范例 453
- 8.2.1沿垂直方向计算矩形的并面积 453
- 8.2.2沿水平方向计算矩形的并面积 457
- 8.3计算半平面交的实验范例 460
- 8.3.1计算半平面交的联机算法 461
- 8.3.2利用极角计算半平面交的算法 466
- 8.4计算凸包和旋转卡壳的实验范例 474
- 8.4.1计算凸包 474
- 8.4.2旋转卡壳实验 479
- 8.5相关题库 482