【章名目录】
第1章　绪论 2
第2章　工之利器——编程珠玑 19
第3章　按图索骥——模拟法 42
第4章　数学归纳——递推法 54
第5章　愚公移山——蛮力法 64
第6章　分而治之——分治法 82
第7章　分而治一——减治法 101
第8章　急功近利——贪心法 119
第9章　表格收纳——动态规划法 136
第10章　深度优先搜索 158
第11章　广度优先搜索 176
第12章　给问题分类——问题的复杂性 192

【详细目录】
第1章　绪论 2
1.1　引言 2
1.1.1　引例——美妙的节奏 3
1.1.2　引例——数组循环左移问题 3
1.1.3　用计算机求解问题的一般过程 5
1.2　为什么要学习和研究算法 5
1.2.1　算法研究推动计算机技术发展 5
1.2.2　算法训练提高计算思维能力 6
1.2.3　程序员必须学习算法吗 6
1.3　算法及其描述方法 7
1.3.1　什么是算法 7
1.3.2　什么是好算法 8
1.3.3　算法的描述方法 9
1.4　算法的时间复杂度 11
1.4.1　输入规模与基本语句 11
1.4.2　算法的渐近时间 13
1.4.3　最好、最坏和平均情况 13
1.5　算法的空间复杂度 15
1.6　拓展与演练 15
1.6.1　角谷猜想 15
1.6.2　算法的实验分析 16
习题 17

第2章　工之利器——编程珠玑 19
2.1　程序设计基础 19
2.1.1　数据类型与变量 20
2.1.2　控制结构 22
2.1.3　自定义函数 24
2.2　程序设计技巧 26
2.2.1　优化代码的技巧 26
2.2.2　表示状态的技巧——标志变量 28
2.2.3　扫描数组的技巧——尺取法 29
2.3　递归简论 31
2.3.1　递归的基本法则 31
2.3.2　递归函数的性能分析 33
2.4　数据结构简论 35
2.4.1　数据结构的基本概念 35
2.4.2　基本的数据结构 35
2.4.3　数据结构的存储表示 37
2.5　拓展与演练 38
2.5.1　递归函数求数组最大值 38
2.5.2　合并数组 39
习题 39

第3章　按图索骥——模拟法 42
3.1　引言 42
3.1.1　模拟法的设计思想 43
3.1.2　引例——鸡兔同笼问题 43
3.2　数学问题中的模拟法 43
3.2.1　约瑟夫环问题 43
3.2.2　埃拉托色尼筛法 45
3.3　排序问题中的模拟法 46
3.3.1　颜色排序 46
3.3.2　计数排序 48
3.4　拓展与演练 50
3.4.1　装箱问题 50
3.4.2　数字回转方阵 51
实验　优化埃氏筛法 52
习题 52

第4章　数学归纳——递推法 54
4.1　引言 54
4.1.1　递推法的设计思想 54
4.1.2　引例——猴子吃桃 55
4.2　数学问题中的递推法 55
4.2.1　Fibonacci数列 55
4.2.2　Catalan数列 56
4.3　组合问题中的递推法 58
4.3.1　伯努利错装信封问题 58
4.3.2　旋转的万花筒 59
4.4　拓展与演练 60
4.4.1　整数划分 60
4.4.2　捕鱼知多少 61
实验　杨辉三角形 62
习题 63

第5章　愚公移山——蛮力法 64
5.1　引言 64
5.1.1　蛮力法的设计思想 64
5.1.2　引例——百钱买百鸡问题 65
5.2　查找问题中的蛮力法 66
5.2.1　顺序查找 66
5.2.2　串匹配问题 67
5.3　排序问题中的蛮力法 71
5.3.1　选择排序 71
5.3.2　起泡排序 72
5.4　图问题中的蛮力法 73
5.4.1　哈密顿回路 73
5.4.2　TSP 74
5.5　几何问题中的蛮力法 75
5.5.1　最近对问题 75
5.5.2　凸包问题 76
5.6　拓展与演练 78
5.6.1　KMP算法计算next值 78
5.6.2　0/1背包问题 79
实验　任务分配问题 80
习题 81

第6章　分而治之——分治法 82
6.1　引言 82
6.1.1　分治法的设计思想 83
6.1.2　引例——汉诺塔问题 83
6.2　排序问题中的分治法 84
6.2.1　归并排序 84
6.2.2　快速排序 86
6.3　组合问题中的分治法 89
6.3.1　最大子段和问题 89
6.3.2　棋盘覆盖问题 91
6.4　几何问题中的分治法 93
6.4.1　最近对问题 93
6.4.2　凸包问题 95
6.5　拓展与演练 97
6.5.1　扩展欧几里得算法 97
6.5.2　中国剩余定理 98
实验　Karatsuba乘法 99
习题 100

