第1章 算法与程序设计简介 1
1.1 算法与算法描述 1
1.1.1 算法 1
1.1.2 算法描述 2
1.2 算法复杂性分析 6
1.2.1 时间复杂度 6
1.2.2 空间复杂度 10
1.3 程序设计简介 11
1.3.1 算法与程序 11
1.3.2 结构化程序设计 14
习题 15
第2章 穷举与回溯 17
2.1 穷举及其应用 17
2.1.1 穷举概述 17
2.1.2 穷举应用 18
2.2 穷举设计的优化 22
2.2.1 优选穷举对象 22
2.2.2 优化穷举循环参量 23
2.2.3 精简穷举循环 27
2.3 回溯法及其描述 30
2.3.1 回溯的基本概念 30
2.3.2 回溯法描述 30
2.3.3 回溯法的效益分析 33
2.4 回溯设计应用 34
2.4.1 桥本分数式 34
2.4.2 排列组合 36
2.4.3 德布鲁金环序列 41
2.4.4 高斯皇后问题及其拓展 45
2.5 回溯设计的优化 51
习题 54
第3章 递归与分治 56
3.1 递归及其应用 56
3.1.1 递归与递归调用 56
3.1.2 递归应用 57
3.2 分治法概述 61
3.2.1 分治法基本思想 61
3.2.2 分治算法设计方法和特点 62
3.2.3 分治法的时间复杂度 64
3.3 分治法的基本应用 65
3.3.1 数据查找与排序 65
3.3.2 计数逆序排名问题 70
3.3.3 投资问题 72
3.4 消除递归 73
3.4.1 一般的递归转非递归 73
3.4.2 分治算法中的递归转化 76
习题 77
第4章 递推 79
4.1 递推概述 79
4.1.1 递推算法 79
4.1.2 递推实施步骤与描述 80
4.2 递推数列 82
4.2.1 裴波那契数列与卢卡斯数列 83
4.2.2 分数数列 85
4.2.3 幂序列 87
4.2.4 双关系递推数列 90
4.3 递推数阵 93
4.3.1 杨辉三角 93
4.3.2 折叠方阵 95
4.4 应用递推求解应用题 97
4.4.1 猴子爬山问题 98
4.4.2 整币兑零问题 100
4.4.3 整数划分问题 102
4.5 递推与递归比较 105
习题 107
第5章 贪心算法 109
5.1 贪心算法概述 109
5.2 贪心算法的理论基础 110
5.3 删数字问题 111
5.4 背包问题 112
5.4.1 0-1背包问题 112
5.4.2 可拆背包问题 113
5.5 覆盖问题 115
5.6 图的着色问题 117
5.7 遍历问题 120
5.8 最小生成树 123
5.9 哈夫曼编码 130
习题 134
第6章 动态规划 135
6.1 一般方法与求解步骤 135
6.1.1 一般方法 135
6.1.2 动态规划求解步骤 136
6.2 装载问题 137
6.3 插入乘号问题 141
6.4 0-1背包问题求解 145
6.4.1 0-1背包问题 146
6.4.2 二维0-1背包问题 151
6.5 最长子序列探索 156
6.5.1 最长非降子序列 156
6.5.2 最长公共子序列 158
6.6 最优路径搜索 161
6.6.1 点数值三角形的最优路径搜索 161
6.6.2 边数值矩形的最优路径搜索 163
6.7 动态规划与其他算法的比较 166
6.7.1 动态规划与递推比较 166
6.7.2 动态规划与贪心算法比较 166
习题 167
第7章 模拟 168
7.1 模拟概述 168
7.2 运算模拟 168
7.2.1 运算模拟描述 168
7.2.2 n个1的整除问题 170
7.2.3 尾数前移问题 172
7.2.4 阶乘与幂的计算 174
7.2.5 求圆周率π 176
7.3 随机模拟 178
7.3.1 进站时间模拟 178
7.3.2 蒙特卡罗模拟计算 179
7.3.3 模拟发扑克牌 181
7.4 操作过程模拟 183
7.4.1 洗牌 183
7.4.2 泊松分酒 185
7.4.3 模拟小孔流水 188
7.5 模拟外索夫游戏 190
习题 194
第8章 智能优化 195
8.1 模拟退火算法 195
8.1.1 物理退火过程和Metropolis准则 195
8.1.2 模拟退火算法概述 196
8.1.3 应用举例 198
8.2 遗传算法 199
8.2.1 生物的进化与遗传 200
8.2.2 遗传算法概述 200
8.2.3 遗传算法关键参数 205
8.2.4 遗传算法应用举例 206
8.3 粒子群优化算法 208
8.3.1 粒子群算法的基本结构 209
8.3.2 粒子群算法的关键参数 209
8.3.3 应用举例 210
8.4 人工神经网络 212
8.4.1 神经网络模型 213
8.4.2 神经网络学习规则 214
习题 215
第9章 并行算法简介 216
9.1 基本概念 216
9.1.1 并行计算机系统结构模型 216
9.1.2 并行计算性能评价 217
9.2 并行算法设计 219
9.2.1 SIMD共享存储模型 220
9.2.2 SIMD互连网络模型 224
9.2.3 MIMD共享存储模型 225
9.2.4 MIMD异步通信模型 229
9.3 并行程序开发 231
9.3.1 并行程序设计概念 232
9.3.2 共享存储系统并行编程 232
9.3.3 分布存储系统并行编程 238
习题 243
附录1 习题解答算法提要 244
附录2 C常用库函数 264
参考文献 267