算法设计与分析实用教程

•注重常用算法的选取与组织。结合本科教学实际，精心选取了几个常用算法。

•注重典型案例的精选与提炼。对选取的每一种算法，设计了基础型、应用型与综合型三种难度梯度的典型案例。

•注重算法设计与实现的紧密结合。采用功能丰富、应用面广、高校学生使用率最高的C语言描述算法，并直接在VC++环境下测试通过，大大缩减了算法设计与程序实现的距离。

•注重算法设计的改进与优化。对某些典型案例提供了多种算法设计，编写出不同表现形式和设计风格的算法，体现了算法设计的灵活性和多样性。

进入21世纪，随着计算机的广泛普及与信息技术的深入发展，培养应用型软件开发人才成为提高国家科技水平的重要方面。国家“973”信息技术与高性能软件基础规划项目首席科学家顾钧教授与中国工程院院士李国杰教授指出：“我国的软件开发要算法先行，这样才能推动软件技术的研究与开发，提高我国企业软件产品的技术竞争力和市场竞争力。”

“算法设计与分析”是计算机科学技术学科体系的一个核心问题，是大学计算机专业一门重要的专业基础课。计算机算法设计是应用计算机解决实际问题的核心环节，是一种创造性思维活动，其教育必须面向应用。针对目前相关教材中，算法内容贪多求全、贪广求深，算法理论与实际应用脱节的现状，探索与改革适合计算机本科层次教学的“算法设计与分析”教材，直接关系到学生应用算法设计解决实际问题能力的培养与提高，是实现算法课程教学目标的当务之急。

为此，我们在《计算机常用算法与程序设计教程》（“十一五”国家级规划教材，人民邮电出版社，2008.11）与《计算机常用算法与程序设计案例教程》（清华大学出版社，2011.7）两本书的基础上进行整合优化，推出适合计算机本科教学实际的《算法设计与分析实用教程》，对算法的组织与案例的选取、算法理论阐述与案例实际应用结合进行精心设计，力求适合高校本科教学目标与知识结构的要求。

本书遵循“精选算法，面向设计，突出案例应用，注重能力培养”的编写宗旨，具有以下“四注重”特色。

（1）注重常用算法的选取与组织

本书在常用算法的选取方面，克服以往贪多求全、贪广求深的弊端，结合本科教学实际，精心选取了枚举、递推、递归、动态规划、回溯、贪心算法与模拟等常用算法，避免出现本科阶段与研究生阶段的教学内容混杂不分的局面。其中，模拟算法中的“竖式运算模拟”是我们总结推广应用于数论高精计算的创新成果。

对选取的常用算法，在介绍算法的基本理论与设计规范的基础上，推介该算法设计应用的常用模式，联系典型案例讲述该算法中要求本科生掌握的基本内容与应用设计，删除一些难度大、理论深、应用少的带研究性质的算法内容。

（2）注重典型案例的精选与提炼

算法是程序设计的核心，算法需要典型案例的展示与支撑。培养学生学习算法设计的兴趣，激发学生应用算法设计解决实际问题的学习热情，不是一两句空洞说教所能奏效的，必须通过一些有趣的、有启发性的典型案例来引导。教程在算法材料的组织上，克服以往罗列算法多、应用算法设计解决实际问题少、算法理论与实际应用脱节的弊端，对选取的每一种算法，设计了基础型、应用型与综合型三种难度梯度的典型案例，包括基础的数值求解、常见的数据处理、有趣的智力测试、巧妙的模拟探索，既有启发引导的基础案例，也有难度较大的综合案例，既有构思巧妙的新创趣题，也有历史悠久的经典名题，难度适宜，深入浅出。

这些典型案例的精选与提炼有利于提高学生学习算法设计的兴趣，有利于学生在计算机实际案例求解上开阔视野，使之在算法思路的开拓与设计技巧的应用上有一个深层次的锻炼与提高。通过典型案例来展开算法设计与分析，突出算法设计在解决实际案例中的核心地位与指导作用。其中一些难度较大的综合型案例可作为课后的专题研究与课程设计选用。

