正版 算法设计与分析:基于计算教学论的解析 段会川等编著 电子工

第 1 章 算法及其可视化教学支持系统 ．．．．．．．．．．．． 1

初识算法：Euclid GCD 算法 ．．．．．．．．．．．．．． 1

1．1．1 GCD 及因子分解方法 ．．．．．．．．．．．．．． 1

1．1．2 Euclid GCD 算法 ．．．．．．．．．．．．．．．．．．．．．．． 3

算法的定义 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 3

1．2．1 算法是一种求解问题的

科学方法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 4

1．2．2 算法的克努特定义．．．．．．．．．．．．．．．．．．．． 5

1．2．3 算法的图灵机定义．．．．．．．．．．．．．．．．．．．． 6

算法的描述方法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8

1．3．1 算法的自然语言描述方法 ．．．．．．．． 8

1．3．2 算法的流程图描述方法 ．．．．．．．．．．．． 8

1．3．3 算法的伪代码描述方法 ．．．．．．．．．．．． 9

1．3．4 算法的现代版 C++描述方法 ．．． 10

1．3．5 设计算法求解问题的

基本过程 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 10

可视化算法学习的支持工具．．．．．．．．．．．．． 12

1．4．1 CAAIS 的基本界面及其

功能 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 12

1．4．2 算法 CD-AV 演示的基本

操作 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 13

使用现代版 C++进行算法实验 ．．．．．．．． 15

1．5．1 现代版 C++的算法实验

环境建议 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 15

1．5．2 算法的现代版 C++实现

方式――以 Euclid GCD

算法为例 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 16

算法国粹――《九章算术》中的

二进制 GCD 算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 17

1．6．1 《九章算术》中的更相减

损术――最早的二进制

GCD 算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 17

1．6．2 现代版的二进制 GCD 算法 ．．．． 18

习题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 19

参考文献 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 20

第 2 章 算法的穷举设计方法 ．．．．．．．．．．．．．．．．．．．．．．．．．． 22

穷举算法设计基础 ．．．．．．．．．．．．．．．．．．．．．．．．．．．． 22

穷举算法设计示例 ．．．．．．．．．．．．．．．．．．．．．．．．．．．． 23

2．2．1 百钱买百鸡问题算法设计 ．．．．． 23

2．2．2 素性测试的试除算法设计 ．．．．． 26

2．2．3 顺序搜索算法设计及 CD-AV

演示 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 28

2．2．4 洗牌算法设计及 CD-AV 演示 29

伪随机数发生器及其在算法实验

中的应用 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 31

2．3．1 生成伪随机数的线性同余法 ．．． 31

2．3．2 传统 C 语言标准库中的

伪随机函数及其应用 ．．．．．．．．．．．．． 32

2．3．3 现代版 C++标准库中的

伪随机函数及其应用 ．．．．．．．．．．．．． 33

2．4 算法国粹――图灵奖获得者姚期智

院士的伪随机数理论 ．．．．．．．．．．．．．．．．．．．．．．．． 34

2．4．1 姚期智院士密码学安全的

伪随机数理论 ．．．．．．．．．．．．．．．．．．．．．．．．． 35

2．4．2 LCG 不是密码学安全的 ．．．．．．．． 35

2．4．3 Java JDK 提供的密码学

安全的伪随机数发生器 ．．．．．．．．． 37

习题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 39

参考文献 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 40

第 3 章 算法复杂度分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 42

算法复杂度分析基础 ．．．．．．．．．．．．．．．．．．．．．．．． 42

3．1．1 算法的输入规模及复杂度

计量 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 42

3．1．2 算法的最好、最坏和平均

情况复杂度 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 43

算法复杂度的渐近分析方法 ．．．．．．．．．．．． 45

3．2．1 算法的渐近复杂度及其记法 ． 46

3．2．2 常见的算法复杂度阶及其

关系 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 51

算法设计与分析――基于计算教学论的解析

- VIII -

3．2．3 算法复杂度渐近分析的

基本范型 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 53

大整数算术运算的复杂度 ．．．．．．．．．．．．．．．． 55

3．3．1 二进制数的竖式算术运算的

复杂度 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 55

3．3．2 大整数的多精度表示 ．．．．．．．．．．．．．． 57

