《算法设计编程实验：大学程序设计课程与竞赛训练教材》是“大学程序设计课程与竞赛训练教材”系列著作中的第2部著作。我们编著这一系列著作的的指导思想是：

（1）程序设计竞赛是“编程解决问题”的竞赛。国际大学生程序设计竞赛（International Collegiate Programming Contest，ICPC）和中学生国际信息学奥赛（International Olympiad in Informatics，IOI）在1980年代中后期走向成熟之后，这30年来，累积了海量的试题。这些来自全球各地，凝聚了无数命题者的心血和智慧的试题，不仅可以用于程序设计竞赛选手的训练，而且可以用于教学，系统、全面提高学生编程解决问题的能力；

（2）我们认为，评价一个人的专业能力，是看这个人的两个方面：1）知识体系；他能用哪些知识去解决问题，或者说，是他所真正掌握、并能应用的知识，而不仅仅是他学过的知识；2）思维方式；在他面对问题，特别是不太标准化的问题的时候，他解决问题的策略是什么？对于程序设计竞赛选手所要求的知识体系，可以概括为“算法+数据结构=程序”，而这也是计算机学科知识体系的核心部分；因此本系列的前两部著作分别是《数据结构编程实验》和《算法设计编程实验》；对于需要采用某些策略进行求解的程序设计试题，比如，并不采用常用的数据结构，或者解题的算法要进行优化，等等；我们进行分析整理，编写本系列的第3部著作《程序设计解题策略》。

（3）程序设计，从其本质上说，是技术。所以，首先，“Practice, Practice, and Practice!”。本系列选用大量的程序设计竞赛的试题，以案例教学的方式，来进行教学实验和安排学生解题训练。其次，“Practice in a systematic way.”。本系列基于传统的教学大纲，以系统、全面提高学生编程解决问题的能力为目标，以程序设计竞赛的试题以及详细的解析、带注解的程序作为实验；并在每一章的结束部分，给出相关题库以及解题提示；并对大部分试题给出官方的测试数据。

基于上述的指导思想，我们在中国大陆出版了本系列的简体中文版，在台湾出版繁体中文版，在美国由CRC Press出版英文版。

2013年，我们在机械工业出版社出版《算法设计编程实验：大学程序设计课程与竞赛训练教材》。2018年，我们在CRC Press出版该书的英文版《Algorithm Design Practice: for Collegiate Programming Contest and Education》，全球发行。在该书的中、英文版这些年来在境内外广泛使用的基础上，我们对第一版进行了脱胎换骨的改进，编著、出版《算法设计编程实验：大学程序设计课程与竞赛训练教材》的第2版。

在第1版中，《算法设计编程实验：大学程序设计课程与竞赛训练教材》共分8章：

 第1章《Ad Hoc类问题的编程实验》：介绍了机理分析法和统计分析法，引导读者在没有经典和模式化算法可对应的情况下，学会自创简单的算法。

第2章《模拟法的编程实验》：引导读者如何按照题意设计数学模型的各种参数，观察变更这些参数所引起过程状态的变化，在此基础上展开算法设计。

第3、4章《数论的编程实验》和《组合分析的编程实验》：这两章凸显了数论和组合分析知识在算法中的应用，其中第3章围绕初等数论中素数运算、求解不定方程和同余方程、应用积性函数等问题展开实验；第4章引导读者在编程求解组合类问题时如何计算具有某种特性的对象个数，如何将它们完全例举出来；如何使用抽屉原理解决存在性问题；如何使用容斥原理计算多个集合并的元素数；如何使用波利亚定理对一个问题的各种不同的组合状态计数。

第5章、第6章《贪心法的编程实验》和《动态规划方法的编程实验》：在求解具备最优子结构特征的问题时，这两种方法是最常用、最经典的思想方法，但适用场合不同，既有相同点又有区别之处。

第7章《高级数据结构的编程实验》：选择在一般数据结构教材中没有出现、但很有用的一些知识，例如后缀数组、线段树、欧拉图、哈密尔顿图、最大独立集、割点、桥和双连通分支等内容展开编程实验。

第8章《计算几何的编程实验》：计算几何学是算法体系中的一个重要组成部分，也是先前算法教材中最薄弱的环节。该章节将展开点线面运算、扫描线算法、计算半平面交、凸包计算和旋转卡壳算法等实验。

