算法与程序设计

　　本书遵循“精选案例，面向设计，深入浅出，注重能力培养”的要求，以案例形式实现算法与程序设计教学，精选了穷举法、递推法、回溯法、分支限界法、递归法、分治法、贪心算法、动态规划法和随机算法等常用算法进行讲解，并给出了使用各算法求解的典型案例。对于每一个案例的求解，从问题提出到算法设计、从程序实现到算法复杂度分析，环环相扣，融为一体，力求理论与实际相结合、算法与程序相统一，突出算法在解决实际问题中的核心地位与引导作用。本书中的所有案例均给出算法设计要点与完整的C语言或者C++语言程序代码（均在VC++ 6.0上编译通过）。为方便教学，每章都附有习题，同时提供教学课件、习题答案、源代码等配套资源，读者可登录华信教育资源网（www.hxedu.com.cn）免费下载使用。本书既可作为高等院校计算机专业相关课程的教材，也可供IT从业人员和计算机编程爱好者参考使用。

　　杨建英，硕士毕业于华南师范大学人工智能与模糊识别专业，目前在山西大学软件学院任教。山西CCF大会分会委员，山西大学计算机协会指导教师，山西大学软件应用协会指导教师，山西大学ACM-ICPC算法队指导老师，山西大学精英之英竞赛与科技创新团队指导老师。 参与多个国家自然科学基金青年基金项目，荣获山西省科技进步三等奖，“数据库原理与应用”获得山西省精品资源共享课程，出版《Vue.js企业开发实战》《Python快乐编程数据分析与实战》《C语言教程与等级考试》等多部图书。