3．3．3 多精度整数算术运算的

复杂度 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 57

Euclid GCD 算法的复杂度分析 ．．．．．．．． 59

3．4．1 Fibonacci 数列及其通项的

闭式解 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 59

3．4．2 Euclid GCD 算法复杂度的

详细分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 62

算法复杂度的平摊分析方法．．．．．．．．．．．．． 64

3．5．1 平摊分析方法概述．．．．．．．．．．．．．．．．．． 64

3．5．2 Fibonacci 堆的基本操作及其

复杂度的平摊分析．．．．．．．．．．．．．．．．．． 66

算法复杂度的实验分析法 ．．．．．．．．．．．．．．．． 70

3．6．1 算法复杂度实验分析的

必要性和基本过程．．．．．．．．．．．．．．．．．． 70

3．6．2 算法复杂度的实验分析法

示例 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 72

问题的复杂度 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 73

3．7．1 问题的复杂度概述．．．．．．．．．．．．．．．．．． 73

3．7．2 基于比较的排序问题的

复杂度 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 74

算法国粹――姚期智院士的通信

复杂性理论 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 76

3．8．1 通信复杂性的问题定义 ．．．．．．．．．． 76

3．8．2 通信复杂性理论的基本成果．．．． 77

习题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 80

参考文献 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 81

第 4 章 算法的递归设计方法 ．．．．．．．．．．．．．．．．．．．．．．．．．． 84

递归算法的普适性及其理论内涵 ．．．．． 84

4．1．1 递归算法的基本特性及实例 ．．．． 84

4．1．2 递归是一种普适的算法表达

方法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 86

子集遍历问题的递归穷举算法 ．．．．．．．．． 88

4．2．1 子集遍历问题及其递归穷举

算法设计 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 88

4．2．2 现代版 C++实现与 CD-AV

演示设计 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 90

全排列遍历问题的递归穷举算法 ．．．． 93

4．3．1 全排列遍历问题及其递归

穷举算法设计 ．．．．．．．．．．．．．．．．．．．．．．．．． 93

4．3．2 现代版 C++实现与 CD-AV

演示设计 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 96

0-1 背包问题及其递归穷举算法 ．．．．．． 98

4．4．1 0-1 背包问题的定义及

解空间分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 99

4．4．2 0-1 背包问题的递归穷举

算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 100

TSP 问题及其递归穷举算法 ．．．．．．．．．． 101

4．5．1 TSP 问题的定义及解空间

分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 101

4．5．2 TSP 问题的递归穷举算法 ．．． 103

栈框架及将递归算法转换为迭代

算法的方法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 105

4．6．1 函数调用的栈框架 ．．．．．．．．．．．．．．． 105

4．6．2 将递归算法转换为迭代

算法的方法 ．．．．．．．．．．．．．．．．．．．．．．．．．．． 107

算法国粹――管梅谷教授的

中国邮递员问题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 111

4．7．1 CPP 与欧拉回路 ．．．．．．．．．．．．．．．．．．．． 111

4．7．2 CPP 的求解思路与算法 ．．．．．．．． 112

习题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 114

参考文献 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 116

第 5 章 基于比较的排序算法 ．．．．．．．．．．．．．．．．．．．．．．．．． 118

冒泡排序算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 118

5．1．1 基本思想、伪代码与复杂度

分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 118

5．1．2 现代版 C++实现 ．．．．．．．．．．．．．．．．．．． 120

5．1．3 CD-AV 演示设计 ．．．．．．．．．．．．．．．．．． 121

插入排序算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 122

5．2．1 基本思想、伪代码与复杂度

分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 123

5．2．2 现代版 C++实现 ．．．．．．．．．．．．．．．．．．． 125

5．2．3 CD-AV 演示设计 ．．．．．．．．．．．．．．．．．． 125

堆排序算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 126

5．3．1 二叉堆的理论及相关算法 ．．． 127

目录

- IX -

5．3．2 基本思想、伪代码与复杂度

分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 131

5．3．3 现代版 C++实现 ．．．．．．．．．．．．．．．．．．． 133

5．3．4 CD-AV 演示设计 ．．．．．．．．．．．．．．．．．． 133

5．3．5 优先队列简介 ．．．．．．．．．．．．．．．．．．．．．．． 136

