【现货速发】算法设计(C++版)

关于本书

根据作者多年教学经验及实践，充分考虑教学难度和授课学时安排，本书在
《算法设计与分析——基于C 编程语言的描述》
的基础上，删减了穷举搜索、深度优先搜索、宽度优先搜索和线性规划问题等内容，整合精简了数论算法和计算几何算法。本书本着“易理解，重实用”的指导思想，以掌握算法设计与分析的基本概念和方法、拓展学生专业知识结构为宗旨，按照“算法思想—算法设计—构造实例—算法描述—算法分析—C 实战”的思路组织
内容，详细讲述了多种经典算法设计策略。纵观全书，这里并没有创造出任何新的算法，因为作者仅仅是希望通过对经典算法的讲解，把算法设计中基础且重要的内容用更清晰的思路、更直观的形式展现给读者。

本书结构

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

第1章算法概述，主要介绍了算法的基本概念与描述方式、算法设计的一般过程、算法分析方法及递归等。

第2~5章介绍经典的算法设计策略： 贪心算法、分治算法、动态规划算法、回溯算法及分支限界算法。每种算法设计策略均按照算法思想、算法设计、构造实例、算法描述、算法分析、C 实战的思路来组织。

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

第7章网络流算法，着重讲述网络流的基本概念及理论、求最大网络流的增广路算法、求最小费用最大流的消圈算法。

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

本书特点

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

本书内容精炼，算法设计步骤清晰，实例构造详尽，算法描述清楚，源码完整，阅读材料丰富，易教、易学，适合高等学校计算机及其相关专业的学生、编程爱好者、各类想从事计算机编程工作的专业或非专业人士阅读。通过本书，读者一方面可以学习到基本的算法设计策略和分析方法； 另一方面，还可以对当今流行算法和算法界的大师有所了解。

本书配套资源丰富，包括教学大纲、教学课件、微课视频、程序代码、实验指导、测试题库等。

授课方法

1. 线上线下混合式教学

利用随书提供的微课视频和测试题库，教师可以布置线上学习任务，检测线上学习效果。线下课堂基于线上学习的情况，有针对性地答疑解惑，采用参与式学习策略，比如问题驱动、任务驱动等教学方法，教师引导，学生充分思考、讨论，寻求问题答案，完成课堂任务。

2. 注重运用前驱课程基本知识、基本原理

“算法”课程与“数学”“程序设计基础”“数据结构”等前驱课程紧密联系。在讲授本课程时，针对要解决的问题： 
①要求学生审清题意，明确问题给定的已知数据、约束条件和求解目标； ②运用数学知识，引入数学符号表达已知数据、约束条件及求解目标，构建数学模型； ③训练计算思维，要求学生思考、讨论数学模型中的符号如何存储到计算机中，即采用什么数据结构存储数学模型中涉及的各种符号； ④选择贪心、分治、动态规划、搜索等一种或多种算法设计策略； ⑤分组任务，要求各小组根据选定的数据结构和算法策略设计求解问题的算法步骤，然后各组分享各自的设计成果，最后教师总结、追问引发更深层的思考； ⑥课下任务，以作业的形式，借助实践教学平台（如头歌）或刷题平台（如洛谷、力扣），选用各自擅长的程序设计语言，将课堂上设计的算法翻译成程序，完成实战训练。

3. 注重创新意识、创新精神、创新思维的训练

“算法”课程应注重应用创新和技术创新，在分析问题求解的思想、方法的基础上，从数据结构、算法设计策略、编程语言、具体操作等方面分析现有方法的优势与不足，发挥现有方法本身的优势，举一反三，创新应用； 针对现有方法自身的不足，开动脑筋，不断创新、创造，寻求其他更好的求解方法，让学生认识到人人可以创新，时时可以创新，处处可以创新。

4. 思政育人、价值塑造

“算法”课程中讲解的策略、思想、方法是人类智慧的结晶，蕴含着丰富的科学思想、技术创新、中华优秀传统文化。教师传道授业解惑时，通过算法名师、技术革新、工程伦理、前沿技术等揭示算法本身的思政属性，把知识传授、能力培养、价值塑造映射到教学的每个环节，实现“课程承载思政，思政寓于课程”的有机统一。通过潜移默化、循循善诱的方式，在不经意中实现“润物细无声”的育人目标。“算法”课程思政育人体系如下，仅供授课教师参考。

