算法设计与分析王红梅电子计算机算法设计高等学校教材

书名：	算法设计与分析（3版）
出版社：	清华大学出版社
出版日期	2022
ISBN号：	9787302594390

本书将经典问题和算法设计技术结合，以读者容易理解和接受的方式，系统介绍了算法设计技术，包括模拟法、递推法、蛮力法、分治法、减治法、贪心法、动态规划法、深度优先搜索、广度优先搜索、回溯法、A*算法、限界剪枝法、近似算法、概率算法和智能算法；同时以通俗易懂的方式，系统介绍了算法分析技术，包括算法的时间复杂度分析、空间复杂度分析、优算法、确定性算法、非确定性算法、P类问题、NP类问题和NP完全问题。所有问题都用伪代码给出了算法描述，并提供了C++语言程序源码，且在C++语言的典型编程环境下调试通过。

本书案例丰富，叙述清晰，深入浅出，结合应用，符合算法学习者的认知规律，可作为高等院校计算机专业本科和研究生学习算法类课程的教材，适合准备参加程序设计竞赛（NOIP或ACM）却无从下手的学生，也特别适合算法爱好者学习参考。

王红梅，女，53岁，三级教授，硕士生导师，省级教学名师，省级教学团队“算法与程序设计”带头人，从事计算机专业教学工作24年，精品课“计算机学科概论”、课程“数据结构”负责人，出版了《数据结构（C++版）》、《计算机学科概论》、《程序设计基础》、《算法设计与分析》等教材，均被评为“十二五”规划教材，《数据结构（C++版）》推荐参评首批优秀教材，获省级教学成果奖一等奖1项、二等奖2项、三等奖2项，发表学术论文20余篇。

一篇基 础 知 识

1章算法设计基础3

1.1什么是算法3

1.1.1算法的定义3

1.1.2算法的描述方法4

1.1.3算法在问题求解中的地位6

1.2什么是好算法6

1.2.1如何评价算法6

1.2.2效率——算法的核心和灵魂7

1.3为什么要学习和研究算法8

1.3.1算法研究是推动计算机技术发展的关键8

1.3.2算法训练能够提高计算思维能力8

1.3.3程序员必须要学习算法吗9

1.4如何设计算法9

1.4.1基本的数据结构9

1.4.2重要的问题类型11

1.4.3算法设计的一般过程13

1.5拓展与演练14

1.5.1算法研究与图灵奖14

1.5.2代码优化技巧15

实验1大公约数17

习题1182章算法分析基础19

2.1算法的时间复杂度分析19

2.1.1输入规模与基本语句192.1.2算法的渐近分析21

2.1.3好、坏和平均情况22

2.1.4非递归算法的时间复杂度分析22

2.1.5递归算法的时间复杂度分析23

2.2算法的空间复杂度分析24

2.3算法的实验分析25

2.4拓展与演练26

2.4.1优算法26

2.4.2角谷猜想27

实验2排序算法的实验比较28

习题229

算法设计与分析（3版）目录二篇基本的算法设计技术

3章模拟法33

3.1概述33

3.1.1模拟法的设计思想33

3.1.2一个简单的例子: 鸡兔同笼问题33

3.2数学问题中的模拟法34

3.2.1约瑟夫环问题34

3.2.2埃拉托色尼筛法35

3.3排序问题中的模拟法37

3.3.1计数排序37

3.3.2颜色排序38

3.4拓展与演练39

3.4.1装箱问题39

3.4.2数字回转方阵41

实验3埃氏筛法的优化42

习题3424章递推法45

4.1概述45

4.1.1递推法的设计思想45

4.1.2一个简单的例子: 猴子吃桃45

4.2数学问题中的递推法46

4.2.1Fibonacci数列46

4.2.2Catalan数列46

4.3组合问题中的递推法48

4.3.1伯努利错装信封问题48

4.3.2旋转的万花筒49

4.4拓展与演练49

4.4.1整数划分49

4.4.2捕鱼知多少50

实验4杨辉三角形51

习题4515章蛮力法53

5.1概述53

5.1.1蛮力法的设计思想53

5.1.2一个简单的例子: 百元买百鸡问题54

5.2查找问题中的蛮力法54

5.2.1顺序查找54

5.2.2串匹配问题56

5.3排序问题中的蛮力法61

5.3.1选择排序61

5.3.2起泡排序62