第1章　算法与程序设计简介 1
1.1　初识算法 1
1.1.1　算法的基本概念 2
1.1.2　算法的描述 4
1.1.3　算法设计的步骤 7
1.1.4　算法的分类 8
1.2　算法复杂度分析 9
1.2.1　时间复杂度 9
1.2.2　空间复杂度 14
1.2.3　算法设计实例 15
1.3　程序设计简介 17
1.3.1　算法与程序 18
1.3.2　结构化程序设计 19
1.3.3　结构化程序设计实例 20
习题 21
第2章　穷举法 23
2.1　穷举法概述 23
2.1.1　穷举法的基本思想 23
2.1.2　穷举法的实施步骤与算法描述 23
2.2　整数搜索 25
2.2.1　算24点游戏 25
2.2.2　韩信点兵 27
2.2.3　素数问题 28
2.2.4　约瑟夫环问题 29
2.2.5　火柴棒等式 30
2.2.6　三色旗问题 31
2.2.7　勾股数问题 32
2.2.8　猜价格游戏 33
2.3　分解与重组 35
2.3.1　水仙花数 35
2.3.2　回文数 35
2.3.3　完数 36
2.4　趣味数学 37
2.4.1　百钱买百鸡问题 37
2.4.2　搬砖问题 38
2.4.3　鸡兔同笼问题 38
2.4.4　数学灯谜 39
2.5　解方程与不等式 40
2.5.1　解二元一次方程 40
2.5.2　解完美立方式 40
2.5.3　解一元二次不等式 41
2.6　数阵与图形 42
2.6.1　杨辉三角形 42
2.6.2　输出各种图形 43
2.7　穷举设计的优化 45
习题 47
第3章　递推法 48
3.1　递推法概述 48
3.1.1　递推法的基本思想 48
3.1.2　递推法的实施步骤与算法描述 49
3.2　递推数列 51
3.2.1　斐波那契数列和卢卡斯数列 51
3.2.2　分数数列 53
3.2.3　幂序列 53
3.2.4　双关系递推数列 54
3.2.5　储油点问题 56
3.3　递推数阵 57
3.3.1　累加和 57
3.3.2　阶乘问题 58
3.3.3　九九乘法表 58
3.4　递推的其他应用 59
3.4.1　猴子爬山问题 59
3.4.2　整币兑零问题 60
3.4.3　整数划分问题 61
3.4.4　汉诺塔问题 61
3.4.5　体重指数BMI 62
3.4.6　求π的近似值 63
3.4.7　求一元二次方程的根 63
3.4.8　求三角形的面积 64
3.4.9　存钱问题 65
3.4.10　求公约数和小公倍数 66
习题 67
第4章　回溯法 68
4.1　回溯法概述 68
4.1.1　回溯法的基本思想 68
4.1.2　回溯法的实施步骤和算法描述 69
4.2　回溯法的应用 70
4.2.1　八皇后问题 70
4.2.2　图的着色问题 71
4.2.3　装载问题 73
4.2.4　批处理作业调度 75
4.2.5　符号三角形问题 77
4.2.6　团问题 78
4.2.7　旅行售货员问题 80
4.2.8　电路板排列问题 82
4.2.9　连续邮资问题 84
4.2.10　圆排列问题 86
4.2.11　桥本分数式 88
4.2.12　素数环 89
4.2.13　神奇古尺 91
4.3　回溯设计的优化 92
习题 93
第5章　分支限界法 94
5.1　分支限界法概述 94
5.1.1　分支限界法的基本思想 94
5.1.2　分支限界法的实施步骤和算法描述 94
5.2　分支限界法的应用 95
5.2.1　迷宫问题 95
5.2.2　六数码问题 98
5.2.3　旅行商问题 101
5.2.4　背包问题 104
5.3　回溯法与分支限界法的比较 108
习题 109
第6章　递归法 110
6.1　递归法概述 110
6.1.1　递归法的基本思想 110
6.1.2　递归法的实施步骤和算法描述 110
6.2　递归法的应用 111
6.2.1　整数划分问题 111
6.2.2　汉诺塔问题 112
6.2.3　枚举排列问题 113
6.2.4　用递归法求斐波那契数列 114
6.2.5　排队买票问题 115
6.2.6　猴子吃桃子问题 116
6.2.7　RPG涂色问题 117
6.2.8　二叉树的遍历 118
6.3　回溯法与递归法的比较 120
习题 120
第7章　分治法 121
7.1　分治法概述 121
7.1.1　分治法的基本思想 121
7.1.2　分治法的实施步骤和算法描述 122
7.2　分治法的应用 123
7.2.1　二分查找法 123
7.2.2　大整数乘法 125
7.2.3　斯特拉森矩阵乘法 127
7.2.4　棋盘覆盖问题 128
7.2.5　合并排序 129
7.2.6　快速排序 132
7.2.7　线性时间选择 133
7.2.8　近点对问题 136
7.2.9　循环赛日程表 137
7.3　递归转化 139
7.3.1　一般的递归转非递归 139
7.3.2　分治法中的递归转化 141
习题 143
第8章　贪心算法 145
8.1　贪心算法概述 145
8.1.1　贪心算法的基本思想 145
8.1.2　贪心算法的实施步骤与算法描述 145
8.2　活动安排问题 146
8.3　田忌赛马 148
8.4　背包问题 149
8.5　覆盖问题 151
8.5.1　区间覆盖问题 151
8.5.2　不相交覆盖 151
8.5.3　点覆盖 151
8.6　教室调度问题 153
8.7　小生成树——Kruskal算法 155
8.8　小生成树——Prim算法 157
8.9　哈夫曼编码 160
8.10　教室分配问题 164
8.11　短路径——弗洛伊德算法 166
8.12　短路径——迪杰斯德拉算法 169
8.13　均分纸牌 172
8.14　浏览路线问题 173
8.15　机器调度问题 175
8.16　钱币找零问题 176
习题 177
第9章　动态规划法 178
9.1　动态规划法概述 178
9.1.1　动态规划法的基本思想 178
9.1.2　动态规划法的实施步骤与算法描述 179
9.2　装载问题 180
9.3　投资分配问题 181
9.4　背包问题 185
9.4.1　0-1背包问题 185
9.4.2　二维0-1背包问题 187
9.5　长子序列探索 188
9.5.1　长非降子序列 188
9.5.2　长公共子序列（Longest Common Subsequence，LCS） 190
9.6　路径搜索 192
9.6.1　数字三角形路径和 192
9.6.2　多源短路径问题 194
9.6.3　走方格问题 197
9.6.4　邮资问题 198
9.7　动态规划与其他算法的比较 199
习题 200
第10章　随机算法 201
10.1　随机算法概述 201
10.2　随机数 201
10.2.1　随机生成数组元素 202
10.2.2　随机生成数字 204
10.2.3　随机生成计算题 206
10.3　同余算法 208
10.4　舍伍德算法 209
10.5　蒙特卡罗算法 211
10.5.1　用蒙特卡罗算法求π的值 211
10.5.2　用蒙特卡罗算法求特殊图形的面积 212
10.5.3　蒙特卡罗算法的优缺点及改进措施 213
10.6　拉斯维加斯算法 214
10.7　蒙特卡罗算法和拉斯维加斯算法的比较 217
10.8　随机算法的优缺点 217
习题 217
附录A　不同算法的比较 219
参考文献 221