本书每章为一个主题,实验内容安排紧扣大学算法和数学的教学,用程序设计竞赛中的算法和数学试题作为实验试题,将算法和数学的教学和程序设计竞赛的解题训练结合在了一起;其次,本书中二百道试题均能通过在线提交的方式进行裁判,使得实验和练习能方便地进行;再次,本书提供了官方的原版试题、测试数据和解答程序作为参考,读者可以通过对官方的测试数据的分析,了解测试数据的特点和常见陷阱,在以后的编程中提高解题质量和正确性。
本书可以作为大专院校计算机专业算法课程教材,也可以作为计算机专业学生的研修资料和程序设计竞赛的培训教材。
封面图
目录
- 前言
- 第1章求解Ad Hoc类问题的编程实验1
- 1.1机理分析法的实验范例1
- 1.2统计分析法的实验范例5
- 1.3相关题库10
- 第2章模拟法的编程实验35
- 2.1直叙式模拟的实验范例36
- 2.2筛选法模拟的实验范例44
- 2.3构造法模拟的实验范例51
- 2.4相关题库55
- 第3章数论的编程实验69
- 3.1素数运算的实验范例69
- 3.1.1使用筛法生成素数的实验范例69
- 3.1.2测试大素数的实验范例76
- 3.2求解不定方程和同余方程的实验范例81
- 3.2.1计算最大公约数和不定方程81
- 3.2.2计算同余方程和同余方程组85
- 3.3积性函数的实验范例91
- 3.3.1使用欧拉函数φ(n)计算与n互质的正整数个数 92
- 3.3.2使用莫比乌斯函数μ(n)计算非平方数n的质因子个数97
- 3.4相关题库102
- 第4章组合分析的编程实验118
- 4.1生成排列组合的实验范例118
- 4.1.1按字典序思想生成下一排列组合118
- 4.1.2按字典序思想生成所有的排列组合121
- 4.2排列组合计数的实验范例122
- 4.2.1一般的排列组合计数公式123
- 4.2.2两种特殊的排列组合计数公式126
- 4.3容斥原理与抽屉原理的实验范例132
- 4.3.1利用抽屉原理求解存在性问题132
- 4.3.2利用容斥原理对并集计数134
- 4.4波利亚定理的实验范例140
- 4.4.1波利亚定理的概念基础141
- 4.4.2利用波利亚定理计算集合在置换群作用下产生的等价类个数148
- 4.5相关题库157
- 第5章贪心法的编程实验165
- 5.1体验贪心法内涵的实验范例165
- 5.2利用数据有序化进行贪心选择的实验范例172
- 5.3在综合性的P类问题中使用贪心法的实验范例181
- 5.4相关题库187
- 第6章动态规划(DP)方法的编程实验197
- 6.1线性DP的实验范例198
- 6.1.1初步体验线性DP问题198
- 6.1.2子集和问题202
- 6.1.3最长公共子序列问题203
- 6.1.4最长递增子序列问题206
- 6.2树形DP的实验范例213
- 6.3状态压缩DP的实验范例218
- 6.4单调优化1D/1D DP的实验范例224
- 6.4.1经典模型1:利用决策代价函数w的单调性优化224
- 6.4.2经典模型2:利用决策区间下界的单调性优化228
- 6.4.3经典模型3:利用最优决策点的凸性优化233
- 6.5相关题库236
- 第7章高级数据结构的编程实验273
- 7.1后缀数组的实验范例273
- 7.1.1使用倍增算法计算名次数组和后缀数组273
- 7.1.2计算最长公共前缀276
- 7.1.3后缀数组的应用278
- 7.2线段树的实验范例288
- 7.2.1线段树的基本概念和基本操作288
- 7.2.2线段树单点更新的维护290
- 7.2.3线段树子区间更新的维护293
- 7.3处理特殊图的实验范例306
- 7.3.1计算欧拉图306
- 7.3.2计算哈密尔顿图314
- 7.3.3计算最大独立集324
- 7.3.4计算割点、桥和双连通分支327
- 7.4相关题库336
- 第8章计算几何的编程实验354
- 8.1点线面运算的实验范例354
- 8.1.1计算点积和叉积354
- 8.1.2计算线段交361
- 8.1.3利用欧拉公式计算多面体371
- 8.2利用扫描线算法计算矩形的面积并375
- 8.2.1沿垂直方向计算矩形的面积并375
- 8.2.2沿水平方向计算矩形的面积并380
- 8.3计算半平面交的实验范例383
- 8.3.1计算半平面交的联机算法384
- 8.3.2利用极角计算半平面交的算法390
- 8.4计算凸包和旋转卡壳的实验范例398
- 8.4.1计算凸包399
- 8.4.2旋转卡壳实验403
- 8.5相关题库408