本教材面向高校"新工科”建设对信息基础理论教学方面的新需求，以及目前计算机及相关专业在应对大数据、人工智能、区块链等信息新技术应用方面的人才培养理论基础新要求，专门设计了相关的教材学习内容。同时，本教材通过时事热点，开展了"课程思政”教育，突出算法工程师的社会责任感和价值观要求，强化了学生的"四个自信”教育。此外，本教材提供了不断更新的配套在线教学资源。本教材根据教学大纲中一般性教学要求与时间规范，分4篇分别介绍了算法理论基础、算法设计基础、算法设计策略和算法设计扩展的基本内容及其内在联系。 本教材适用于计算机、信息安全、物联网工程、通信工程、人工智能、信息管理等专业的学生学习。

罗熊，北京科技大学计算机与通信工程学院教授，博士生导师，计算机科学与技术专业教师，现任北京科技大学教务处处长。北京市高等学校教学名师奖、高校计算机专业优秀教师奖、宝钢优秀教师奖获得者。主要讲授"算法设计与分析”、"离散数学”等多门本科及研究生课程，主编的教材获批为国家级规划教材。获得国家级教学成果二等奖1项，北京市高等教育教学成果特等奖1项、一等奖1项、二等奖2项，其他省部级教学成果奖2项。IEEE Senior Member。主要研究领域包括数据挖掘与机器学习、区块链、物联网应用等。兼任教育部高等学校计算机类教学指导委员会"计算机专业开放教育体系建设和教材建设专家委员会”委员等。近年来主持并完成4项国家自然科学基金和3项北京市自然科学基金项目。在国际知名期刊和会议上发表学术论文180余篇（其中，曾有12篇入选ESI高被引论文，2篇论文入选ESI热点论文）。获得包括北京市科学技术二等奖、中国图象图形学学会技术发明一等奖、中国煤炭工业协会科学技术二等奖等在内的省部级科研奖励6项，入选美国斯坦福大学发布的2020-2025年"全球前2%顶尖科学家榜单”。