（3）注重算法设计与实现的紧密结合

算法是程序设计的核心与灵魂，程序是算法的一种描述与实现手段。算法与程序实际上是一个统一体，不应该也不能将它们对立或分割。教程采用功能丰富、应用面广、高校学生使用率最高的C语言描述算法，并直接在VC++环境下测试通过，大大缩减了算法设计与程序实现的距离。对每一个实际案例，从案例提出、算法设计与描述，到算法测试与分析、算法改进与优化，环环相扣，融为一体。学生看得懂、学得会、用得上，可以收到立竿见影、举一反三的效果，力求理论与实际相结合、算法设计与应用实际相统一，突出算法在解决实际案例中的核心地位与引导作用，切实提高学生对算法思想的理解和算法设计的把握，有效提高学生应用算法设计解决实际问题的水平和能力。

（4）注重算法设计的改进与优化

算法设计不可能是一成不变的，教材对某些典型案例提供了多种算法设计，编写出不同表现形式与不同设计风格的算法，并对一些常规设计实施多层次多方位的变通、改进与优化，集中体现了算法设计的灵活性和多样性。对不同算法的复杂性分析，确立不同算法的特点与适应环境，比较出不同算法的优劣。

变通出成果，变通长能力。算法改进与优化的过程既是提高案例求解效率的过程，也是对学生算法设计能力培养与提高的过程，更是优化意识与创新能力增强的过程。

为方便师生教学，本书配套的教学课件、源代码与习题的参考解答均可从指定网站下载。

本书可作为各高等院校计算机及相关专业“算法设计与分析”、“计算机程序设计应用基础”等课程教材，供各级程序设计选拔赛与ACM复习参考；也可供IOI、NOI及各省程序设计竞赛培训选用；还可作为广大程序设计爱好者与软件开发人员的参考书。

本书由杨克昌、严权峰进行策划、编著与统稿。在本书的编写过程中，湖南理工学院的王岳斌教授、周持中教授以及甘靖、方世林等老师给予了多方面的指导与帮助，唐雁、陈凯、姜镇林等同学阅读了书稿并测试了相关算法，在此深表感谢。

尽管每一算法设计都经反复核实检查与检测调试，但因涉及内容较广，难免存在差错，恳请专家与读者批评指正。

编著者

2013年6月

前言