相应于本书的第1版，我们除了修正原有的小错误和笔误，以及改进了一些表述外，较大的改进如下：

对于第3章《数论的编程实验》和第4章《组合分析的编程实验》的内容和结构，基于数论、组合数学的知识体系，进行全面的加强和改进。其中，第3章在素数运算、求解不定方程和同余方程、特殊的同余式、积性函数的应用、高斯素数等5个方面展开实验；而第4章在排列的生成、排列和组合的计数、容斥原理与鸽笼原理、Pólya计数公式、生成函数与递推关系、快速傅里叶变换（FFT）等6个方面展开实验。对于数论、组合分析所涉及的知识点，都采用程序设计竞赛的试题，作为实验范例；也就是说，基于数论、组合分析的知识体系，实验范例“鱼鳞状分布”在各个知识点中。同时，将数学证明能力和编程解决问题的能力的训练相结合，这也是数学类试题的特征。

对于第5章《贪心法的编程实验》和第6章《动态规划方法的编程实验》，则增加了经典问题的实验。在第5章中，增加背包问题、任务调度、区间调度等经典的贪心问题的实验；在第6章中，则以“背包九讲”为基础，增加0-1背包问题的实验。这样改进的目的，是使得同学们能够更好地体验贪心和动态规划的方法。

本书可以用于大学的算法以及相关数学课程的教学和实验，也可以用于程序设计竞赛选手的系统训练。对于本书，我们的使用建议是：书中每章的实验范例可以用于算法、数学课程的教学、实验和上机作业，以及程序设计竞赛选手掌握相关知识点的入门训练；而在每章最后给出的相关题库中的试题则可以作为程序设计竞赛选手的专项训练试题，以及学生进一步提高编程能力的练习题。

我们对浩如烟海的ACM-ICPC程序设计竞赛区预赛和总决赛、各种大学生程序设计竞赛、在线程序设计竞赛以及中学生信息学奥林匹克竞赛的试题进行了分析和整理，从中精选出314道试题作为本书的试题，其中157道试题作为实验范例试题，每道试题不仅有详尽的试题解析，还给出标有详细注释的参考程序；另外的157道试题为题库试题，所有试题都有清晰的提示。

在本书的网站中提供了所有试题的英文原版以及大部分试题的官方测试数据和解答程序。

本书的第1版是在复旦大学程序设计集训队长期活动的基础上积累而成的。

感谢Stony Brook University的Steven Skiena教授和Rezaul Chowdhury教授；Texas State University的C. Jinshong Hwang教授、Ziliang Zong教授和Hongchi Shi教授；German University of Technology in Oman的Rudolf Fleischer教授；North South University的Abul L.Haque教授和Shazzad Hosain教授；International Islamic University Malaysia的Normaziah Abdul Aziz教授；以及香港理工大学曹建农教授，他们为本书英文版书稿的试用和改进提供了英语为母语或官方语言的平台。感谢Georgia Institute of Technology的Jiaqi Chen同学审看英文版书稿的部分章节。

感谢巴黎第十一大学博士生张一博同学、香港中文大学博士生王禹同学和复旦大学已故教授朱洪先生，他们对于第2版的编写提出了建设性的意见。

感谢组织程序设计训练营集训并邀请我使用本书书稿讲学的香港理工大学曹建农教授；台湾东华大学彭胜龙教授；西北工业大学姜学峰教授和刘君瑞教授；宁夏理工学院副校长俞经善教授；中国矿业大学毕方明教授；以及中国矿业大学徐海学院刘昆教授等老师。

感谢指出书稿中错误的西安电子科技大学朱微、张恩溶和中国矿业大学徐海学院贺小梅等同学。

特别感谢两岸四地的同仁们和我一起创建ACM-ICPC亚洲训练联盟，不仅为本书书稿，也为我的系列著作及其课程建设提供了一个实践的平台。这些年，我们并肩作战，风雨同舟，如莎士比亚《亨利五世》的台词：“今日谁与我共同浴血，他就是我的兄弟！”

由于时间和水平所限，书中肯定夹杂了不少缺点和错误，表述不当和笔误也在所难免，热忱欢迎学术界同仁和读者赐正。如果您在阅读中发现了问题，恳请通过电子邮件告诉我们，以便我们在课程建设和中英文版再版时改进。我们的联系方式如下：

通信地址：上海市邯郸路220号复旦大学计算机科学技术学院吴永辉 （邮编：200433）

