为了适应培养21世纪计算机人才的需要，结合我国高等院校教育工作的现状，立足培养学生能跟上国际计算机科学技术的发展水平，本书以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为信息技术相关学科的学生打下坚实的算法基础。本书主要内容包括算法概述、递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、图的搜索算法、公钥加密算法、P和NP问题浅析等。书中既涉及经典算法及分析，又包括指导ACM竞赛训练的相关算法。本书内容丰富、结构紧凑、可读性强，采用Python语言描述算法，对应的C语言描述算法可扫描二维码下载。 本书可作为高等院校计算机相关专业本科生和研究生学习算法设计的教材，也可供广大工程技术人员和对算法感兴趣的读者学习参考。

李文书 主编。李文书，工学博士，现任浙江理工大学计算机科技与技术学院教授，博士生导师。IEEE (1-1163129461)、中国计算机学会（E200016385S）高级会员；中国药物滥用防治协会理事；杭州市科技促进会大数据主任；杭州市人工智能协会理事；浙江省国防科技工业协会专家库专家，浙江省151培养人才；杭州市第1批工业企业信息化专家；高校面向全国接受访问学者导师，曾获中国商业联合会科学技术奖三等奖1次(2013.12)。主要研究方向为图像处理、认知建模、虚拟实现、中医四诊合参、物联网集成开发、VR展示。发表论文90余篇，其中有60余篇被SCI/EI收录；著作7部；主持或参与的国家项目8项、省部级项目10项、厅局级项目20项、企业课题30余项等。 韩逢庆 主编。韩逢庆，工学博士，三级教授，重庆交通大学，重庆市优秀中青年骨干教师，重庆市数学学会理事，重庆市运筹学学会理事。参加工作以来先后为本科生讲授“运筹学”“面向对象程序设计”“人工智能导论”“数据结构”“算法设计与分析”“数学模型”“机器学习”和“计算方法”，为硕士和博士研究生讲授“人工智能”“小波分析与应用”“数值分析”“可靠性理论”和“分形几何”等课程，主编《算法分析与设计》教材1部。主要研究方向包括人工智能、机器学习和优化计算等领域。在国际期刊和国际会议发表SCI和EI检索论文近40篇。主研国家项目7项，主持省部级项目3项。获重庆市科技进步二等奖1项，重庆市科技进步三等奖2项。 董世都 主编。董世都，博士，重庆理工大学副教授，硕士研究生导师，长期从事计算机视觉与生产排程优化算法的研究，具有近二十年算法分析与设计及数据结构课程的教学经验。

