1、 国外电子与通信教材系列 算法基础打开程序设计之门 梁 冰 冯 林 刘胜蓝 编著 Publishing House of Electronics Industry 北京BEIJING 内 容 简 介 算法是一系列解决问题的清晰指令，是程序设计的灵魂。同一问题可采用不同的算法解决，而一个算法的优劣将直接影响程序的执行效率。本书以 ACM 程序设计竞赛的题目为基础，详细介绍一些常用的算法以及相关的理论知识，主要内容包括高级数据结构、字符串、动态规划进阶算法、图论高级算法、经典算法问题、组合数学、计算几何、组合游戏论。本书适合计算机专业的学生以及对程序设计竞赛感兴趣的读者阅读。本书提供源代码下载，读
2、者可登录华信教育资源网（）免费注册后下载。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目（CIP）数据 算法基础：打开程序设计之门/梁冰，冯林，刘胜蓝编著.北京：电子工业出版社，2019.1 ISBN 978-7-121-35868-5.算 .梁 冯 刘 .程序设计 .TP311.1 中国版本图书馆 CIP 数据核字（2018）第 296484 号 责任编辑：田宏峰 特约编辑：李秦华 印 刷：装 订：出版发行：电子工业出版社 北京市海淀区万寿路 173 信箱 邮编：100036 开 本：787980 1/16 印张：17.5 字数：392 千字 版 次
3、：2019 年 1 月第 1 版 印 次：2019 年 1 月第 1 次印刷 定 价：69.00 元 凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888，88258888。质量投诉请发邮件至 ，盗版侵权举报请发邮件至 。本书咨询联系方式：。前 言 这是一本关于算法的教程。算法是一系列解决问题的清晰指令，可以说它是程序设计的灵魂。同一问题可用不同的算法解决，而一个算法的质量优劣将影响程序的执行效率。算法分析的目的在于选择合适算法和改进算法。评价一个算法的好坏主要是通过算法运行的时间长短和占用空间的大小来评估的。对于计
4、算机专业或者爱好计算机的人士来说，无论学习还是工作，或多或少都会应用一些算法的知识。而目前国内外大型互联网公司在招聘时的笔试和面试都以算法为主。可见，算法的重要性是不言而喻的。ACM/ICPC（ACM International Collegiate Programming Contest）是一项由美国计算机协会主办的，旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。ACM 程序设计竞赛的题目强调算法的高效性与正确性。参赛选手只有编写出能够在规定时间内运行完成若干组数严格的测试数据，并且结果全部正确的程序才能得到分数。本书将以 ACM 程序设计竞赛的题目为基础
5、，介绍一些经典的算法。本书的目的是将更多对计算机算法感兴趣，但又苦于无从入手的读者带进程序设计的大门，让刚迈入大学校门的学生学会使用 C+语言解决简单的问题。本书主要介绍高级数据结构、字符串、动态规划、图论、组合数学方面的经典算法，相信当读者掌握了这些内容之后，会对算法和程序设计有一个新层次的认识，并会产生浓厚的兴趣。对于每个算法，本书都有图文并茂的讲解；在每章节的最后，都有针对该部分知识点的例题讲解，每道例题都是国内外著名程序在线判题系统中的原题，而且对于每道例题，都会从理解题意开始，详细讲解解题的思路，并附有完整的可以正确通过测试样例的代码，供读者研究学习。除了例题，在每章的最后还有一些练
6、习题供读者巩固学到的知识，如果读者对这些习题仍感觉无从下手，可以参考每道练习题后附带的思路分析来帮助整理解题思路。大连理工大学是在全国高校中较早倡导并开展创新创业教育的学校。自 1984 年以来，学校大力开展以突出创新创业实践为特色的创新创业教育。1995 年，在全国率先成立以学生创新创业教育为主体的教学改革示范区创新教育实践中心，开展创新创业教育课程体系、教学内容、教学方法、教学模式等方面的改革，探索与之配套的管理运行机制，将创造性思维与创新方法融入教学实践中，在课堂教学中树立“CDIO 工程教育”新理念，倡导“做中学”，在实践环节构建了“个性化、双渠道、三结合、四层次、多模式”的创新教育实
7、践教学新体系，取得了一系列成果，在全国高校产生了很大的影响。“创造性思维与创新方法”和“创新教育基础与实践（系列）”课程分别被评为国家级精品资源开放课程。“大学生程序设计竞赛初级教材”是“创新教育基础与实践”系列课程的核心课程，是面向大连理工大学 ACM 创新实践班的学生开设的。此外，本书在撰写过程中，除了参考文献和正文中标出的引用来源，还参考了国内外的相关研究成果和网站资源，但没有一一列出，在此感谢所涉及的所有单位、专家和研究人员。因编者水平有限，书中的错误和不足之处在所难免，欢迎广大读者来信批评指正，提出宝贵意见，帮助我们不断地完善本书。编 者 2018 年 12 月 目 录 第 1 章
8、高级数据结构（1）1.1 堆（1）1.1.1 堆的定义（1）1.1.2 建堆（1）1.1.3 堆排序算法（2）1.2 树状数组（3）1.2.1 树状数组的定义（4）1.2.2 树状数组的实现和使用（4）1.2.3 例题讲解（5）1.3 左倾堆（7）1.3.1 左倾堆相关定义和性质（7）1.3.2 左倾堆的操作（7）1.3.3 例题讲解（8）1.4 平衡二叉树（10）1.4.1 Treap （11）1.4.2 Splay 树（13）1.4.3 例题讲解 （18）1.5 练习题（22）第 2 章 字符串（24）2.1 Trie 树（24）2.1.1 Trie 树的原理（24）2.1.2 Trie
9、树的实现（25）2.1.3 例题讲解 （26）2.2 KMP 算法（29）2.2.1 KMP 算法的原理 （29）2.2.2 KMP 算法的实现 （31）2.2.3 例题讲解 （32）2.3 Aho-Corasick 自动机 （35）2.3.1 Aho-Corasick 自动机原理（35）算法基础打开程序设计之门 VI 2.3.2 Aho-Corasick 自动机算法的实现（37）2.3.3 例题讲解 （39）2.4 后缀数组（43）2.4.1 后缀数组基本原理 （43）2.4.2 后缀数组的应用 （46）2.4.3 例题讲解 （49）2.5 练习题（54）第 3 章 动态规划进阶算法（57）
10、3.1 树状 DP （57）3.1.1 树状 DP 的定义 （57）3.1.2 树状 DP 解题方法 （58）3.1.3 例题讲解 （58）3.2 状态压缩 DP （62）3.2.1 集合的整数表示 （62）3.2.2 例题讲解 （63）3.3 动态规划的优化方法（66）3.3.1 单调队列优化的动态规划 （66）3.3.2 例题讲解 （66）3.3.3 斜率优化的动态规划 （68）3.3.4 例题讲解 （68）3.3.5 四边形不等式优化的动态规划 （71）3.3.6 例题讲解 （71）3.4 练习题（73）第 4 章 图论高级算法（76）4.1 最大流（76）4.1.1 最大流的定义 （7
11、6）4.1.2 增广路算法涉及的三个重要概念 （77）4.1.3 Edmonds-Karp 算法 （79）4.1.4 Dinic 算法（82）4.1.5 ISAP 算法 （84）4.1.6 网络流的建图 （89）4.1.7 例题讲解 （91）4.2 最小费用流（99）4.2.1 最小费用流算法 （99）目录 VII 4.2.2 例题讲解（100）4.3 二分图匹配（109）4.3.1 二分图的定义（109）4.3.2 二分图的最大匹配（109）4.3.3 二分图的性质与应用（114）4.3.4 例题讲解（115）4.4 练习题（118）第 5 章 经典算法问题（121）5.1 多项式与快速傅里
12、叶变换（121）5.1.1 多项式（121）5.1.2 多项式的表示与多项式乘法（121）5.1.3 DFT 和 FFT 的实现（123）5.1.4 例题讲解（124）5.2 NP 完全性（127）5.2.1 NP 问题简介（127）5.2.2 哈密顿回路（127）5.2.3 例题讲解（128）5.3 对偶图问题（135）5.3.1 基本概念（135）5.3.2 平面图转化为对偶图（137）5.3.3 对偶图的应用（140）5.4 RMQ 问题（144）5.4.1 RMQ 问题的简单求解方法（145）5.4.2 ST（Sparse Table）算法（145）5.4.3 例题讲解（146）5.5
13、 LCA 问题（151）5.5.1 LCA 问题的简单求解方法（151）5.5.2 基于倍增的双亲存储法（152）5.5.3 高效的 LCA 算法（152）5.5.4 例题讲解（154）5.6 练习题（158）第 6 章 组合数学（161）6.1 排列组合（161）6.1.1 基本计数原则（161）算法基础打开程序设计之门 VIII 6.1.2 排列（161）6.1.3 组合（162）6.1.4 例题讲解（163）6.2 母函数（164）6.2.1 母函数基础（165）6.2.2 母函数的两类具体应用（165）6.2.3 例题讲解（166）6.3 整数划分（169）6.3.1 从动态规划到母函
14、数（169）6.3.2 例题讲解（170）6.4 Stirling 数和 Catalan 数（172）6.4.1 第一类 Stirling 数（172）6.4.2 第二类 Stirling 数（173）6.4.3 Catalan 数（173）6.4.4 例题讲解（174）6.5 容斥原理与反演（179）6.5.1 容斥原理（179）6.5.2 反演理论（180）6.5.3 Mobius 反演（181）6.5.4 例题讲解（184）6.6 群论与 Polya 定理（187）6.6.1 群的基本性质（187）6.6.2 置换群（188）6.6.3 Burnside 定理及 Polya 定理（189
15、）6.6.4 例题讲解（190）6.7 练习题（192）第 7 章 计算几何（195）7.1 多边形上的数据结构表示（195）7.1.1 点（195）7.1.2 线段（197）7.1.3 多边形类（198）7.1.4 例题讲解（199）7.2 多边形相交问题（202）7.2.1 线段相交（202）目录 IX 7.2.2 多边形相交问题的讨论（203）7.2.3 例题讲解（204）7.3 多边形求面积（207）7.3.1 计算多边形的面积（207）7.3.2 格点数（208）7.3.3 例题讲解（209）7.4 凸包（210）7.4.1 凸多边形（210）7.4.2 凸多边形的性质（215）7.
16、4.3 构造凸包（215）7.4.4 例题讲解（219）7.5 相交问题（230）7.5.1 半平面交（230）7.5.2 凸多边形交（232）7.5.3 例题讲解（232）7.6 圆（240）7.6.1 圆与线段的交（240）7.6.2 圆与多边形的交的面积（241）7.6.3 圆与圆的交的面积（241）7.6.4 圆与圆的并的面积（245）7.7 练习题（249）第 8 章 组合游戏论（252）8.1 组合游戏论中的游戏（252）8.1.1 组合游戏论的定义（252）8.1.2 博弈树模型（253）8.1.3 巴什博弈（253）8.1.4 威佐夫博弈（254）8.1.5 例题讲解（255）8.2 NIM 游戏和 SG 函数（256）8.2.1 NIM 游戏的定义（256）8.2.2 NIM 游戏中的性质（256）8.2.3 Sprague-Grundy 函数的价值（257）8.2.4 SG 函数的应用（258）8.2.5 例题讲解（259）算法基础打开程序设计之门 X 8.3 NIM 游戏的变形（262）8.3.1 ANTI-NIM 问题（262）8.3.2 Staircase N