电子邮件：yhwu@fudan.edu.cn

     吴永辉   王建德

                                                 2019-7-30于上海

 

目录

 

前言

 

第1章  求解Ad Hoc类问题的编程实验

1.1机理分析法的实验范例

1.2统计分析法的实验范例

1.3 相关题库

 

第2章 模拟法的编程实验

2.1直叙式模拟的实验范例

2.2筛选法模拟的实验范例

2.3构造法模拟的实验范例

2.4 相关题库

 

第3章 数论的编程实验

3.1素数运算的实验范例

3.1.1 使用筛法生成素数的实验范例

3.1.2 测试大素数的实验范例

3.2求解不定方程和同余方程的实验范例

3.2.1计算最大公约数和不定方程

3.2.2 计算同余方程和同余方程组

3.2.3 计算多项式同余方程

3.3  特殊的同余式

3.3.1 威尔逊定理和费马小定理

3.3.2  伪素数

3.3.3  欧拉定理

3.4 积性函数的实验范例

3.4.1欧拉函数()的实验范例

3.4.2莫比乌斯函数(n)的实验范例

3.4.3完全数和梅森素数

3.5高斯素数的实验范例

3.6 相关题库

 

第4章  组合分析的编程实验

4.1生成排列的实验范例

4.1.1按字典序思想生成下一个排列

4.1.2按字典序思想生成所有排列

4.2排列组合计数的实验范例

4.2.1 一般的排列组合计数公式

4.2.2两种特殊的排列组合计数公式

4.2.3 多重集的排列数和组合数

4.3容斥原理与鸽笼原理的实验范例

4.3.1利用鸽笼原理求解存在性问题

4.3.2容斥原理应用实验

4.3.3 Ramsey定理的应用

4.4 Pólya计数公式的实验范例

4.5生成函数与递推关系

4.5.1幂级数型生成函数

4.5.2指数数型生成函数

4.5.3递推关系

4.6 快速傅里叶变换（FFT）的实验范例

4.7 相关题库

 

第5章  贪心法的编程实验

5.1体验贪心法内涵的实验范例

5.1.1  贪心法的经典问题

5.1.2  体验贪心法内涵的实验范例

5.2利用数据有序化进行贪心选择的实验范例

5.3在综合性的P类问题中使用贪心法的实验范例

5.4相关题库

 

第6章  动态规划方法的编程实验

6.1 线性DP的实验范例

6.1.1初步体验线性DP问题

6.1.2 子集和问题

6.1.3 最长公共子序列问题

6.1.4 最长递增子序列问题

 6.2  0-1背包问题

6.2.1基本的0-1背包

6.2.2 完全背包

6.2.3 多重背包

6.2.4 混合背包

6.2.5二维背包

6.2.6分组背包

6.2.7有依赖的背包

6.3 树形DP的实验范例

6.4 状态压缩DP的实验范例

6.5 单调优化1D/1D DP的实验范例

6.5.1经典模型1：利用决策代价函数w的单调性优化

6.5.2经典模型2：利用决策区间下界的单调性优化

6.5.3经典模型3：利用最优决策点的凸性优化

6.6 相关题库

 

第7章  高级数据结构的编程实验

7.1后缀数组的实验范例

7.1.1使用倍增算法计算名次数组和后缀数组

7.1.2 计算最长公共前缀

7.1.3后缀数组的应用

7.2线段树的实验范例

7.2.1线段树的基本概念和基本操作

7.2.2线段树单点更新的维护

7.2.3线段树子区间更新的维护

7.3处理特殊图的实验范例

7.3.1 计算欧拉图

7.3.2 计算哈密尔顿图

7.3.3计算最大独立集

7.3.4 计算割点、桥和双连通分支

7.4相关题库

 

第8章  计算几何的编程实验

8.1点线面运算的实验范例

8.1.1 计算点积和叉积

8.1.2 计算线段交

8.1.3利用欧拉公式计算多面体

8.2 利用扫描线算法计算矩形面积并

8.2.1 沿垂直方向计算矩形的并面积

8.2.2 沿水平方向计算矩形的并面积

8.3计算半平面交的实验范例

8.3.1计算半平面交的联机算法

8.3.2利用极角计算半平面交的算法

8.4计算凸包和旋转卡壳的实验范例

8.4.1计算凸包

8.4.2旋转卡壳实验

8.5相关题库