本书每章为一个主题，实验内容安排紧扣大学算法和数学的教学，用程序设计竞赛中的算法和数学试题作为实验试题，将算法和数学的教学和程序设计竞赛的解题训练结合在了一起；其次，本书中二百道试题均能通过在线提交的方式进行裁判，使得实验和练习能方便地进行；再次，本书提供了官方的原版试题、测试数据和解答程序作为参考，读者可以通过对官方的测试数据的分析，了解测试数据的特点和常见陷阱，在以后的编程中提高解题质量和正确性。
本书可以作为大专院校计算机专业算法课程教材，也可以作为计算机专业学生的研修资料和程序设计竞赛的培训教材。
本书每章为一个主题，实验内容安排紧扣大学算法和数学的教学，用程序设计竞赛中的算法和数学试题作为实验试题，将算法和数学的教学与程序设计竞赛的解题训练结合在一起；在思维方式和解题策略的训练方面，以问题驱动和启发式引导为主要方式，培养读者通过编程解决问题的能力。
本书特点：
书中给出的234道试题全部精选自ACM国际大学生程序设计竞赛的世界总决赛以及各大洲赛区现场赛和网络预赛、大学程序设计竞赛、在线比赛和其他诸如IOI等程序设计竞赛题目，时间跨度为1989年到2010年，这些试题均能通过在线提交的方式进行实时检验，从而方便读者进行实验和练习。
本书提供了官方的原版试题、测试数据和解答程序作为参考，读者可以通过对官方的测试数据的分析，了解测试数据的特点和常见陷阱，在以后的编程中提高解题质量和正确性。
各章的实验范例可以用于大学算法课程的教学与实验，在此基础上使用题库进行解题，还可以辅导学生进行程序设计竞赛的专项训练。
本书提供了试题的英文原版描述和大部分试题的测试数据，读者可登录华章网站（http://www.hzbook.com）下载。
2012年，我们在机械工业出版社出版了《数据结构编程实验：大学程序设计课程与竞赛训练教材》一书。现在，我们又编著了《算法设计编程实验：大学程序设计课程与竞赛训练教材》，旨在为计算机学科的核心课程——算法与数据结构提供配套的实验教材，为全国各大学的ACM程序设计竞赛活动提供系列化的培训资料，并为从事计算机软硬件研发或系统自学算法的人员提供丰富、实用的参考手册。
全书以知识单元为基本构件，各单元既保持循序渐进的顺序又相对独立，既可拆卸重组、各取所需，又可在此基础上推广或创新，便于各学校按照不同的层次要求组织教学和培训活动。
全书共分8章：
第1章求解Ad Hoc类问题的编程实验：介绍机理分析法和统计分析法，引导读者在没有相应经典和模式化算法的情况下，学会自创简单的算法。
第2章模拟法的编程实验：引导读者如何按照题意设计数学模型的各种参数，观察变更这些参数所引起过程状态的变化，并在此基础上展开算法设计。
第3章数论的编程实验和第4章组合分析的编程实验：这两章凸显了数论和组合分析知识在算法中的应用。其中第3章围绕初等数论中素数运算、求解不定方程和同余方程、应用积性函数等问题展开实验。第4章引导读者在编程求解组合类问题时如何计算具有某种特性的对象个数，如何将它们完全列举出来；如何使用抽屉原理解决存在性问题；如何使用容斥原理计算多个集合并的元素数；如何使用波利亚定理对一个问题的各种不同的组合状态计数。
第5章贪心法的编程实验和第6章动态规划（DP）方法的编程实验：在求解具备最优子结构特征的问题时，这两种方法是最常用、最经典的，但适用场合不同，既有相同点又有不同之处。
第7章高级数据结构的编程实验：选择在一般数据结构教材中没有出现但很有用的一些知识，例如后缀数组、线段树、欧拉图、哈密尔顿图、最大独立集、割点、桥和双连通分支等内容，展开编程实验。
第8章计算几何的编程实验：计算几何学是算法体系中的一个重要组成部分，也是先前算法教材中最薄弱的环节。该章将展开介绍点线面运算、扫描线算法、计算半平面交、计算凸包和旋转卡壳算法等实验。
全书以上述8个知识主线为架构，以问题驱动和启发式引导为主要方式。每个章节都有实验范例，启发性地引出相应的算法设计思想；每个实验范例不仅有知识要点阐述和详尽的试题解析，而且还列出了标有详细注释的参考程序；每个常用的算法都以经典模型为支撑，每个定理、概念都有详尽的说明和推导，并使用大量图表增强直观性和可读性。本书尽力将经典模型推广到具有相同性质的一类问题中，让读者解决一个经典模型就相当于解决一类问题。有时还有意在经典模型外适当加入其他因素，引导读者对被套用的经典模型进行适当修改，加入独特的属性，或者运用已知模型或方法来分析信息原型的属性，在此基础上创造出具有新意的模型或方法来。
“算法设计编程实验”是一门实践出真知的课程，需要大量引入案例教学，通过模拟或者重现现实生活中的一些场景，让读者把自己置入问题情境之中，通过思考、讨论和上机编程来学习算法。为此，本书别出心裁、独辟蹊径，将ACM国际大学生程序设计竞赛和其他程序设计竞赛中的典型试题分门别类，精选了其中234道试题（3题为一题多解），翻译后作为学习算法设计的实验案例。其中83道试题作为各章节的实验范例，151道试题列入各章节的题库。正如上面所说，每个实验范例都有详尽的试题解析和标有注释的参考程序，而题库中的所有试题无论难易，都有清晰的提示。教师既可以将实验范例作为“算法设计编程实验”课程的教学素材，也可以从相关题库中挑选试题作为“算法设计编程实验”课程的作业、考题或ACM集训活动的培训资料。每道题都注明了试题来源和在线测试地址，提供了程序测试的明确去处。这些试题既为学生学习算法的相关知识设立了丰富、有趣的问题背景，使得他们能够带着问题学，而且自编程序的正确性和效率也可以通过相关网站上的测试系统得到实时检验，达到学以致用的目的。此外，本书提供了所有试题的英文原版描述、大部分试题的测试数据等资料，有需要者可登录华章网站（http://www.hzbook.com）下载。
需要说明的是，本书是在复旦大学ACM集训队长期活动的基础上积累而成的，刘宇达、宋凯强、黄云南、符汉杰、袁梓峰、于竟成、钱雨露、沈晨曦、文琪、李星、金阳华等同学精心编写了所有程序，每道程序都通过了严格的测试验证，其中一些程序经多次修改，精益求精。这些同学为本书的出版付出了辛勤的劳动，做出了不可或缺的贡献。在此，向他们表示由衷的感谢。
由于时间和水平所限，书中肯定夹杂了不少缺点和错误，表述不当和笔误更是在所难免，热忱欢迎学术界同仁或读者赐正。如果你在阅读中发现了问题，请通过书信或电子邮件告诉我们，以便及时整理成勘误表放在本书的专门网站上，供广大读者查询更正。我们更期望读者对本书提出建设性意见，以便再版时改进。我们的联系方式是：
通信地址：上海市邯郸路220号复旦大学计算机科学技术学院 吴永辉
邮编：200433
E-mail：yhwu@fudan.edu.cn
王建德 吴永辉
2013年2月20日于上海
注：
本书试题的在线测试地址主要如下表所示：
在线评测系统简称网址北京大学在线评测系统POJhttp://poj.org/浙江大学在线评测系统 ZOJhttp://acm.zju.edu.cn/onlinejudge/UVA在线评测系统UVAhttp://uva.onlinejudge.org/
http://livearchive.onlinejudge.org/Ural在线评测系统Uralhttp://acm.timus.ru/SGU在线评测系统 SGUhttp://acm.sgu.ru/
计算机\算法
本书每章为一个主题，实验内容安排紧扣大学算法和数学的教学，用程序设计竞赛中的算法和数学试题作为实验试题，将算法和数学的教学与程序设计竞赛的解题训练结合在一起；在思维方式和解题策略的训练方面，以问题驱动和启发式引导为主要方式，历练读者通过编程解决问题的能力。
本书特点：
本书给出的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
