前言







党的二十大报告指出： 教育、科技、人才是全面建设社会主义现代化国家的基础性、战略性支撑。必须坚持科技是第一生产力、人才是第一资源、创新是第一动力，深入实施科教兴国战略、人才强国战略、创新驱动发展战略，开辟发展新领域新赛道，不断塑造发展新动能新优势。高等教育与经济社会发展紧密相连，对促进就业创业、助力经济社会发展、增进人民福祉具有重要意义。

用计算机求解问题就是将特定问题的求解过程转换为计算机可以执行的程序。能够设计好的程序是计算机专业学生的基本功。在计算机教学体系中编程类的主要课程有“高级程序设计语言”“数据结构”“算法设计与分析”等，这些课程相互承接，程序设计语言是求解问题的工具，数据结构是求解问题的基础，算法设计是求解问题的关键。

“算法设计与分析”课程是计算机科学与技术等专业的必修课，课程目的是通过学习掌握算法设计的主要策略和算法复杂性分析的方法，并能熟练运用各种数据结构和常用算法策略设计高效算法，培养学生分析问题和解决复杂工程问题的能力，为学生进一步学习后续课程奠定良好的基础。本书是编者长期从事“数据结构”“算法设计与分析”课程教学的经验总结，凝聚了编者多年的教学体会和教学理念。

1. 本书内容

全书由9章构成，各章的内容如下。

第1章为算法入门——概论，介绍算法的概念、算法描述方法、算法设计步骤和算法时空分析方法。

第2章为工之利器——常用数据结构及其应用，结合Python中的各种数据类型介绍线性表、字符串、栈、双端队列、队列、优先队列、树和二叉树、图、并查集、二叉排序树和平衡二叉树、哈希表等数据结构原理和应用。

第3章为必备技能——基本算法设计方法，介绍穷举法、归纳法、迭代法和递归法等常用的算法设计方法，讨论递推式计算等基本算法分析方法。

第4章为分而治之——分治法，介绍分治法的原理和框架，讨论利用分治法求解排序问题、查找问题和组合问题等，包括快速排序、归并排序、二分查找、假币问题、最大连续子序列和、多数元素和最近点对距离等典型算法。

第5章为走不下去就回退——回溯法，介绍解空间的概念和回溯法框架，根据解空间的类型分别讨论基于子集树框架和基于排列树框架的问题求解方法，包括子集和问题、简单装载问题、0/1背包问题、n皇后问题、任务分配问题、图的m着色和货郎担问题等典型算法。

第6章为朝最优解方向前进——分支限界法，介绍分支限界法的要点和框架，讨论广度优先搜索、队列式分支限界法和优先队列式分支限界法，包括图的单源最短路径、0/1背包问题、任务分配问题和货郎担问题等典型算法。

第7章为每一步局部最优——贪心法，介绍贪心法的策略和要点，讨论采用贪心法求解组合问题、图问题、调度问题和哈夫曼编码，包括活动安排问题Ⅰ、Prim算法、Kruskal算法、Dijkstra算法和不带惩罚/带惩罚的调度问题等典型算法。

第8章为保存子问题的解——动态规划，介绍动态规划的原理和要点，讨论一维动态规划、二维动态规划、三维动态规划、字符串动态规划、背包动态规划、树形动态规划和区间动态规划算法设计方法，包括最大连续子序列和、最长递增子序列、活动安排问题Ⅱ、三角形的最小路径和、Floyd算法、双机调度、最长公共子序列、编辑距离、0/1背包问题、完全背包问题和多重背包问题等典型算法。

第9章为最难问题——NP完全问题，介绍P类、NP类和NP完全问题。

书中带“*”符号的部分作为选学内容。

2. 本书特色

本书具有以下鲜明特色。

(1) 由浅入深，循序渐进。每种算法策略从设计思想、算法框架入手，由易到难地讲解经典问题的求解过程，使读者既能学到求解问题的方法，又能通过对算法策略的反复应用掌握其核心原理，以收到融会贯通之效。

(2) 示例丰富，重视启发。书中列举大量具有典型性的求解问题，深入剖析采用相关算法策略求解的思路，清晰地展示算法设计的过程，并举一反三，激发学生学习算法设计的兴趣。

(3) 注重求解问题的多维性。同一个问题采用多种算法策略实现，例如0/1背包问题采用回溯法、分支限界法和动态规划求解。通过不同算法策略的比较，使学生更容易了解每一种算法策略的设计特点和各自的优缺点，以提高算法设计的效率。

(4) 强调实践和动手能力的培养。书中针对相关知识点以实战题形式讨论了力扣中国网站部分在线编程题的设计思路和解题过程，让学生体会到“学以致用”和解决实际问题的乐趣。实战题按难度分为3个级别，即★、★★和★★★，分别对应简单、中等和困难级别。书中绝大部分实战题和全部在线编程题选自力扣中国网站，该网站是全球领先的面向社会大众的在线编程学习平台，教师和学生免费注册后可以在该平台上进行实训和交流学习。

3. 教学资源

为了方便教师教学和学生学习，本书提供了全面、丰富的教学资源。配套教学资源包括的内容如下。

(1) 教学PPT： 提供全部教学内容的精美PPT课件，共计1017页，供任课教师在教学中使用。

(2) 源程序代码： 所有源代码按章组织，例如ch3文件夹存放第3章的源代码，其中perm．py为求全排列的源代码。

(3) “算法设计与分析”课程教学大纲和电子教案： 包含教学目的、课程内容和学时分配(44学时)，以及各章的课程思政要点，每课时的教学内容安排。

(4) “算法设计与分析”实验课程教学大纲： 包含课程介绍、教学目的、实验基本要求与方式、实验报告、实验内容与学时分配(15~21学时)，以及推荐的在线编程题目。

（5） 本书大部分知识点配套了教学视频，视频采用微课碎片化形式组织，总时长超过19小时。

（6） 本书配套在线题库，主要包含单选题和填空题，总计超过500道，并提供习题答案。


资源下载提示

课件等资源： 扫描封底的“图书资源”二维码，在公众号“书圈”下载。

素材（源码）等资源： 扫描目录上方的二维码下载。

在线自测题： 扫描封底的作业系统二维码，再扫描自测题二维码，可以在线做题及查看答案。

微课视频： 扫描封底的文泉云盘防盗码，再扫描书中相应章节的视频讲解二维码，可以在线学习。





本书的出版得到武汉大学计算机学院核心课程建设项目的资助和清华大学出版社魏江江分社长的全力支持，王冰飞老师给予精心编辑，力扣中国网站提供了无私的帮助，在编写中河南工程学院张天伍、湖南涉外经济学院邹竞、百色学院牛思先等老师提供了具有建设性的建议，编者在此一并表示衷心的感谢。尽管编者不遗余力，但由于水平所限，书中仍存在不足之处，敬请广大教师和同学批评指正。


编者

2024年8月