另外，要说明一下，书中出现的log均是以2为底的对数。

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

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

编者
2023年12月

本书是一本注重理论联系实践，系统介绍算法设计方法、分析技巧和C 编程实战的著作。本着“易理解，重实用”的指导思想，结合多年的教学经验，以算法设计策略为主线，沿着“算法思想——算法设计——构造实例——算法描述——算法分析——C 实战”的思路来组织学习内容，主要包括：算法概述、贪心算法、分治算法、动态规划、回溯算法及分支限界算法、随机化算法、网络流算法和NP完全理论等八章内容。为突出教材的可读性、可用性及前沿性，每章增设了学习目标、阅读材料及习题解析。配套资源包括实验指导书、大纲、PPT课件、经典案例源代码、微课视频等内容。适合作为计算机类及相关专业的本科生教材，也可供工程技术人员和自学读者学习参考，还适合作为程序设计大赛爱好者的参考用书。

王秋芬：一位具有近20年一线教学经验的教育工作者，主讲算法设计与分析、操作系统原理、数据结构、Linux操作系统等课程。致力于算法、操作系统和智能计算等领域的研究，主持或参与了10余项重要课题，并发表了20多篇学术论文，获国家发明专利4项。此外，还出版了《算法设计与分析》、《算法设计艺术》、《算法设计与分析——Python版》、《算法设计与分析——基于C 编程语言的描述》和《Flash CS5 中文版基础教程》等5部著作，为国家和社会的发展做出了贡献。

第1章算法概述

1.1算法的基本概念

1.1.1学习算法的重要性

1.1.2算法的定义及特性

1.1.3算法的描述方式

1.2算法设计的一般过程

1.3算法分析

1.3.1算法分析的概念

1.3.2时间复杂性

1.3.3空间复杂性

1.3.4算法渐进复杂性

1.3.5算法复杂性的权衡考虑

1.4递归

1.4.1认知递归

1.4.2n的阶乘

1.4.3排列问题

1.4.4最大公约数

1.4.5递归算法的复杂性分析

拓展知识： 算法界十大名师简介

本章习题

第2章贪心算法

2.1贪心算法概述

2.1.1贪心算法的基本思想

2.1.2贪心算法的基本要素

2.1.3贪心算法的解题步骤及算法设计模式

2.2会场安排问题

2.3单源最短路径问题

2.4哈夫曼编码

2.5最小生成树

2.5.1Prim算法

2.5.2Kruskal算法

2.5.3两种算法的比较

拓展知识： 遗传算法

本章习题

第3章分治算法

3.1分治算法概述

3.1.1分治算法的基本思想

3.1.2分治算法的解题步骤

3.2二分查找

3.3循环赛日程表

3.4合并排序

3.5快速排序

3.6最接近点对问题

拓展知识： 禁忌搜索算法

本章习题

第4章动态规划算法

4.1动态规划算法概述

4.1.1动态规划算法的基本思想

4.1.2动态规划算法的解题步骤

4.1.3动态规划算法的基本要素

4.2矩阵连乘问题

4.3凸多边形最优三角剖分问题

4.4最长公共子序列问题

4.5加工顺序问题

4.601背包问题

4.7最优二叉查找树

拓展知识： 模拟退火算法

本章习题

第5章回溯算法及分支限界算法

5.1回溯算法

5.1.1回溯算法的算法框架及思想

5.1.2子集树

5.1.3排列树

5.1.4满m叉树

5.2分支限界算法

5.2.1分支限界算法的基本思想

5.2.201背包问题

5.2.3旅行商问题

5.2.4布线问题

5.2.5分支限界算法与回溯算法的比较

拓展知识： 蚁群算法

本章习题

第6章随机化算法

6.1随机化算法概述

6.1.1随机化算法的类型及特点

6.1.2随机数发生器

6.2数值随机化算法

6.2.1计算π值的问题及分析

6.2.2计算定积分

6.3蒙特卡洛算法

6.3.1主元素问题

6.3.2素数测试

6.4拉斯维加斯算法

6.4.1整数因子分解问题

6.4.2n皇后问题