算法国粹――π 值计算方法 ．．．．．．．．．．．． 137

5．4．1 刘徽关于 π 值的“割圆术”

计算方法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 137

5．4．2 祖冲之的 π 值计算成果 ．．．．．．．． 138

5．4．3 π 值的近现代计算方法和

计算成果 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 138

习题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 139

参考文献 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 140

第 6 章 算法的分治设计方法 ．．．．．．．．．．．．．．．．．．．．．．．． 141

分治法基础 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 141

6．1．1 分治法概述 ．．．．．．．．．．．．．．．．．．．．．．．．．．． 141

6．1．2 二分搜索算法 ．．．．．．．．．．．．．．．．．．．．．．． 142

Karatsuba 乘法算法 ．．．．．．．．．．．．．．．．．．．．．．．．． 144

6．2．1 大整数乘法的朴素分治

算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 144

6．2．2 大整数乘法的 Karatsuba

算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 145

归并排序算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 147

6．3．1 基本思想、伪代码与复杂度

分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 147

6．3．2 现代版 C++实现与 CD-AV

演示设计 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 150

快速排序算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 152

6．4．1 基本思想、伪代码与复杂度

分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 152

6．4．2 现代版 C++实现与 CD-AV

演示设计 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 155

大师定理及其应用 ．．．．．．．．．．．．．．．．．．．．．．．．．． 156

6．5．1 大师定理简介 ．．．．．．．．．．．．．．．．．．．．．．． 157

6．5．2 大师定理的应用 ．．．．．．．．．．．．．．．．．．． 157

算法国粹――贾宪的增乘开平

方法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 158

6．6．1 增乘开平方法详解．．．．．．．．．．．．．．．． 158

6．6．2 近代开平方法――牛顿

迭代法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 160

习题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 161

参考文献 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 163

第 7 章 算法的动态规划设计方法 ．．．．．．．．．．．．．．．． 164

DP 方法概述 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 164

7．1．1 Fibonacci 数的 DP 计算 ．．．．．．． 164

7．1．2 DP 方法的基本思想及其所

求解问题的两个重要特征 ．．． 166

7．1．3 DP 算法设计的基本步骤 ．．．．． 167

两个字符串间的编辑距离问题的

DP 算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 168

7．2．1 DP 方程及算法设计 ．．．．．．．．．．．．． 168

7．2．2 现代版 C++实现与复杂度

分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 172

7．2．3 CD-AV 演示设计 ．．．．．．．．．．．．．．．．．． 174

矩阵链相乘问题的 DP 算法 ．．．．．．．．．．． 176

7．3．1 DP 方程及算法设计 ．．．．．．．．．．．．． 176

7．3．2 现代版 C++实现与复杂度

分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 179

7．3．3 CD-AV 演示设计 ．．．．．．．．．．．．．．．．．． 181

0-1 背包问题的 DP 算法 ．．．．．．．．．．．．．．．．． 184

7．4．1 DP 方程及算法设计 ．．．．．．．．．．．．． 184

7．4．2 现代版 C++实现与复杂度

分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 187

7．4．3 CD-AV 演示设计 ．．．．．．．．．．．．．．．．．． 189

TSP 问题的 DP 算法 ．．．．．．．．．．．．．．．．．．．．．．． 191

7．5．1 DP 方程及算法设计 ．．．．．．．．．．．．． 191

7．5．2 现代版 C++实现与复杂度

分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 196

7．5．3 CD-AV 演示设计 ．．．．．．．．．．．．．．．．．． 200

算法国粹――秦九韶的正负开方术

与最优多项式计算算法 ．．．．．．．．．．．．．．．．．． 202

7．6．1 秦九韶的正负开方术 ．．．．．．．．．．． 202

7．6．2 秦九韶的最优多项式计算

算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 205

习题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 206

参考文献 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 207

第 8 章 算法的贪心设计方法 ．．．．．．．．．．．．．．．．．．．．．．．． 209

贪心法概述 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 209

算法设计与分析――基于计算教学论的解析

- X -

8．1．1 找零钱问题、局部最优与

全局最优 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 209

8．1．2 贪心法的基本特征．．．．．．．．．．．．．．．． 211