第 1 篇 算法理论基础
第 1 章 算法概述·······························································································.3
1.1 算法的基本概念 ·····················································································.4
1.1.1 用计算机求解问题 ··············································································.4
1.1.2 算法及其要素和特性 ············································································.6
1.2 算法描述 ······························································································.7
1.3 算法设计的流程 ···················································································.12
1.4 扩展阅读 ····························································································.14
1.4.1 算法的历史 ····················································································.14
1.4.2 东数西算 ······················································································.15
本章小结 ···································································································.17
习题 1 ······································································································.17
应用实验和限时编程 ····················································································.18
第 2 章 算法分析基础 ······················································································.21
2.1 算法分析体系及计量 ·············································································.22
2.1.1 算法分析的评价体系 ··········································································.22
2.1.2 计算模型 ······················································································.23
2.1.3 算法的时间复杂度 ············································································.26
2.2 算法复杂性理论 ···················································································.30
2.2.1 P 类和 NP 类问题 ·············································································.30
2.2.2 NPC 类问题 ···················································································.31
2.3 算法分析方法 ······················································································.31
2.3.1 非递归算法的分析 ············································································.31
2.3.2 递归算法的分析 ···············································································.32
2.4 扩展阅读：算法复杂性的历史 ·································································.33
本章小结 ···································································································.36
习题 2 ······································································································.37
应用实验及限时编程题 ·················································································.39
第 2 篇 算法设计基础
第 3 章 基本数据结构 ······················································································.43
3.1 数组的高级使用方法 ·············································································.44
3.1.1 使用技巧 ······················································································.44
·V·
3.2 指针的高级使用方法 ·············································································.52
3.2.1 使用技巧 ······················································································.52
3.2.2 设计示例 ······················································································.53
3.3 扩展阅读 ····························································································.56
本章小结 ···································································································.58
习题 3 ······································································································.59
应用实验及限时编程题 ·················································································.61
第 4 章 循环和递归 ·························································································.65
4.1 循环的设计 ·························································································.66
4.1.1 循环的定义 ····················································································.66
4.1.2 循环的设计要点 ···············································································.66
4.1.3 设计示例 ······················································································.67
4.2 递归的设计 ·························································································.70
4.2.1 递归的定义 ····················································································.70
4.2.2 递归的执行过程 ···············································································.70
4.2.3 递归的设计步骤 ···············································································.71
4.2.4 递归的设计要点 ···············································································.72
4.2.5 递归与循环的关系 ············································································.72
4.2.6 设计示例 ······················································································.73
4.3 递归的转换 ·························································································.74
4.4 扩展阅读：递归循环效率问题 ·································································.77
本章小结 ···································································································.78
习题 4 ······································································································.79
应用实验及限时编程题 ·················································································.82
第 5 章 优化模型·····························································································.85
5.1 算术运算的妙用 ···················································································.86
5.2 标志量的妙用 ······················································································.89
5.3 优化算法的数学模型 ·············································································.93
5.3.1 认识数学模型和数学建模 ····································································.93
5.3.2 杨辉三角形的应用 ············································································.94
5.3.3 最大公约数的应用 ············································································.96
5.3.4 公倍数的应用 ·················································································.98
5.3.5 裴波那契数列的应用 ·········································································.100
5.3.6 递推关系求解方程 ···········································································.100
5.4 扩展阅读：数学建模 ············································································.102
本章小结 ··································································································.104
习题 5 ·····································································································.104
应用实验及限时编程题 ················································································.105
第 3 篇 算法设计策略
第 6 章 迭代法 ·······························································································.111
6.1 迭代法的基本思想 ···············································································.112
6.2 迭代法的设计 ·····················································································.114
6.3 经典例题解析 ·····················································································.114
6.3.1 兔子繁殖问题的求解算法 ···································································.114
6.3.2 辗转相除法 ···················································································.118
6.3.3 沙漠储油点规划问题的求解算法 ····························································.119
6.3.4 牛顿迭代数值计算问题的求解算法 ·························································.121
6.3.5 实测问题算法 ················································································.124
6.4 扩展阅读 ···························································································.126
6.4.1 火箭的迭代精确制导与国防安全 ····························································.126
6.4.2 梯度下降法 ···················································································.127
本章小结 ··································································································.128
习题 6 ·····································································································.128
应用实验及限时编程题 ················································································.132
第 7 章 分治法 ·······························································································.135
7.1 分治法的基本思想 ···············································································.136
7.1.1 分治法的基本概念 ···········································································.136
7.1.2 分治法的求解过程 ···········································································.137
7.1.3 分治法的实现框架 ···········································································.137
7.2 经典例题解析 ·····················································································.138
7.2.1 金块问题的求解算法 ·········································································.138
7.2.2 循环赛日程安排问题的求解算法 ····························································.142
7.2.3 大整数乘法问题的求解算法 ·································································.145
7.2.4 数组中第 k 小元素的求解算法 ······························································.148
7.2.5 实测问题算法 ················································································.151
7.3 扩展阅读：大规模并行计算和超级计算机 ·················································.153
本章小结 ···································································································.155
习题 7 ·····································································································.156
应用实验及限时编程题 ················································································.157
第 8 章 动态规划法 ························································································.161
8.1 动态规划法的基本思想 ·········································································.162
8.1.1 动态规划法的基本概念 ······································································.162
8.1.2 动态规划法的基本特征 ······································································.163
8.1.3 动态规划法的求解过程 ······································································.163
8.1.4 动态规划法的实现框架 ······································································.164
8.2 经典例题解析 ·····················································································.164
8.2.1 数塔问题的求解算法 ·········································································.165
8.2.2 整数拆分问题的求解算法 ···································································.167
8.2.3 资源分配问题的求解算法 ···································································.170
8.2.4 0-1 背包问题的求解算法 ····································································.173
8.2.5 矩阵链乘法问题的求解算法 ·································································.176
8.2.6 最长公共字符子序列问题的求解算法 ······················································.180
8.2.7 最长单调递增子序列问题的求解算法 ······················································.183
8.2.8 实测问题的求解算法 ·········································································.190
8.3 扩展阅读 ···························································································.193
8.3.1 自适应动态规划 ··············································································.193
8.3.2 强化学习 ·····················································································.194
8.3.3 人工智能伦理 ················································································.194
本章小结 ··································································································.196
习题 8 ·····································································································.197
应用实验及限时编程题 ················································································.199
第 9 章 贪婪法 ·······························································································.202
9.1 贪婪法的基本概念 ···············································································.203
9.1.1 贪婪法的基本思想 ···········································································.203
9.1.2 贪婪法的基本特征 ···········································································.204
9.1.3 贪婪法的实现框架 ···········································································.204
9.2 贪婪法的设计思路 ···············································································.205
9.3 经典例题解析 ·····················································································.208
9.3.1 活动安排问题 ················································································.208
9.3.2 部分背包问题 ················································································.210
9.3.3 哈夫曼问题 ···················································································.212
9.3.4 纸币统计问题 ················································································.219
9.3.5 多机调度问题 ················································································.222
9.3.6 单源最短路径问题 ···········································································.227
9.3.7 实测问题 ·····················································································.232
9.4 扩展阅读 ···························································································.235
9.4.1 贪婪法的历史 ················································································.235
9.4.2 集束搜索 ·····················································································.236
9.4.3 贪婪法和高速缓冲存储器管理 ······························································.236
本章小结 ···································································································.238
习题 9 ·····································································································.238
应用实验及限时编程题 ················································································.244
第 10 章 蛮力法 ·····························································································.247
10.1 蛮力法的基本概念 ·············································································.248
10.1.1 蛮力法的基本思想 ··········································································.248
10.1.2 蛮力法的实现框架 ··········································································.248
10.2 蛮力法的设计 ···················································································.249
10.3 经典例题解析 ···················································································.250
10.3.1 百鸡百钱问题的求解算法 ··································································.250
10.3.2 最大连续子序列和问题的求解算法 ························································.254
10.3.3 拨钟问题的求解算法 ·······································································.258
10.3.4 重复数字统计问题的求解算法 ·····························································.262
10.3.5 数字方格问题的求解算法 ··································································.266
10.3.6 实测问题的求解算法 ·······································································.269
10.4 扩展阅读 ·························································································.273
10.4.1 蛮力搜索和组合爆炸 ·······································································.273
10.4.2 蛮力法和密码破解 ··········································································.274
本章小结 ···································································································.277
习题 10 ····································································································.277
应用实验及限时编程题 ················································································.284
第 11 章 回溯法 ·····························································································.287
11.1 回溯法的基本概念 ·············································································.288
11.1.1 回溯法的基本思想 ··········································································.288
11.1.2 回溯法的实现框架 ··········································································.289
11.1.3 回溯法与深度优先搜索的关系 ·····························································.290
11.2 回溯法的设计 ···················································································.290
11.3 经典例题解析 ···················································································.294
11.3.1 八皇后问题的求解算法 ·····································································.294
11.3.2 素数环问题的求解算法 ·····································································.302
11.3.3 0-1 背包问题的求解算法 ···································································.305
11.3.4 任务分配问题的求解算法 ··································································.315
11.3.5 子集和问题的求解算法 ·····································································.318
11.3.6 格雷码问题的求解算法 ·····································································.321
11.3.7 实测问题的求解算法 ·······································································.324
11.4 扩展阅读 ·························································································.327
11.4.1 回溯法的历史 ···············································································.327
11.4.2 Davis-Putnam 算法 ··········································································.328
11.4.3 研究求解器的中国科学家 ··································································.330
本章小结 ···································································································.332
习题 11 ····································································································.334
应用实验及限时编程题 ················································································.338
第 12 章 分支限界法 ·······················································································.341
12.1 分支限界法的基本概念 ·······································································.342
12.1.1 分支限界法的基本思想 ·····································································.342
12.1.2 分支限界法的实现框架 ·····································································.342
12.2 分支限界法的设计 ·············································································.343
12.3 经典例题解析 ···················································································.343
12.3.1 0-1 背包问题的求解算法 ···································································.343
12.3.2 单源最短路径问题的求解算法 ·····························································.347
12.3.3 任务分配问题的求解算法 ··································································.350
12.4 扩展阅读：路径规划 ·········································································.353
本章小结 ···································································································.356
习题 12 ····································································································.356
应用实验及限时编程题 ················································································.358
第 4 篇 算法设计扩展
第 13 章 概率算法 ··························································································.365
13.1 概率算法的基本概念 ··········································································.366
13.2 概率算法的实现框架 ··········································································.369
13.3 典型的概率算法 ················································································.370
13.3.1 蒙特卡洛方法 ···············································································.370
13.3.2 拉斯维加斯算法 ············································································.371
13.3.3 舍伍德算法 ··················································································.372
13.4 扩展阅读：概率算法延伸 ····································································.374
本章小结 ···································································································.375
习题 13 ·····································································································.376
应用试验及限时编程题 ················································································.376
第 14 章 基于华为云的算法设计实践 ··································································.377
14.1 华为云平台简介 ················································································.378
14.1.1 华为云平台 ··················································································.378
14.1.2 实验环境 ····················································································.379
14.1.3 编程语言选择 ···············································································.379
14.2 应用示例 ·························································································.379
14.2.1 华为云注册 ··················································································.380
14.2.2 实验环境搭建 ···············································································.380
14.2.3 实验问题—八皇后问题 ··································································.385
14.2.4 实验步骤 ····················································································.386
14.3 扩展阅读 ·························································································.391
14.3.1 华为云延伸介绍 ············································································.391
14.3.2 教育部-华为“智能基座”产教融合协同育人基地项目 ··································.391
本章小结 ··································································································.392
名词与术语索引表 ······················································································.393
名词与术语索引表 ······················································································.394
参考文献 ········································································································.397