6.5舍伍德算法

6.5.1随机快速排序

6.5.2线性时间选择问题

拓展知识： 粒子群优化算法

本章习题

第7章网络流算法

7.1最大网络流

7.1.1基本概念

7.1.2增广路算法

7.1.3最大网络流的变换与应用

7.2最小费用最大流

7.2.1基本概念

7.2.2消圈算法

7.2.3最小费用最大流的变换与应用

拓展知识： 捕食搜索算法

本章习题

第8章NP完全理论

8.1易解问题和难解问题

8.2P类问题和NP类问题

8.2.1P类问题

8.2.2NP类问题

8.2.3P类问题和NP类问题的关系

8.3NP完全问题

8.3.1多项式变换技术

8.3.2典型的NP完全问题

8.4NP完全问题的近似算法

8.4.1顶点覆盖问题

8.4.2装箱问题

8.4.3旅行商问题

8.4.4集合覆盖问题

拓展知识： DNA计算

本章习题

本书是一本注重理论联系实践，系统介绍算法设计方法、分析技巧和C 编程实战的著作。本着“易理解，重实用”的指导思想，结合多年的教学经验，以算法设计策略为主线，沿着“算法思想——算法设计——构造实例——算法描述——算法分析——C 实战”的思路来组织学习内容，主要包括：算法概述、贪心算法、分治算法、动态规划、回溯算法及分支限界算法、随机化算法、网络流算法和NP完全理论等八章内容。为突出教材的可读性、可用性及前沿性，每章增设了学习目标、阅读材料及习题解析。配套资源包括实验指导书、大纲、PPT课件、经典案例源代码、微课视频等内容。适合作为计算机类及相关专业的本科生教材，也可供工程技术人员和自学读者学习参考，还适合作为程序设计大赛爱好者的参考用书。

王秋芬：一位具有近20年一线教学经验的教育工作者，主讲算法设计与分析、操作系统原理、数据结构、Linux操作系统等课程。致力于算法、操作系统和智能计算等领域的研究，主持或参与了10余项重要课题，并发表了20多篇学术论文，获国家发明专利4项。此外，还出版了《算法设计与分析》、《算法设计艺术》、《算法设计与分析——Python版》、《算法设计与分析——基于C 编程语言的描述》和《Flash CS5 中文版基础教程》等5部著作，为国家和社会的发展做出了贡献。

李永华 北京邮电大学信息与通信工程学院教授

有两种思想像宝石一样熠熠生辉一一微积分和算法。微积分造就了现代科学，算法造就了现代世界。《算法设计(C 版)》系统讲解了贪心算法、分治算法、动态规划算法、回溯算法及分支限界算法、随机化算法、网络流算法等多种经典算法，并提供遗传算法、粒子群算法等智能算法的拓展知识。本书内容全面，充分展示了运用数学、数据结构、程序设计语言求解问题的内在联系，能帮助读者深入理解算法，并使其能迅速动手进行编程实战。

叶志伟 湖北工业大学计算机学院教授

有计算的地方，就有算法的身影。从网上购物到出行规划，从学习工作到休闲娱乐，算法无所不在。《算法设计(C 版)》的作者结合自己十多年算法设计的教学实践经验，由浅入深地讲解了经典算法理论及设计方法，并提供了将理论付诸实践的程序源码，具有很高的学习价值。

韩道军 河南大学计算机与信息工程学院教授，河南省教学名师

《算法设计(C 版)》涵盖了算法思想剖析及C 编程实战，强化从理论分析到实践演练的具体操作方法，注重工科思维训练与提升。本书借助经典算法实例演示算法的运行过程，帮助读者深入理解算法原理及实际应用，同时配套相应的C 程序源码帮助读者学会算法实现。本书对读者学习算法设计具有很高的参考价值，有助于培养读者解决复杂工程问题的能力。

关东升 北京智捷课堂CTO，高级架构师，畅销IT图书作家

从辗转相除法到割圆术，从算盘到电子计算机，算法在人类文明发展中始终扮演着重要角色，《算法设计(C 版)》侧重用实例演示经典算法的运行，用C 编程语言展示实现细节和技巧，打造真正的从理论到实践的具体路线，形象直观，易学易懂，具有很高的参考价值。