第1章 算法及其复杂性分析 1
1.1 算法及其描述 1
1.1.1 算法定义与特性 1
1.1.2 算法描述 3
1.2 算法复杂性分析 7
1.2.1 算法的时间复杂度 7
1.2.2 算法的空间复杂度 12
1.2.3 NP完全问题 12
1.3 算法设计与分析实例 13
1.3.1 求解最大公约数 13
1.3.2 计算n! 14
1.3.3 全码倍数搜索 16
1.4 算法与程序设计 17
1.4.1 算法与程序 17
1.4.2 结构化程序设计 21
习题1 23
第2章 枚举 26
2.1 枚举概要 26
2.2 统计求和 27
2.2.1 同码小数 27
2.2.2 三角网格 30
2.3 整数搜索 32
2.3.1 整数对 32
2.3.2 基于s的双和数组 33
2.3.3 最小连续m个合数 34
2.4 解方程与不等式 37
2.4.1 佩尔方程 37
2.4.2 分数不等式 38
2.5 数式与运算 40
2.5.1 奇数序列运算式 40
2.5.2 完美综合运算式 41
2.6 数列与数阵 44
2.6.1 H形数序列 44
2.6.2 三阶素数幻方 46
2.7 表格与图形 48
2.7.1 p进制乘法表 48
2.7.2 基于s的和积三角形 49
2.8 枚举设计的改进与优化 52
2.8.1 选择枚举路线 52
2.8.2 精简枚举结构 54
2.8.3 优化枚举参数 55
习题2 56
第3章 递推 59
3.1 递推概述 59
3.1.1 递推的概念 59
3.1.2 递推常用模式 60
3.2 递推数列 61
3.2.1 双关系递推数列 62
3.2.2 振动数列 63
3.2.3 分数数列 65
3.3 超级素数搜索 66
3.4 数阵与网格 69
3.4.1 杨辉三角 69
3.4.2 方格网交通线路 71
3.5 六六顺数组 73
3.6 猴子爬山 76
3.6.1 简单递推设计 76
3.6.2 分级递推设计 77
3.7 整数划分 79
3.7.1 整数划分式的个数 79
3.7.2 整数划分式的实现 80
3.7.3 实现整数划分式的优化 82
3.8 递推与迭代 84
习题3 86
第4章 递归 88
4.1 分治策略与递归 88
4.2 汉诺塔游戏 92
4.2.1 移动次数求解 93
4.2.2 移动过程实现 94
4.3 排队购票问题 96
4.3.1 常规排队 96
4.3.2 带条件限制的排队 98
4.4 多转向旋转方阵 100
4.5 快速排序与选择 102
4.5.1 分区交换排序 103
4.5.2 分区交换选择 105
4.6 实现排列组合 107
4.6.1 基本排列实现 107
4.6.2 复杂排列实现 109
4.6.3 组合实现 111
4.7 整数的拆分式 113
4.8 递归与递推 115
习题4 117
第5章 回溯法 119
5.1 回溯法概述 119
5.1.1 回溯的概念 119
5.1.2 回溯的数学概括与效益分析 120
5.1.3 回溯法的分类 121
5.2 桥本分数式 124
5.3 直尺与串珠 127
5.3.1 古尺神奇 127
5.3.2 数码串珠 129
5.4 逐位整除数 132
5.4.1 回溯探索 132
5.4.2 递推求解 133
5.5 二组均分 135
5.6 伯努利装错信封问题 136
5.6.1 回溯设计 137
5.6.2 递归探索 138
5.7 情侣拍照 140
5.7.1 逐位安排回溯设计 140
5.7.2 成对安排回溯设计 142
5.8 回溯应用小结 144
习题5 145
第6章 动态规划 147
6.1 动态规划概述 147
6.1.1 动态规划的概念 147
6.1.2 动态规划实施步骤 149
6.2 0-1背包问题 150
6.2.1 一般0-1背包问题 150
6.2.2 二维约束0-1背包问题 153
6.3 西瓜分堆 156
6.4 凸n边形的三角形划分 158
6.5 最长子序列 160
6.5.1 最长非降子序列 160
6.5.2 最长公共子序列 163
6.6 插入乘号问题 165
6.7 数阵中的最优路径 167
6.7.1 三角数阵中的最大路径 167
6.7.2 矩阵中的最大路径 169
6.8 动态规划设计小结 172
习题6 172
第7章 贪心算法 174
7.1 贪心算法概述 174
7.1.1 贪心算法的概念 174
7.1.2 贪心算法的理论基础 175
7.2 背包问题 176
7.2.1 可拆背包问题 176
7.2.2 0-1背包问题 178
7.3 删数字问题 179
7.4 埃及分数式 182
7.4.1 选择最小分母构建 182
7.4.2 贪心选择范围的扩展 184
7.5 数列操作与极差 185
7.5.1 数列操作 185
7.5.2 数列操作优化 187
7.5.3 数列极差 188
7.6 哈夫曼树及其应用 190
7.6.1 哈夫曼树 190
7.6.2 哈夫曼编码 193
7.7 贪心算法应用小结 196
习题7 197
第8章 模拟 199
8.1 模拟概述 199
8.1.1 模拟分类 199
8.1.2 竖式运算模拟 202
8.2 乘数探求 203
8.2.1 积为若干个1构成 203
8.2.2 积为若干个2014构成 204
8.2.3 积为任意指定构成 205
8.3 特殊数积 206
8.3.1 01串积 206
8.3.2 二部数积 209
8.4 尾数前移问题 213
8.4.1 限1位尾数前移 213
8.4.2 多位尾数前移 215
8.5 圆周率计算 218
8.5.1 蒙特卡罗模拟计算 218
8.5.2 指定高精度计算 219
8.6 模拟发桥牌 221
8.7 泊松分酒 223
8.8 模拟应用小结 226
习题8 227
第9章 算法的综合应用与优化案例 228
9.1 幂积序列 228
9.1.1 双幂积枚举设计 228
9.1.2 双幂积递推设计 230
9.1.3 多幂积拓广 233
9.2 高斯皇后问题 234
9.2.1 高斯八皇后问题 235
9.2.2 n皇后问题 236
9.2.3 皇后全控棋盘 238
9.3 翻转硬币 241
9.3.1 m×9矩阵枚举设计 241
9.3.2 m×n矩阵回溯设计 247
9.3.3 大规模矩阵贪心设计 251
9.4 最优复杂路径 257
9.4.1 三角数阵中的最小路径 257
9.4.2 矩阵迷宫中的最小通道 260
9.5 马步遍历与哈密顿圈 263
9.5.1 马步遍历 263
9.5.2 马步型哈密顿圈 268
9.5.3 组合型哈密顿圈 272
9.6 算法综合应用小结 277
习题9 278
附录A 在VC++ 6.0环境下运行C程序
方法简介 280
附录B C常用库函数 284
参考文献 288