图中单源最短路径的 Dijkstra

算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 213

8．2．1 最短路径的最优子结构

性质 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 213

8．2．2 Dijkstra 算法的基本思想与

贪心选择策略 ．．．．．．．．．．．．．．．．．．．．．．． 214

8．2．3 现代版 C++实现与复杂度

分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 215

8．2．4 CD-AV 演示设计 ．．．．．．．．．．．．．．．．．． 219

图的最小生成树的 Prim 算法 ．．．．．．．．． 222

8．3．1 最小生成树的最优子

结构性质 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 222

8．3．2 Prim 算法的基本思想与

贪心选择策略 ．．．．．．．．．．．．．．．．．．．．．．． 223

8．3．3 现代版 C++实现与 CD-AV

演示设计 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 224

图的最小生成树的 Kruskal 算法 ．．．． 225

8．4．1 Kruskal 算法的基本思想与

贪心选择策略 ．．．．．．．．．．．．．．．．．．．．．．． 225

8．4．2 不相交集合及其 Union 与

Find 操作 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 227

8．4．3 现代版 C++实现与复杂度

分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 228

8．4．4 CD-AV 演示设计 ．．．．．．．．．．．．．．．．．． 231

Huffman 编码算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．． 233

8．5．1 变长编码、前缀编码及其

满二叉树表示 ．．．．．．．．．．．．．．．．．．．．．．． 233

8．5．2 Huffman 编码算法的基本

思想与复杂度分析．．．．．．．．．．．．．．．． 235

8．5．3 最优前缀编码的最优子结构

性质与 Huffman 编码算法的

贪心选择策略 ．．．．．．．．．．．．．．．．．．．．．．． 236

8．5．4 现代版 C++实现 ．．．．．．．．．．．．．．．．．．． 238

8．5．5 CD-AV 演示设计 ．．．．．．．．．．．．．．．．．． 240

算法国粹――姚期智院士的

最小生成树算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 242

8．6．1 算法描述 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 242

8．6．2 复杂度分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．． 244

习题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 244

参考文献 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 245

第 9 章 算法的回溯设计方法 ．．．．．．．．．．．．．．．．．．．．．．．． 247

图的 DFS 算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 247

9．1．1 图及其表示 ．．．．．．．．．．．．．．．．．．．．．．．．．．． 247

9．1．2 图的 DFS 算法、DFS 树及

拓扑排序 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 248

9．1．3 现代版 C++实现 ．．．．．．．．．．．．．．．．．．． 251

9．1．4 CD-AV 演示设计 ．．．．．．．．．．．．．．．．．． 252

回溯法概述 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 254

9．2．1 回溯法基础 ．．．．．．．．．．．．．．．．．．．．．．．．．．． 254

9．2．2 问题解的形态与回溯

算法的基本流程及相

关的节点状态 ．．．．．．．．．．．．．．．．．．．．．．． 257

0-1 背包问题的回溯算法 ．．．．．．．．．．．．．．．． 258

9．3．1 约束条件和限界条件设计 ．．． 259

9．3．2 0-1 背包问题回溯算法的

伪代码及运行实例 ．．．．．．．．．．．．．．． 260

N-皇后问题的回溯算法 ．．．．．．．．．．．．．．．．．． 263

9．4．1 N-皇后问题的定义、解空间

分析及约束条件设计 ．．．．．．．．．．． 263

9．4．2 现代版 C++实现 ．．．．．．．．．．．．．．．．．．． 265

9．4．3 CD-AV 演示设计 ．．．．．．．．．．．．．．．．．． 266

K-着色问题的回溯算法 ．．．．．．．．．．．．．．．．．． 268

9．5．1 图着色问题的定义与分析 ．．． 268

9．5．2 K-着色问题的回溯算法

设计 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 270

9．5．3 现代版 C++实现 ．．．．．．．．．．．．．．．．．．． 270

9．5．4 CD-AV 演示设计 ．．．．．．．．．．．．．．．．．． 272

算法国粹――线性方程组的

消元求解法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 274

9．6．1 中国古代数学家对线性

方程组消元求解法的探索 ．．． 274

9．6．2 线性方程组求解的高斯

消元法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 276

习题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 277

参考文献 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 278

