计算机动画算法与技术 第3版PDF电子书下载

第1章 引言 1

1.1 算法的定义 1

1.1.1 算法的属性 2

1.1.2 效率的定义 3

1.2 算法设计与分析举例 5

1.2.1 寻找局部高点-1D 5

1.2.2 图书管理 8

1.3 小结 10

课后习题 11

第2章 渐进分析与Python计算模型 13

2.1 引言 13

2.2 计算模型 13

2.3 算法的渐进分析 14

2.4 Python计算模型 17

2.4.1 控制流语句 17

2.4.2 数据结构 19

2.5 算法分析实例 21

2.5.1 求最大值 22

2.5.2 二分搜索 22

2.5.3 子集和问题 23

2.6 小结 24

课后习题 25

第3章 问题求解与代码优化 27

3.1 引言 27

3.2 文档比较 27

3.2.1 问题提出 27

3.2.2 算法设计 28

3.2.3 算法优化 31

3.3 拼写矫正 33

3.3.1 问题提出 33

3.3.2 算法设计 33

3.4 稳定匹配问题 36

3.4.1 问题提出 36

3.4.2 算法设计 38

3.5 小结 40

课后习题 41

第4章 递归算法与递归函数 42

4.1 引言 42

4.2 递归的组成结构 42

4.2.1 如何筹集巨款 42

4.2.2 上线与下线 44

4.3 递归算法的执行 45

4.3.1 跟踪函数的执行 47

4.4 利用递归算法求解问题 51

4.4.1 回文判断 51

4.4.2 全排列 53

4.4.3 汉诺塔问题 54

4.4.4 雪花曲线 57

4.5 递归函数的求解 58

4.5.1 替换法 59

4.5.2 主分析法 60

4.6 小结 62

课后习题 63

第5章 排序与树结构 64

5.1 引言 64

5.2 递归与排序 65

5.2.1 选择排序 65

5.2.2 插入排序 67

5.2.3 合并排序 69

5.3 二叉搜索树 72

5.3.1 BST的实现 74

5.3.2 插入新结点 75

5.3.3 BST上查找 77

5.3.4 二叉树修剪 78

5.4 堆 81

5.4.1 堆化操作 81

5.4.2 构造堆 83

5.4.3 堆排序 85

5.4.4 合并k个有序序列 86

5.5 小结 87

课后习题 88

第6章 分治算法 90

6.1 引言 90

6.2 股票的买卖 91

6.2.1 问题描述 91

6.2.2 算法设计 91

6.3 统计逆序 94

6.3.1 问题描述 94

6.3.2 算法设计 94

6.4 空间最小距离点对 97

6.4.1 问题描述 97

6.4.2 算法设计 98

6.5 寻找第k小的数 103

6.5.1 问题描述 103

6.5.2 算法设计 103

6.6 大整数乘法 107

6.6.1 问题描述 107

6.6.2 算法设计 108

6.7 小结 109

课后习题 109

第7章 图搜索算法 111

7.1 引言 111

7.2 图搜索的应用 112

7.3 图的表示 113

7.4 宽度优先搜索 114

7.4.1 宽度优先搜索算法 114

7.4.2 BFS算法分析 117

7.4.3 BFS算法应用举例 117

7.5 深度优先搜索 121

7.5.1 深度优先搜索算法 121

7.5.2 DFS算法分析 124

7.5.3 DFS应用举例 124

7.6 小结 126

课后习题 126

第8章 贪心算法 128

8.1 引言 128

8.2 硬币找零 128

8.2.1 问题描述 128

8.2.2 问题求解 129

8.2.3 最优解证明 130

8.3 间隔任务规划 130

8.3.1 问题描述 130

8.3.2 问题求解 131

8.3.3 最优解证明 133

8.4 单源最矩路径问题 134

8.4.1 Dijkstra问题 135

8.4.2 算法的正确性 136

8.4.3 算法的性能优化 137

8.5 最小生成树 139

8.5.1 Prim算法 140

8.5.2 算法实现 142

8.6 小结 145

课后习题 145

第9章 动态规划算法 147

9.1 引言 147

9.2 再遇斐波那契数 147

9.3 一维动态规划 151

9.3.1 拾捡硬币 152

9.3.2 连续子序列和的最大值 155

9.3.3 疯狂的8 157

9.3.4 文本排版 161

9.3.5 完全信息的21点 165

9.4 二维动态规划 169

9.4.1 矩阵的括号 169

9.4.2 字符串编辑距离 173

9.4.3 0-1背包问题 176

9.5 小结 179

课后习题 180

第10章 最大流算法应用 182

101 引言 182

10.2 最大流算法 182

10.2.1 Ford-Fulkerson算法 186

10.2.2 Edmond-Karp算法 187

10.3 最大流算法的应用 189

10.3.1 二向图最大匹配问题 189

10.3.2 文件传输中的不重合边问题 191

10.4 小结 193

课后习题 193

第11章 随机算法 195

11.1 引言 195

11.2 矩阵乘积结果验证 196

11.3 快速排序 198

11.3.1 根据支点数划分输入序列 199

11.3.2 选择支点数 200

11.3.3 随机快速排序 202

11.4 选择第k小的数 203

11.5 寻找最小割边 206

11.6 小结 209

课后习题 209

第12章 算法复杂度 210

12.1 引言 210

12.2 问题的分类 210

12.2.1 易解与难解 210

12.2.2 无解的问题 211

12.2.3 难解问题的证明 213

12.3 NPC问题应用 214

12.3.1 决策问题 214

12.3.2 问题的化约 215

12.3.3 NP问题 215

12.3.4 NPC问题 216

12.4 P等于NP吗 218

12.5 小结 219

课后习题 219

索引 221

代码列表 222

参考文献 226