算法设计与分析(第3版)

本书将经典问题和算法设计技术结合,以读者容易理解和接受的方式,系统介绍了算法设计技术,包括模拟法、递推法、蛮力法、分治法、减治法、贪心法、动态规划法、深度优先搜索、广度优先搜索、回溯法、A*算法、限界剪枝法、近似算法、概率算法和群智能算法;同时以通俗易懂的方式,系统介绍了算法分析技术,包括算法的时间复杂度分析、空间复杂度分析、算法、确定性算法、非确定性算法、P类问题、NP类问题和NP完全问题。所有问题都用伪代码给出了算法描述,并提供了C++语言程序源码,且在C++语言的典型编程环境下调试通过。 本书案例丰富,叙述清晰,深入浅出,结合应用,符合算法学习者的认知规律,可作为高等院校计算机专业本科和研究生学习算法类课程的教材,适合准备参加程序设计竞赛(NOIP或ACM)却无从下手的学生,也特别适合算法爱好者学习参考。 封面 1 书名 2 版权 3 前言 4 目录 9 第一篇 基础知识 19 第1章 算法设计基础 19 1.1什么是算法 19 1.1.1算法的定义 19 1.1.2算法的描述方法 20 1.1.3算法在问题求解中的地位 22 1.2什么是好算法 22 1.2.1如何评价算法 22 1.2.2效率——算法的核心和灵魂 23 1.3为什么要学习和研究算法 24 1.3.1算法研究是推动计算机技术发展的关键 24 1.3.2算法训练能够提高计算思维能力 24 1.3.3程序员必须要学习算法吗 25 1.4如何设计算法 25 1.4.1基本的数据结构 25 1.4.2重要的问题类型 27 1.4.3算法设计的一般过程 29 1.5拓展与演练 30 1.5.1算法研究与图灵奖 30 1.5.2代码优化技巧 31 实验1最大公约数 33 习题1 34 第2章 算法分析基础 35 2.1算法的时间复杂度分析 35 2.1.1输入规模与基本语句 35 2.1.2算法的渐近分析 37 2.1.3最好、最坏和平均情况 38 2.1.4非递归算法的时间复杂度分析 38 2.1.5递归算法的时间复杂度分析 39 2.2算法的空间复杂度分析 40 2.3算法的实验分析 41 2.4拓展与演练 42 2.4.1最优算法 42 2.4.2角谷猜想 43 实验2排序算法的实验比较 44 习题2 45 第二篇 基本的算法设计技术 49 第3章 模拟法 49 3.1概述 49 3.1.1模拟法的设计思想 49 3.1.2一个简单的例子:鸡兔同笼问题 49 3.2数学问题中的模拟法 50 3.2.1约瑟夫环问题 50 3.2.2埃拉托色尼筛法 51 3.3排序问题中的模拟法 53 3.3.1计数排序 53 3.3.2颜色排序 54 3.4拓展与演练 55 3.4.1装箱问题 55 3.4.2数字回转方阵 57 实验3埃氏筛法的优化 58 习题3 58 第4章 递推法 61 4.1概述 61 4.1.1递推法的设计思想 61 4.1.2一个简单的例子:猴子吃桃 61 4.2数学问题中的递推法 62 4.2.1 Fibonacci数列 62 4.2.2 Catalan数列 62 4.3组合问题中的递推法 64 4.3.1伯努利错装信封问题 64 4.3.2旋转的万花筒 65 4.4拓展与演练 65 4.4.1整数划分 65 4.4.2捕鱼知多少 66 实验4杨辉三角形 67 习题4 67 第5章 蛮力法 69 5.1概述 69 5.1.1蛮力法的设计思想 69 5.1.2一个简单的例子:百元买百鸡问题 70 5.2查找问题中的蛮力法 70 5.2.1顺序查找 70 5.2.2串匹配问题 72 5.3排序问题中的蛮力法 77 5.3.1选择排序 77 5.3.2起泡排序 78 5.4图问题中的蛮力法 79 5.4.1哈密顿回路问题 79 5.4.2 TSP问题 80 5.5几何问题中的蛮力法 81 5.5.1最近对问题 81 5.5.2凸包问题 82 5.6拓展与演练 84 5.6.1 KMP算法中next值的计算 84 5.6.2 0/1背包问题 85 实验5任务分配问题 86 习题5 87 第6章 分治法 89 6.1概述 89 6.1.1分治法的设计思想 89 6.1.2分治与递归 90 6.1.3一个简单的例子:汉诺塔问题 90 6.2排序问题中的分治法 91 6.2.1归并排序 91 6.2.2快速排序 93 6.3组合问题中的分治法 96 6.3.1最大子段和问题 96 6.3.2棋盘覆盖问题 98 6.4几何问题中的分治法 100 6.4.1最近对问题 100 6.4.2凸包问题 102 6.5拓展与演练 104 6.5.1扩展欧几里得算法 104 6.5.2中国剩余定理 105 实验6 Karatsuba乘法 106 习题6 107 第7章 减治法 109 7.1概述 109 7.1.1减治法的设计思想 109 7.1.2一个简单的例子:俄式乘法 110 7.2查找问题中的减治法 110 7.2.1折半查找 110 7.2.2选择问题 112 7.3排序问题中的减治法 114 7.3.1插入排序 114 7.3.2堆排序 115 7.4组合问题中的减治法 117 7.4.1淘汰赛冠军问题 117 7.4.2假币问题 118 7.5拓展与演练 120 7.5.1两个序列的中位数 120 7.5.2 topK问题 122 实验7假币问题的复杂版本 123 习题7 125 第8章 贪心法 127 8.1概述 127 8.1.1贪心法的设计思想 127 8.1.2一个简单的例子:付款问题 127 8.2图问题中的贪心法 128 8.2.1 TSP问题 128 8.2.2图着色问题 130 8.2.3最小生成树 132 8.3组合问题中的贪心法 135 8.3.1背包问题 135 8.3.2活动安排问题 137 8.3.3埃及分数 139 8.4拓展与演练 140 8.4.1贪心法的正确性证明 140 8.4.2田忌赛马 142 实验8合并字符串 143 习题8 143 第9章 动态规划法 145 9.1概述 145 9.1.1多阶段决策过程 145 9.1.2动态规划法的设计思想 146 9.1.3一个简单的例子:网格上的最短路径 147 9.2组合问题中的动态规划法 149 9.2.1最长公共子序列 149 9.2.2 0/1背包问题 151 9.3图问题中的动态规划法 153 9.3.1多段图的最短路径 153 9.3.2 TSP问题 156 9.4查找问题中的动态规划法 157 9.4.1近似串匹配 157 9.4.2最优二叉查找树 160 9.5拓展与演练 162 9.5.1最优性原理 162 9.5.2数塔问题 163 实验9最大子段和 166 习题9 166 第三篇 基于搜索的算法设计技术 171 第10章 深度优先搜索 171 10.1深度优先搜索概述 171 10.1.1深度优先搜索的设计思想 171 10.1.2山洞寻宝图 172 10.1.3城堡问题 173 10.2回溯法 174 10.2.1问题的解空间树 174 10.2.2回溯法的设计思想 175 10.2.3回溯法的时间性能 176 10.2.4素数环问题 176 10.2.5八皇后问题 178 10.2.6图着色问题 180 10.3拓展与演练 183 10.3.1批处理作业调度 183 10.3.2哈密顿回路 186 实验10 0/1背包问题 188 习题10 189 第11章 广度优先搜索 191 11.1广度优先搜索概述 191 11.1.1广度优先搜索的设计思想 191 11.1.2农夫抓牛 192 11.1.3骑士旅行 193 11.2 A*算法 195 11.2.1 A*算法的设计思想 195 11.2.2八数码问题 196 11.2.3多段图的最短路径问题 197 11.2.4任务分配问题 199 11.3限界剪枝法 200 11.3.1限界剪枝法的设计思想 200 11.3.2 0/1背包问题 201 11.3.3 TSP问题 203 11.3.4圆排列问题 205 11.4拓展与演练 207 11.4.1限界剪枝法的关键问题 207 11.4.2批处理作业调度问题 208 实验11电路布线问题 210 习题11 211 第四篇 NP问题的算法设计技术 215 第12章 问题的复杂性 215 12.1问题的复杂性分类 215 12.1.1什么是计算 215 12.1.2可计算问题与不可计算问题 217 12.1.3易解问题与难解问题 218 12.2 P类问题与NP类问题 220 12.2.1判定问题 220 12.2.2确定性算法与P类问题 221 12.2.3非确定性算法与NP类问题 221 12.3 NP完全问题 222 12.3.1问题变换 222 12.3.2 NP完全问题的定义 223 12.3.3基本的NP完全问题 223 12.4拓展与演练 224 12.4.1 k带图灵机 224 12.4.2 NP类问题的计算机处理 225 实验12 SAT问题 226 习题12 226 第13章 近似算法 229 13.1概述 229 13.1.1近似算法的设计思想 229 13.1.2一个简单的例子:求π的近似值 230 13.2图问题中的近似算法 231 13.2.1顶点覆盖问题 231 13.2.2 TSP问题 232 13.3组合问题中的近似算法 233 13.3.1装箱问题 233 13.3.2多机调度问题 235 13.4拓展与演练 238 13.4.1带权顶点覆盖问题 238 13.4.2子集和问题 239 实验13 TSP问题的近似算法 242 习题13 243 第14章 概率算法 245 14.1概述 245 14.1.1概率算法的设计思想 245 14.1.2随机数生成器 246 14.2舍伍德型概率算法 247 14.2.1舍伍德型概率算法的设计思想 247 14.2.2快速排序 247 14.2.3二叉查找树 248 14.3拉斯维加斯型概率算法 250 14.3.1拉斯维加斯型概率算法的设计思想 250 14.3.2八皇后问题 250 14.3.3整数因子划分问题 251 14.4蒙特卡罗型概率算法 252 14.4.1蒙特卡罗型概率算法的设计思想 252 14.4.2主元素问题 253 14.4.3素数测试 254 14.5拓展与演练 255 14.5.1随机数与随机数生成器 255 14.5.2蒙特卡罗型算法计算定积分 256 实验14随机数生成器 257 习题14 257 第15章 群智能算法 259 15.1遗传算法 259 15.1.1遗传算法的基本思想 259 15.1.2遗传算法的关键问题 260 15.1.3应用举例 261 15.2蚁群算法 262 15.2.1蚁群算法的基本原理 262 15.2.2蚁群算法的参数设定 263 15.2.3应用举例 264 15.3粒子群算法 265 15.3.1粒子群算法的基本思想 265 15.3.2粒子群算法的参数分析 266 15.3.3应用举例 266 实验15函数的最大值 267 习题15 267 名词索引 269 参考文献 273 封底 273