本书每章为一个主题,实验内容安排紧扣大学算法和数学的教学,用程序设计竞赛中的算法和数学试题作为实验试题,将算法和数学的教学与程序设计竞赛的解题训练结合在一起;在思维方式和解题策略的训练方面,以问题驱动和启发式引导为主要方式,培养读者通过编程解决问题的能力。
本书特点:
书中给出的234道试题全部精选自ACM国际大学生程序设计竞赛的世界总决赛以及各大洲赛区现场赛和网络预赛、大学程序设计竞赛、在线比赛和其他诸如IOI等程序设计竞赛题目,时间跨度为1989年到2010年,这些试题均能通过在线提交的方式进行实时检验,从而方便读者进行实验和练习。
本书提供了官方的原版试题、测试数据和解答程序作为参考,读者可以通过对官方的测试数据的分析,了解测试数据的特点和常见陷阱,在以后的编程中提高解题质量和正确性。
各章的实验范例可以用于大学算法课程的教学与实验,在此基础上使用题库进行解题,还可以辅导学生进行程序设计竞赛的专项训练。
本书提供了试题的英文原版描述和大部分试题的测试数据,读者可登录华章网站(http://www.hzbook.com)下载。
前言
第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
《绽放:第二十届新概念作文获奖者作品精选(A卷)》内容简介:本书精选2018年第20届全国新概念作文大赛一、二等奖获奖者的作品,结
《小学生必背常考古诗词(五年级)》内容简介:丛书收入小学一至六年级语文教材要求背诵学习的古诗词及经典的拓展阅读诗词,以年级
单片机原理与应用及C51程序设计-(第3版)-赠送电子课件 本书特色 mcs-51系列单片机应用广泛,是学习单片机技术较好的系统平台,同时也是单片微型计算机应用...
本书是一部为广大从事声频工程工作的读者提供准确、全面、简明的专业知识的工具书。该书的第三版全面更新了原有的内容,这部新版
HIGHLIGHTUpdatedfromtheclassicoriginal,TheQuickPythonBook,SecondEditionwillhelpw...
《1小时漫游量子世界》内容简介:我们所能感受到的世界,遵循着一套被称为宏观世界经典力学的规则;相对的,量子力学所研究的微观世
《吾心可鉴:跨文化沟通》内容简介:不同的文化在语言、习俗、文化心理等方面都有巨大的差异。本书从文化和心理学的双重视角,分全
《中国社会质量研究:理论、测量和政策》内容简介:近年来,国内逐渐兴起了对欧洲社会质量理论的讨论。本书在介绍欧洲社会质量理论
《脑机革命》内容简介:畅想一下,如果你能用大脑来控制电脑……比如在电脑屏上打字,或者是用意识操控机械臂完成各种动作……这些
《我也有过小时候》内容简介:在中国,任溶溶先生是一个无论大人还是孩子都喜欢的作者,他的许多作品包括译作滋养了几代人,任老先
《伊朗通史》内容简介:伊朗的历史传统源远流长,广袤的高原热土孕育了璀璨夺目的古代文明。公元前后,波斯帝国雄踞中东大地长达千
零基础学PHP+MySQL(附光盘) 本书特色 内容全面,讲解细致:讲解php与mysql的使用,还介绍html、xml等内容。由浅入深,循序渐进:采用循序渐进...
《Linux内核观测技术BPF》内容简介:本书是一本面向系统工程师的实践指南,皆在帮助他们获得Linux内核中BPF虚拟机的专业知识。通过
这是一本研究如何实现具有Web访问能力的网络机器人的书。该书从Internet编程的基本原理出发,深入浅出、循序渐进地阐述了网络机器
《珠宝首饰设计手册》内容简介:这是一本全面介绍珠宝首饰设计的图书,特点是知识易懂、案例趣味、动手实践、发散思维。本书从学习
本书是理论计算机科学方面的优秀教材,主要介绍形式语言、自动机、可计算性和相关内容。本书特别注意定义、定理的准确性和严格性
《软件自动化测试实战解析:基于Python3编程语言》内容简介:本书尽量用生活化的场景来描述编程场景,避免正确但是晦涩的表达,避免
《学习正则表达式》从正则表达式的基本概念讲起,到编写完整的sed和Perl脚本,再到转换HTML文件,将这种强大的工具解释得清晰透彻
《刑法案例研习教程(第二版)》内容简介:本书由韩玉胜主编,每章都有详细分析的案例若干,然后提供了若干个没有提供分析论证的探
射频功放非线性建模分析与预失真算法研究 本书特色 本书是著者及所带领团队近10年来在射频功放建模(包括神经Volterra级数建模,神经网络建模,X参数建模),...