算法与程序设计

第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