基本信息
- 原书名：Algorithm Design Practice：for Collegiate Programming Contest and Education
编辑推荐
适用于ACM-ICPC、IOI等各类
程序设计竞赛的训练
精析典型赛题，并给出有详细注释的参考程序
系统、高效地训练思维能力和编程能力
内容简介
目录
前 言
第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
第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
前言
本书是“大学程序设计课程与竞赛训练教材”系列著作中的第2部。我们编著这一系列著作的指导思想如下。
（1）程序设计竞赛是“通过编程解决问题”的竞赛。国际大学生程序设计竞赛（Inter-national Collegiate Programming Contest，ICPC）和中学生国际信息学奥赛（International Olympiad in Informatics，IOI）在20世纪80年代中后期走向成熟，30多年来，累积了海量的试题。这些来自全球各地、凝聚了无数命题者的心血和智慧的试题，不仅可以用于程序设计竞赛选手的训练，而且可以用于教学，以系统、全面地提高学生编程解决问题的能力。
（2）我们认为，评价一个人的专业能力，要看这个人的两个方面：1）知识体系，即他能用哪些知识去解决问题，或者说，他所真正掌握并能应用的知识，而不仅仅是他学过的知识；2）思维方式，即他在面对问题（特别是不太标准化的问题）的时候，解决问题的策略是什么？对于程序设计竞赛选手所要求的知识体系，可以概括为1984年图灵奖得主Niklaus Wirth提出的著名公式“算法+数据结构=程序”，这也是计算机学科知识体系的核心部分，因此本系列的前两部著作分别是《数据结构编程实验》和《算法设计编程实验》。对于需要采用某些策略进行求解的程序设计试题，比如，不采用常用的数据结构或者需要优化解题的算法，我们进行分析整理，编写了本系列的第3部著作《程序设计解题策略》。
（3）从本质上说，程序设计是技术，所以，首先牢记学习编程要不断“Practice, Practice,
Practice”!本系列选用程序设计竞赛的大量试题，以案例教学的方式进行教学实验并安排学生进行解题训练。其次，“Practice in a systematic way”。本系列的编写基于传统的教学大纲，以系统、全面地提高学生编程解决问题的能力为目标，以程序设计竞赛的试题及详细的解析、带注释的程序作为实验，在每一章的结束部分给出相关题库及解题提示，并对大部分试题给出官方的测试数据。
2013年，我们在机械工业出版社出版了《算法设计编程实验：大学程序设计课程与竞赛训练教材》。2018年，我们在CRC Press出版了该书的英文版《Algorithm Design Practice: for Collegiate Programming Contest and Education》。此外，我们还在中国台湾地区出版了繁体中文版。
本书的第1版是在复旦大学程序设计集训队长期活动的基础上编写而成的，共分8章，主要内容如下：
第1章“求解Ad Hoc类问题的编程实验”：介绍了机理分析法和统计分析法，引导读者在没有经典和模式化算法可对应的情况下，学会自创简单的算法。
第2章“模拟法的编程实验”：引导读者按照题意设计数学模型的各种参数，观察变更这些参数所引起的过程状态的变化，在此基础上展开算法设计。
第3章“数论的编程实验”和第4章“组合分析的编程实验”：这两章凸显了数论和组合分析知识在算法中的应用。其中，第3章围绕初等数论中的素数运算、求解不定方程和同余方程、应用积性函数等问题展开实验。第4章介绍在编程求解组合类问题时如何计算具有某种特性的对象个数，如何将它们完全列举出来，如何使用抽屉原理解决存在性问题，如何使用容斥原理计算多个集合并的元素数，如何使用Pólya定理对一个问题的各种不同的组合状态计数。
第5章“贪心法的编程实验”和第6章“动态规划方法的编程实验”：在求解具备最优子结构特征的问题时，这两种方法是最常用、最经典的思想方法，但适用场合不同，既有相同点又有区别之处。
第7章“高级数据结构的编程实验”：选择在一般数据结构教材中没有出现但很有用的一些知识，例如后缀数组、线段树、欧拉图、哈密顿图、最大独立集、割点、桥和双连通分支等内容展开编程实验。
第8章“计算几何的编程实验”：计算几何学是算法体系中一个重要的组成部分，也是先前算法教材中最薄弱的环节。该章开展点线面运算、扫描线算法、计算半平面交、凸包计算和旋转卡壳算法等实验。
近来年，我们使用本书第1版的中、英文版在全球高校进行教学，根据读者和学生的反馈，我们对本书第1版的内容进行了修订，形成了第2版。我们除了修正第1版中的小错误，以及改进一些表述之外，还做了如下较大改进：
对于第3章“数论的编程实验”和第4章“组合分析的编程实验”的内容和结构，基于数论、组合数学的知识体系，进行全面的加强和改进。其中，第3章从素数运算、求解不定方程和同余方程、特殊的同余式、积性函数的应用、高斯素数5个方面展开实验；而第4章从排列的生成、排列和组合的计数、容斥原理与鸽笼原理、Pólya计数公式、生成函数与递推关系、快速傅里叶变换（FFT）6个方面展开实验。对于数论、组合分析所涉及的知识点，都采用程序设计竞赛的试题作为实验范例，也就是说，基于数论、组合分析的知识体系，实验范例“鱼鳞状”分布在各个知识点中。同时，将数学证明能力和编程解决问题能力的训练相结合，这也是数学类试题的特征。
对于第5章“贪心法的编程实验”和第6章“动态规划方法的编程实验”，则增加了经典问题的实验。在第5章中，增加了背包问题、任务调度、区间调度等经典贪心问题的实验；在第6章中，则以“背包九讲”为基础，增加0-1背包问题的实验。这样改进的目的，是使读者能够更好地体验贪心和动态规划的方法。
本书可以用于大学的算法及相关数学课程的教学和实验，也可以用于程序设计竞赛选手的系统训练。对于本书，我们的使用建议是：书中每章的实验范例可以用于算法和数学课程的教学、实验和上机作业，以及程序设计竞赛选手掌握相关知识点的入门训练；而每章最后给出的相关题库中的试题则可以作为程序设计竞赛选手的专项训练试题，以及学生进一步提高编程能力的练习题。
我们对浩如烟海的ACM-ICPC预赛和总决赛、各种大学生程序设计竞赛、在线程序设计竞赛及中学生信息学奥林匹克竞赛的试题进行了分析和整理，从中精选出314道试题作为本书的试题。其中157道试题作为实验范例试题，每道试题不仅有详尽的解析，还给出标有详细注释的参考程序；另外的157道试题为题库试题，所有试题都有清晰的提示。
本书提供了所有试题的英文原版以及大部分试题的官方测试数据和解答程序，有需要者可登录华章网站（http://www.hzbook.com）下载。
感谢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同学审阅英文版书稿的部分章节。
（1）程序设计竞赛是“通过编程解决问题”的竞赛。国际大学生程序设计竞赛（Inter-national Collegiate Programming Contest，ICPC）和中学生国际信息学奥赛（International Olympiad in Informatics，IOI）在20世纪80年代中后期走向成熟，30多年来，累积了海量的试题。这些来自全球各地、凝聚了无数命题者的心血和智慧的试题，不仅可以用于程序设计竞赛选手的训练，而且可以用于教学，以系统、全面地提高学生编程解决问题的能力。
（2）我们认为，评价一个人的专业能力，要看这个人的两个方面：1）知识体系，即他能用哪些知识去解决问题，或者说，他所真正掌握并能应用的知识，而不仅仅是他学过的知识；2）思维方式，即他在面对问题（特别是不太标准化的问题）的时候，解决问题的策略是什么？对于程序设计竞赛选手所要求的知识体系，可以概括为1984年图灵奖得主Niklaus Wirth提出的著名公式“算法+数据结构=程序”，这也是计算机学科知识体系的核心部分，因此本系列的前两部著作分别是《数据结构编程实验》和《算法设计编程实验》。对于需要采用某些策略进行求解的程序设计试题，比如，不采用常用的数据结构或者需要优化解题的算法，我们进行分析整理，编写了本系列的第3部著作《程序设计解题策略》。
（3）从本质上说，程序设计是技术，所以，首先牢记学习编程要不断“Practice, Practice,
Practice”!本系列选用程序设计竞赛的大量试题，以案例教学的方式进行教学实验并安排学生进行解题训练。其次，“Practice in a systematic way”。本系列的编写基于传统的教学大纲，以系统、全面地提高学生编程解决问题的能力为目标，以程序设计竞赛的试题及详细的解析、带注释的程序作为实验，在每一章的结束部分给出相关题库及解题提示，并对大部分试题给出官方的测试数据。
2013年，我们在机械工业出版社出版了《算法设计编程实验：大学程序设计课程与竞赛训练教材》。2018年，我们在CRC Press出版了该书的英文版《Algorithm Design Practice: for Collegiate Programming Contest and Education》。此外，我们还在中国台湾地区出版了繁体中文版。
本书的第1版是在复旦大学程序设计集训队长期活动的基础上编写而成的，共分8章，主要内容如下：
第1章“求解Ad Hoc类问题的编程实验”：介绍了机理分析法和统计分析法，引导读者在没有经典和模式化算法可对应的情况下，学会自创简单的算法。
第2章“模拟法的编程实验”：引导读者按照题意设计数学模型的各种参数，观察变更这些参数所引起的过程状态的变化，在此基础上展开算法设计。
第3章“数论的编程实验”和第4章“组合分析的编程实验”：这两章凸显了数论和组合分析知识在算法中的应用。其中，第3章围绕初等数论中的素数运算、求解不定方程和同余方程、应用积性函数等问题展开实验。第4章介绍在编程求解组合类问题时如何计算具有某种特性的对象个数，如何将它们完全列举出来，如何使用抽屉原理解决存在性问题，如何使用容斥原理计算多个集合并的元素数，如何使用Pólya定理对一个问题的各种不同的组合状态计数。
第5章“贪心法的编程实验”和第6章“动态规划方法的编程实验”：在求解具备最优子结构特征的问题时，这两种方法是最常用、最经典的思想方法，但适用场合不同，既有相同点又有区别之处。
第7章“高级数据结构的编程实验”：选择在一般数据结构教材中没有出现但很有用的一些知识，例如后缀数组、线段树、欧拉图、哈密顿图、最大独立集、割点、桥和双连通分支等内容展开编程实验。
第8章“计算几何的编程实验”：计算几何学是算法体系中一个重要的组成部分，也是先前算法教材中最薄弱的环节。该章开展点线面运算、扫描线算法、计算半平面交、凸包计算和旋转卡壳算法等实验。
近来年，我们使用本书第1版的中、英文版在全球高校进行教学，根据读者和学生的反馈，我们对本书第1版的内容进行了修订，形成了第2版。我们除了修正第1版中的小错误，以及改进一些表述之外，还做了如下较大改进：
对于第3章“数论的编程实验”和第4章“组合分析的编程实验”的内容和结构，基于数论、组合数学的知识体系，进行全面的加强和改进。其中，第3章从素数运算、求解不定方程和同余方程、特殊的同余式、积性函数的应用、高斯素数5个方面展开实验；而第4章从排列的生成、排列和组合的计数、容斥原理与鸽笼原理、Pólya计数公式、生成函数与递推关系、快速傅里叶变换（FFT）6个方面展开实验。对于数论、组合分析所涉及的知识点，都采用程序设计竞赛的试题作为实验范例，也就是说，基于数论、组合分析的知识体系，实验范例“鱼鳞状”分布在各个知识点中。同时，将数学证明能力和编程解决问题能力的训练相结合，这也是数学类试题的特征。
对于第5章“贪心法的编程实验”和第6章“动态规划方法的编程实验”，则增加了经典问题的实验。在第5章中，增加了背包问题、任务调度、区间调度等经典贪心问题的实验；在第6章中，则以“背包九讲”为基础，增加0-1背包问题的实验。这样改进的目的，是使读者能够更好地体验贪心和动态规划的方法。
本书可以用于大学的算法及相关数学课程的教学和实验，也可以用于程序设计竞赛选手的系统训练。对于本书，我们的使用建议是：书中每章的实验范例可以用于算法和数学课程的教学、实验和上机作业，以及程序设计竞赛选手掌握相关知识点的入门训练；而每章最后给出的相关题库中的试题则可以作为程序设计竞赛选手的专项训练试题，以及学生进一步提高编程能力的练习题。
我们对浩如烟海的ACM-ICPC预赛和总决赛、各种大学生程序设计竞赛、在线程序设计竞赛及中学生信息学奥林匹克竞赛的试题进行了分析和整理，从中精选出314道试题作为本书的试题。其中157道试题作为实验范例试题，每道试题不仅有详尽的解析，还给出标有详细注释的参考程序；另外的157道试题为题库试题，所有试题都有清晰的提示。
本书提供了所有试题的英文原版以及大部分试题的官方测试数据和解答程序，有需要者可登录华章网站（http://www.hzbook.com）下载。
感谢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同学审阅英文版书稿的部分章节。
媒体评论
本书基于作者20余年来总结的编程知识体系和行之有效的编程能力训练方法，以ACM-ICPC、IOI等各类大型程序设计竞赛的经典试题为素材编写而成，通过启发式、案例化的教学，系统、全面地培养读者编程解决问题的能力。本书不仅可以作为ACM-ICPC、IOI等程序设计竞赛的训练教程，亦可作为高校程序设计相关课程的实践教材以及对编程感兴趣的读者的自学读物。
本书特色
从ACM-ICPC、IOI等各类国内外程序设计竞赛中精选300余道典型赛题，并归为Ad Hoc、模拟、数论、组合分析、贪心、动态规划、高级数据结构、计算几何八类，使读者掌握各类经典问题的思考方法和解题策略。
将150余道试题作为范例试题，每道试题不仅有详尽的试题解析，还给出有详细注释的参考程序；其他试题为题库试题，每道试题给出清晰的提示，使读者进一步训练解题策略。
与上一版相比，数论、组合分析两章通过程序设计竞赛试题及其解析对相关知识点进行了全覆盖，贪心、动态规划两章则加强了对经典问题的解析。
本书给出所有试题的英文原版以及大部分试题的官方测试数据和解答程序，读者可登录华章网站下载。
本书特色
从ACM-ICPC、IOI等各类国内外程序设计竞赛中精选300余道典型赛题，并归为Ad Hoc、模拟、数论、组合分析、贪心、动态规划、高级数据结构、计算几何八类，使读者掌握各类经典问题的思考方法和解题策略。
将150余道试题作为范例试题，每道试题不仅有详尽的试题解析，还给出有详细注释的参考程序；其他试题为题库试题，每道试题给出清晰的提示，使读者进一步训练解题策略。
与上一版相比，数论、组合分析两章通过程序设计竞赛试题及其解析对相关知识点进行了全覆盖，贪心、动态规划两章则加强了对经典问题的解析。
本书给出所有试题的英文原版以及大部分试题的官方测试数据和解答程序，读者可登录华章网站下载。