第7章　分而治一——减治法 101
7.1　引言 101
7.1.1　减治法的设计思想 101
7.1.2　引例——俄式乘法 102
7.2　查找问题中的减治法 102
7.2.1　折半查找 102
7.2.2　选择问题 104
7.3　排序问题中的减治法 106
7.3.1　插入排序 106
7.3.2　堆排序 108
7.4　组合问题中的减治法 110
7.4.1　淘汰赛冠军问题 110
7.4.2　假币问题 111
7.5　拓展与演练 112
7.5.1　两个序列的中位数 112
7.5.2　topK问题 114
实验　假币问题的复杂版本 116
习题 117

第8章　急功近利——贪心法 119
8.1　引言 119
8.1.1　贪心法的设计思想 119
8.1.2　引例——付款问题 120
8.2　数学问题中的贪心法 121
8.2.1　删数问题 121
8.2.2　埃及分数 122
8.3　图问题中的贪心法 123
8.3.1　TSP 123
8.3.2　图着色问题 125
8.4　组合问题中的贪心法 127
8.4.1　背包问题 127
8.4.2　活动安排问题 128
8.5　拓展与演练 130
8.5.1　田忌赛马 130
8.5.2　多机调度问题 132
实验　合并字符串 134
习题 134

第9章　表格收纳——动态规划法 136
9.1　引言 136
9.1.1　多阶段决策过程 137
9.1.2　动态规划法的设计思想 137
9.1.3　引例——网格上的最短路径 138
9.2　组合问题中的动态规划法 140
9.2.1　最长公共子序列问题 140
9.2.2　0/1背包问题 142
9.3　图问题中的动态规划法 144
9.3.1　多段图的最短路径 144
9.3.2　TSP 146
9.4　查找问题中的动态规划法 147
9.4.1　近似串匹配问题 147
9.4.2　最优二叉查找树 150
9.5　拓展与演练 152
9.5.1　最优性原理 152
9.5.2　数塔问题 153
实验　最大子段和问题 155
习题 155

第10章　深度优先搜索 158
10.1　纵深推进——深度优先搜索 158
10.1.1　深度优先搜索的设计思想 159
10.1.2　山洞寻宝 159
10.1.3　城堡问题 160
10.2　及时止损——回溯法 162
10.2.1　问题的解空间树 162
10.2.2　回溯法的设计思想 162
10.2.3　素数环问题 163
10.2.4　八皇后问题 165
10.2.5　图着色问题 167
10.3　拓展与演练 169
10.3.1　批处理作业调度 169
10.3.2　哈密顿回路 171
实验　0/1背包问题 173
习题 174

第11章　广度优先搜索 176
11.1　由近及远——广度优先搜索 176
11.1.1　广度优先搜索的设计思想 177
11.1.2　农夫抓牛 178
11.1.3　骑士旅行 179
11.2　向最优解前进——A*算法 181
11.2.1　A*算法的设计思想 181
11.2.2　八数码问题 182
11.2.3　多段图的最短路径 183
11.3　丢掉包袱——限界剪枝法 184
11.3.1　限界剪枝法的设计思想 184
11.3.2　0/1背包问题 185
11.3.3　TSP 186
11.4　拓展与演练 188
11.4.1　任务分配问题 188
11.4.2　限界剪枝法的关键问题 189
实验　电路布线问题 189
习题 190

第12章　给问题分类——问题的复杂性 192
12.1　问题的复杂性分类 192
12.1.1　什么是计算 193
12.1.2　可计算问题与不可计算
　问题 195
12.1.3　易解问题与难解问题 196
12.2　P类问题与NP类问题 197
12.2.1　判定问题 197
12.2.2　确定性算法与P类问题 198
12.2.3　非确定性算法与NP类问题 198
12.3　NP完全问题 199
12.3.1　问题归约 199
12.3.2　NP完全问题的定义 200
12.3.3　基本的NP完全问题 200
12.4　NP类问题的求解方法 201
12.4.1　近似算法 201
12.4.2　随机算法 203
12.5　拓展与演练 204
12.5.1　顶点覆盖问题 204
12.5.2　素数测试 205
实验　SAT问题 206
习题 206

参考文献 208