第 10 章 算法的分支限界设计方法 ．．．．．．．．．．．．．． 280

目录

- XI -

图的广度优先搜索 ．．．．．．．．．．．．．．．．．．．．．．．． 280

10．1．1 图的 BFS 算法 ．．．．．．．．．．．．．．．．．．．． 280

10．1．2 现代版 C++实现 ．．．．．．．．．．．．．．．．． 282

10．1．3 CD-AV 演示设计 ．．．．．．．．．．．．．．．． 282

分支限界法概述 ．．．．．．．．．．．．．．．．．．．．．．．．．．．． 283

10．2．1 分支限界算法设计的

基本要领 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 283

10．2．2 两类分支限界法 ．．．．．．．．．．．．．．．．． 284

0-1 背包问题的分支限界算法 ．．．．．． 286

10．3．1 约束条件和限界函数设计．．．． 286

10．3．2 现代版 C++实现 ．．．．．．．．．．．．．．．．． 287

10．3．3 CD-AV 演示设计 ．．．．．．．．．．．．．．．． 289

TSP 问题的分支限界算法 ．．．．．．．．．．．．． 292

10．4．1 TSP 问题与哈密尔顿回路 ．．． 292

10．4．2 费用矩阵及其归约矩阵上的

哈密尔顿回路 ．．．．．．．．．．．．．．．．．．．．． 293

10．4．3 基于费用矩阵归约的 TSP

问题的分支限界条件设计．．． 295

10．4．4 现代版 C++实现 ．．．．．．．．．．．．．．．．． 299

10．4．5 CD-AV 演示设计 ．．．．．．．．．．．．．．．． 303

算法国粹――内插法与招差术 ．．．．． 306

10．5．1 中国古代数学家对内插法与

招差术的探索 ．．．．．．．．．．．．．．．．．．．．． 306

10．5．2 现代插值法 ．．．．．．．．．．．．．．．．．．．．．．．．． 309

习题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 311

参考文献 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 312

第 11 章 RSA 算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 313

公钥密码学基础 ．．．．．．．．．．．．．．．．．．．．．．．．．．．． 313

11．1．1 凯撒加密 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 313

11．1．2 对称密钥体制 ．．．．．．．．．．．．．．．．．．．．．． 314

11．1．3 公钥密码学简介 ．．．．．．．．．．．．．．．．．． 315

模幂运算的反复平方算法 ．．．．．．．．．．．．． 317

11．2．1 模运算基础 ．．．．．．．．．．．．．．．．．．．．．．．．．． 317

11．2．2 模幂运算的反复平方表示与

算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 318

模同余、模的乘法逆元及扩展

Euclid GCD 算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．． 320

11．3．1 模同余的定义及其

运算性质 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 320

11．3．2 模的乘法逆元及

扩展 Euclid GCD 算法 ．．．．．．． 322

Miller-Rabin 素性测试算法 ．．．．．．．．．． 324

11．4．1 关于素数的定理 ．．．．．．．．．．．．．．．．． 324

11．4．2 费马小定理及相关的素性

测试算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 326

11．4．3 Miller-Rabin 素性测试算法

详解 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 328

RSA 算法的基本原理与实现 ．．．．．．．． 331

11．5．1 RSA 算法的基本原理 ．．．．．．．．． 331

11．5．2 现代版 C++实现 ．．．．．．．．．．．．．．．．． 333

11．5．3 CD-AV 演示设计 ．．．．．．．．．．．．．．．． 335

算法国粹――中国余数算法 ．．．．．．．．． 339

11．6．1 《孙子算经》中的中国

余数算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 339

11．6．2 秦九韶关于中国余数算法的

普适设计 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 340

11．6．3 中国余数算法的现代版 C++

实现及 CD-AV 演示设计 ．．． 341

11．6．4 中国余数算法在加快 RSA

解密运算中的应用 ．．．．．．．．．．．．． 343

习题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 345

参考文献 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 346

第 12 章 NP 理论．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 348

算法不可解的问题 ．．．．．．．．．．．．．．．．．．．．．．．． 348

12．1．1 停机问题的不可计算性 ．．．．． 348

12．1．2 希尔伯特第十问题的

不可计算性 ．．．．．．．．．．．．．．．．．．．．．．．．． 349

