前言

一、关于本书

本书是在结合作者多年教学经验及实践的基础上编写而成的。它充分考虑了学生的接受能力，本着“易理解，重实用”的指导思想，以掌握算法设计与分析的基本概念和方法、运用算法理论编程解决实际问题、拓展专业知识结构为宗旨，按照“算法思想—算法设计—构造实例—算法描述—算法分析—C++实战”的思路组织内容，详细讲述了多种经典算法设计策略。纵观全书，这里并没有创造出任何新的算法，因为作者仅仅希望通过对经典算法的讲解，把算法设计与分析中基础且重要的内容用更清晰的思路、更直观的形式展现给读者。

二、本书结构

本书以算法策略为知识单元，共9章内容，其中第1章介绍基础知识，第2～8章介绍经典的算法设计策略，第9章简单介绍NP完全理论。具体结构安排如下：

第1章：算法基础。主要介绍算法设计与分析的基础知识、递归、常用的数据结构及数学公式等。

第2～5章介绍经典的算法设计策略：贪心算法、分治算法、动态规划、搜索算法等。每一种算法设计策略均按照“算法思想—算法设计—构造实例—算法描述—算法分析—C++实战”的思路详细讲解。

第6章：随机化算法。讲述了4种类型的随机化算法，并结合实例讲述了每种随机化算法的特点。

第7章：线性规划问题与网络流。着重讲述线性规划问题的标准化及单纯形算法、网络流的基本概念及理论、求最大流的增广路算法、求最小费用流的消圈算法。

第8章：数论算法及计算几何算法。数论算法中介绍了一些简单的数论理论知识及最大公约数、一次同余方程和同余方程组的算法；计算几何算法中主要介绍叉积的概念和几何意义，进而利用它判断点与线段、线段与线段之间的关系；解决凸包问题及最接近点对问题的两种算法的实现与比较。

第9章：NP完全理论。简单介绍了NP完全理论和近似算法，以引起读者进一步学习和研究的兴趣。

其中，第4～9章由南阳理工学院王秋芬编写，第1～3章由南阳理工学院赵刚彬编写，习题解析由王秋芬编写。

三、本书特点

本书侧重于算法步骤的设计及实例构造，注重算法与数据结构的结合、算法时间效率分析和实战演练。其特色在于针对每一种算法设计策略，按照算法思想设计了详细的算法步骤，构造了具体实例以展现算法的详细演示过程，最后给出算法描述及C++源代码。

本书内容精练，算法设计步骤清晰，实例构造详尽，算法描述的注释清楚，源码完整，阅读材料丰富，易教、易学。通过本书，读者一方面可以学习到基本的算法设计策略、分析和实现方法；另一方面还可以对当今流行算法和算法界的大师有所了解。

在此，谨向清华大学出版社负责本书编辑出版工作的全体人员和每一位曾经关心和支持本书编写工作的各方面专家表示衷心感谢。

由于编者水平有限，书稿虽几经修改，仍难免有疏漏或不妥之处，欢迎广大读者和专家批评指正。

编　者

2022年9月