第1章 算法概述 1 1.1 引言 1 1.1.1 算法的描述 2 1.1.2 算法的特性 2 1.1.3 为什么学习算法 3 1.2 算法的设计 4 1.3 算法的分析 7 1.3.1 正确性分析 7 1.3.2 时空效率分析 8 1.3.3 特性分析 11 1.4 解决问题的一般步骤 11 1.5 本章小结 13 1.6 习题 13 1.6.1 选择题 13 1.6.2 问答题 14 第2章 递归与分治策略 15 2.1 递归 16 2.1.1 递归的概念 16 2.1.2 具有递归特性的问题 17 2.1.3 递归算法分析 19 2.2 分治策略 26 2.2.1 分治策略的基本步骤 26 2.2.2 分治策略的适用条件 27 2.2.3 二分搜索算法 28 2.2.4 棋盘覆盖问题 28 2.2.5 快速排序 31 2.2.6 大整数乘法 34 2.2.7 矩阵乘法 37 2.3 ACM经典问题解析 41 2.3.1 蜂窝问题 (难度：★☆☆☆☆) 41 2.3.2 丑数问题 (难度：★★☆☆☆) 43 2.3.3 复制书本问题 (难度：★★★☆☆) 45 2.3.4 分形问题 (难度：★★★☆☆) 48 2.3.5 玩具分箱问题 (难度：★★☆☆☆) 49 2.3.6 电缆分段问题 (难度：★★☆☆☆) 52 2.4 本章小结 54 2.5 习题 54 第3章 动态规划 58 3.1 动态规划简介 59 3.1.1 动态规划的基本思想 59 3.1.2 动态规划算法的步骤 59 3.1.3 动态规划问题的特征 59 3.1.4 动态规划与静态规划的关系 60 3.2 矩阵连乘积问题 61 3.2.1 分析最优解的结构 64 3.2.2 建立递归关系 64 3.2.3 计算最优值 65 3.2.4 构造最优解 67 3.3 动态规划算法的基本要素 68 3.3.1 最优子结构 68 3.3.2 子问题重叠 68 3.3.3 备忘录算法 69 3.4 最长公共子序列 70 3.4.1 最长公共子序列的结构 71 3.4.2 子问题的递归结构 72 3.4.3 计算最优值 72 3.4.4 构造最长公共子序列 73 3.5 最大子段和 74 3.5.1 递归关系分析 74 3.5.2 算法实现 75 3.6 0-1背包问题 76 3.6.1 递归关系分析 76 3.6.2 算法实现 77 3.7 ACM经典问题解析 79 3.7.1 数塔(难度：★★☆☆☆) 79 3.7.2 免费馅饼 (难度：★★★☆☆) 80 3.7.3 珠宝分类 (难度：★★★☆☆) 82 3.7.4 最大得分序列 (难度：★★★★☆) 85 3.7.5 堆砖块 (难度：★★★★☆) 86 3.7.6 火车线路 (难度：★★★★☆) 89 3.8 本章小结 92 3.9 习题 93 第4章 贪心算法 97 4.1 活动安排问题 97 4.2 贪心算法的理论基础 100 4.2.1 贪心算法的基本思想 100 4.2.2 贪心算法的基本要素 100 4.2.3 贪心算法的基本步骤 101 4.3 删数问题 102 4.3.1 算法基本思想 102 4.3.2 贪心选择性质 102 4.3.3 最优子结构性质 102 4.3.4 算法实现 103 4.3.5 复杂度分析 103 4.4 背包问题 104 4.4.1 算法基本思想 104 4.4.2 最优子结构性质 104 4.4.3 贪心选择性质 105 4.4.4 算法实现 105 4.4.5 复杂度分析 106 4.5 最优装载问题 107 4.5.1 算法基本思想 107 4.5.2 贪心选择性质 107 4.5.3 最优子结构性质 107 4.5.4 算法实现 108 4.5.5 复杂度分析 109 4.6 单源最短路径问题 109 4.6.1 算法基本思想 109 4.6.2 贪心选择性质 110 4.6.3 最优子结构性质 111 4.6.4 算法实现 111 4.6.5 复杂度分析 113 4.7 最优服务顺序问题 113 4.7.1 算法基本思想 113 4.7.2 贪心选择性质 114 4.7.3 最优子结构性质 114 4.7.4 算法实现 114 4.7.5 复杂度分析 115 4.8 ACM经典问题解析 115 4.8.1 老鼠的交易 (难度：★★☆☆☆) 115 4.8.2 整理照片 (难度：★★★☆☆) 117 4.8.3 搬桌子问题 (难度：★★★☆☆) 119 4.8.4 堆积木问题 (难度：★★★★☆) 120 4.8.5 处理木棍问题 (难度：★★★★☆) 122 4.8.6 钓鱼问题 (难度：★★★★☆) 123 4.8.7 树形动态规划问题 (难度：★★★★☆) 126 4.8.8 青蛙的邻居 (难度：★★★☆☆) 128 4.9 本章小结 131 4.10 习题 131 第5章 回溯法 133 5.1 回溯法的基本思想 133 5.1.1 问题的解空间 134 5.1.2 解空间的搜索过程 136 5.1.3 回溯法的基本步骤 137 5.1.4 回溯法实现 138 5.2 图的m着色问题 140 5.2.1 问题的解空间 140 5.2.2 约束条件 141 5.2.3 搜索过程 141 5.2.4 算法实现 142 5.2.5 复杂度分析 143 5.3 n皇后问题 143 5.3.1 问题的解空间 144 5.3.2 约束条件 144 5.3.3 搜索过程 144 5.3.4 算法实现 145 5.3.5 复杂度分析 146 5.4 装载问题 147 5.4.1 问题的解空间 147 5.4.2 约束条件 147 5.4.3 限界条件 147 5.4.4 搜索过程 147 5.4.5 算法实现 148 5.4.6 复杂度分析 150 5.5 0-1背包问题 150 5.5.1 问题的解空间 150 5.5.2 约束条件 150 5.5.3 限界条件 150 5.5.4 搜索过程 150 5.5.5 算法实现 151 5.5.6 复杂度分析 152 5.6 旅行商问题 152 5.6.1 问题的解空间 153 5.6.2 约束条件 153 5.6.3 限界条件 153 5.6.4 搜索过程 153 5.6.5 算法实现 154 5.6.6 复杂度分析 155 5.7 流水作业调度问题 156 5.7.1 问题的解空间 156 5.7.2 约束条件 156 5.7.3 限界条件 156 5.7.4 搜索过程 156 5.7.5 算法实现 157 5.7.6 复杂度分析 158 5.8 ACM经典问题解析 158 5.8.1 外星人的等式 (难度：★★★☆☆) 158 5.8.2 UNIX的插座问题 (难度：★★★☆☆) 163 5.8.3 变位词检测 (难度：★★☆☆☆) 167 5.8.4 重新整理序列 (难度：★★★☆☆) 171 5.9 本章小结 173 5.10 习题 174 第6章 分支限界法 175 6.1 分支限界法的基本理论 175 6.1.1 分支限界法的搜索策略 175 6.1.2 分支结点的选择 176 6.1.3 限界函数 177 6.2 单源最短路径问题 177 6.2.1 问题描述 177 6.2.2 算法描述与设计 178 6.2.3 算法实现 179 6.3 装载问题 182 6.3.1 问题描述 182 6.3.2 算法设计与实现 182 6.4 0-1背包问题 189 6.4.1 问题描述 189 6.4.2 算法描述与设计 189 6.4.3 算法实现 191 6.5 旅行商问题 196 6.5.1 问题描述 196 6.5.2 算法描述与设计 196 6.5.3 算法实现 198 6.5.4 算法复杂度分析 202 6.6 ACM经典问题解析 202 6.6.1 布线问题 (难度：★★★☆☆) 202 6.6.2 方格调整问题 (难度：★★★☆☆) 206 6.6.3 旅行商问题 (难度：★★★☆☆) 207 6.6.4 祖父的庄园 (难度：★★★☆☆) 210 6.6.5 寻找倍数 (难度：★★★☆☆) 212 6.7 本章小结 214 6.8 习题 215 第7章 图的搜索算法 217 7.1 图的广度优先搜索遍历 219 7.1.1 算法描述与分析 219 7.1.2 程序实现 222 7.2 图的深度优先搜索遍历 225 7.2.1 算法描述与分析 225 7.2.2 程序实现 228 7.2.3 有向无环图的拓扑排序 230 7.3 有向图的强连通分支 237 7.3.1 算法描述与分析 237 7.3.2 程序实现 240 7.4 无向图的双连通分支 243 7.4.1 算法描述与分析 243 7.4.2 程序实现 247 7.5 流网络与最大流问题 249 7.5.1 算法描述与分析 249 7.5.2 程序实现 256 7.6 ACM经典问题解析 258 7.6.1 树的判断问题 (难度：★★★☆☆) 258 7.6.2 股票经纪人问题 (难度：★★★☆☆) 260 7.6.3 UNIX的插座问题 (难度：★★★☆☆) 262 7.7 本章小结 266 7.8 习题 266 第8章 公钥加密算法 275 8.1 RSA公钥密码算法 277 8.1.1 算法描述 278 8.1.2 快速模幂算法 279 8.1.3 素数的生成 280 8.1.4 扩展欧几里得算法 282 8.2 因子分解算法 284 8.2.1 Pollard’s p-1算法 285 8.2.2 Pollard’s rho算法 286 8.3 离散对数密码算法 288 8.3.1 Diffie-Hellman密钥交换协议 288 8.3.2 ElGamal公钥加密算法 289 8.4 离散对数算法 289 8.4.1 小步/大步算法 290 8.4.2 Pohlig-Hellman算法 293 8.5 ACM经典问题解析 294 8.5.1 简单的加密算法 (难度：★★☆☆☆) 294 8.5.2 古代密码 (难度：★★★☆☆) 295 8.6 本章小结 297 8.7 习题 298 第9章 P和NP问题浅析 299 9.1 决策问题和优化问题 300 9.2 P类问题和NP类问题 301 9.2.1 P类问题 301 9.2.2 NP类问题 301 9.3 确定性图灵机 302 9.3.1 图灵机的定义 302 9.3.2 k带图灵机的形式化描述 303 9.3.3 图灵机计算实例 303 9.4 非确定性图灵机 306 9.4.1 非确定性图灵机的定义 306 9.4.2 非确定性图灵机的形式化描述 306 9.4.3 非确定性图灵机计算实例 307 9.4.4 非确定性算法 308 9.4.5 NP类问题的定义 309 9.4.6 NP难(NP-hard)问题 309 9.5 NP完全问题 310 9.5.1 NP完全问题的定义 310 9.5.2 多项式时间归约 311 9.5.3 库克定理 312 9.5.4 3-SAT问题 315 9.5.5 NP完全问题的近似算法 316 9.6 NP难问题的近似算法* 326 9.6.1 旅行商问题的近似算法 327 9.6.2 背包问题的近似算法 334 9.7 本章小结 337 9.8 习题 338 附录A 求和 339 附录B 数论入门 346 参考文献 350