易解问题与难解问题、NP 理论

基础 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 350

12．2．1 易解问题与难解问题 ．．．．．．．．． 350

12．2．2 NP 理论基础 ．．．．．．．．．．．．．．．．．．．．．．． 351

NP 完全性理论 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 356

12．3．1 判定性问题的多项式

时间归约 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 356

12．3．2 通过定义证明的 NP

完全问题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 357

12．3．3 通过多项式归约证明的

NP 完全问题 ．．．．．．．．．．．．．．．．．．．．．．． 360

算法设计与分析――基于计算教学论的解析

- XII -

12．3．4 问题复杂性类间的关系 ．．．．．． 365

算法国粹――姚期智院士的百万富翁

问题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 366

12．4．1 多方安全计算简介 ．．．．．．．．．．．．．． 367

12．4．2 百万富翁问题及其

求解协议 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 368

习题 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 369

参考文献 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 370

附录：教材算法的现代版 C++实现及

计算教学论简介 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 372

附录 1-1 Euclid GCD 算法 ．．．．．．．．．．．．．．．．．．．． 372

附录 2-1 洗牌算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 373

附录 2-2 顺序搜索算法 ．．．．．．．．．．．．．．．．．．．．．．．．． 374

附录 4-1 子集遍历问题的递归穷举

算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 374

附录 4-2 全排列遍历问题的递归穷举

算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 376

附录 5-1 冒泡排序算法 ．．．．．．．．．．．．．．．．．．．．．．．．． 376

附录 5-2 插入排序算法 ．．．．．．．．．．．．．．．．．．．．．．．．． 377

附录 5-3 堆排序算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 378

附录 6-1 归并排序算法 ．．．．．．．．．．．．．．．．．．．．．．．．． 379

附录 6-2 快速排序算法 ．．．．．．．．．．．．．．．．．．．．．．．．． 380

附录 7-1 Levenshtein 编辑距离问题的

DP 算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 381

附录 7-2 矩阵链相乘问题的 DP 算法 ．．．． 384

附录 7-3 0-1 背包问题的 DP 算法 ．．．．．．． 387

附录 7-4 TSP 问题的 DP 算法 ．．．．．．．．．．．．．． 389

附录 8-1 Dijkstra 最短路径算法 ．．．．．．．．．．． 392

附录 8-2 Prim 算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 396

附录 8-3 Kruskal 算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．． 399

附录 8-4 Huffman 编码算法 ．．．．．．．．．．．．．．．．． 404

附录 9-1 图遍历的 DFS 算法 ．．．．．．．．．．．．．．． 408

附录 9-2 N-皇后问题的回溯算法 ．．．．．．．．． 410

附录 9-3 K-着色问题的回溯算法 ．．．．．．．．．． 411

附录 10-1 图的 BFS 算法 ．．．．．．．．．．．．．．．．．．．．．． 414

附录 10-2 0-1 背包问题的分支限界

算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 415

附录 10-3 TSP 问题的分支限界算法 ．．．． 420

附录 11-1 RSA 算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 426

附录 11-2 中国余数算法 ．．．．．．．．．．．．．．．．．．．．．．． 429

附录 12 计算教学论简介 ．．．．．．．．．．．．．．．．．．．．．． 431

段会川 教授，长期致力于以计算改进教和学的效率，并创立了计算教学论学说。该学说以计算的本质能力即算法化的知识表达和解析改进教与学的效率，在《算法设计与分析》和《计算机网络原理》课程中取得了很好的效果。

本教材是基于作者所创立的计算教学论编写的，是为实现教学效率显著提升而对计算教学论提出的思想、方法和工具的深广应用。本教材共12章。第1章由EuclidGCD算法引出算法的定义，并介绍基于可视化的算法学习方法，第2～5章分别介绍算法的穷举设计方法、算法复杂度分析、算法的递归设计方法和基于比较的排序算法，第6～10章分别介绍分治、动态规划、贪心、回溯和分支限界等经典的算法设计方法，第11章介绍RSA算法，第12章介绍NP理论。本教材可作为高等学校计算机科学与技术专业算法设计与分析课程的教材，也可作为计算机及相关专业研究生和科研、工程或技术人员自学算法设计与分析的参考书。