1. 算法设计与分析 [赵晶]
2. 信息技术基础 [主编 唐倩 邵锐]
3. 大学计算机基础实验（WPS版） [主编　谢江宜　蔡勇]
4. 信息技术（微课版） [王云　徐江鸿　李清霞　罗学锋　]
5. 计算思维与大学计算机基础 [主编　赵旭剑]
6. 大学信息技术实训教程 [主编 任云晖 丁红 赵琳琳]
7. 大学信息技术教程 [主编 任云晖 冯政军 魏斌]
8. 信息技术基础立体化教程 [邹承俊 周洪林 刘和文 叶煜 ]
9. 大学计算机基础与计算思维 [主编 闵笛 汪莹]
10. 信息技术基础项目化教程 [主编 王宏斌 王万丽 王芳]
11. 大学计算机信息素养（第二版） [主编 卢山]
12. 全国计算机等级考试一级（MS Office）指导手册 [主编 王宏斌 孙元 禹晨]
13. 大学计算机基础实验指导及习题解析 [主编 闵笛 李明]
14. 大学计算机信息素养实验指导（第二版） [主编 卢山]
15. 信息技术基础（微课版） [主编　赵艳莉　喻林]
16. 大学信息技术基础 [主编 黎夏克 张倩文 王静]
17. 计算机信息素养基础实践教程 [王锦 姚晓杰 王立武 等 编著]
18. 计算机基础与应用实践教程 [杨毅 刘立君 张春芳 梁宁玉 ]
19. 计算机信息素养基础 [主编 陈艳 秦凯 黄海玉]
20. 计算机基础与应用 [主编 秦凯 梁宁玉 王毅]
21. 大学计算机基础上机实践教程（第六版） [主编 何振林 罗奕]
22. 大学计算机基础教程实验指导与测试题集 [主编 饶拱维 吴华光 巫满秀]
23. 大学计算机基础（等级考试版） [主编 钟诚]
24. 大学计算机基础教程（第二版） [主编 安志远 崔岩]
25. 计算机应用基础实训教程（第三版） [主 编 王向慧 康秀兰]
26. 计算机应用基础（第三版） [主 编 王向慧 康秀兰]
27. 计算机应用基础 [主编　赵艳莉]
28. 大学计算机基础案例教程（第二版） [主 编 叶潮流 金 莹]
29. 大学信息技术 [主编　连卫民　张志明　陈炎龙]
30. 新编计算机应用基础教程 [主编　戴毅　吴瑞芝　贾姗姗]