✍ Scribed by 王晓东
No coin nor oath required. For personal study only.
本书是《算法设计与分析（第4版）》配套辅助教材。本书将结合原教材的内容，进一步讨论和讲解原教材中的重点和难点，问题分析，求解思路和方法，为读者深刻体会问题求解的核心思想提供帮助。由于原教材的内容有一定的深度和难度，读者在学习和解答习题过程中会遇到一定的困难，因此本书选择了原教材的一些典型的习题和难题，给出详细的解答和分析。 本书内容丰富，观点新颖，理论联系实际。不仅可用作高等学校计算机专业本科生和研究生学习计算机算法设计的教材，而且也适合广大工程技术人员和自学读者学习参考。
封面
扉页
内容简介
版权页
21世纪大学本科计算机专业系列教材编委会
前言
目录
第1章 算法引论
习题1-1 实际参数交换
习题1-2 方法头签名
习题1-3 数组排序判定
习题1-4 函数的渐近表达式
习题1-5 O(1)和O(2)的区别
习题1-6 按渐近阶排列表达式
习题1-7 算法效率
习题1-8 硬件效率
习题1-9 函数渐近阶
习题1-10 n!的阶
习题1-11 平均情况下的计算时间复杂性
算法实现题1-1 统计数字问题
算法实现题1-2 字典序问题
算法实现题1-3 最多约数问题
算法实现题1-4 金币阵列问题
算法实现题1-5 最大间隙问题
第2章 递归与分治策略
习题2-1 Hanoi塔问题的非递归算法
习题2-2 7个二分搜索算法
习题2-3 改写二分搜索算法
习题2-4 大整数乘法的O(nmlog(3/2))算法
习题2-5 5次n/3位整数的乘法
习题2-6 矩阵乘法
习题2-7 多项式乘积
习题2-8 不动点问题的O(logn)时间算法
习题2-9 主元素问题的线性时间算法
习题2-10 无序集主元素问题的线性时间算法
习题2-11 O(1)空间子数组换位算法
习题2-12 O(1)空间合并算法
习题2-13 n段合并排序算法
习题2-14 自然合并排序算法
习题2-15 最大值和最小值问题的最优算法
习题2-16 最大值和次大值问题的最优算法
习题2-17 整数集合排序
习题2-18 第k小元素问题的计算时间下界
习题2-19 非增序快速排序算法
习题2-20 随机化算法
习题2-21 随机化快速排序算法
习题2-22 随机排列算法
习题2-23 算法qSort中的尾递归
习题2-24 用栈模拟递归
习题2-25 算法select中的元素划分
习题2-26 O(nlogn)时间快速排序算法
习题2-27 最接近中位数的k个数
习题2-28 X和Y的中位数
习题2-29 网络开关设计
习题2-30 带权中位数问题
习题2-31 构造Gray码的分治算法
习题2-32 网球循环赛日程表
算法实现题2-1 输油管道问题
算法实现题2-2 众数问题
算法实现题2-3 邮局选址问题
算法实现题2-4 马的Hamilton周游路线问题
算法实现题2-5 半数集问题
算法实现题2-6 半数单集问题
算法实现题2-7 士兵站队问题
算法实现题2-8 有重复元素的排列问题
算法实现题2-9 排列的字典序问题
算法实现题2-10 集合划分问题(一)
算法实现题2-11 集合划分问题(二)
算法实现题2-12 双色Hanoi塔问题
算法实现题2-13 标准二维表问题
算法实现题2-14 整数因子分解问题
算法实现题2-15 有向直线2中值问题
第3章 动态规划
习题3-1 最长单调递增子序列
习题3-2 最长单调递增子序列的O(nlogn)算法
习题3-3 漂亮打印
习题3-4 整数线性规划问题
习题3-5 二维背包问题
习题3-6 Ackermann函数
算法实现题3-1 独立任务最优调度问题
算法实现题3-2 最少硬币问题
算法实现题3-3 序关系计数问题
算法实现题3-4 多重幂计数问题
算法实现题3-5 最小m段和问题
算法实现题3-6 石子合并问题
算法实现题3-7 数字三角形问题
算法实现题3-8 乘法表问题
算法实现题3-9 租用游艇问题
算法实现题3-10 汽车加油行驶问题
算法实现题3-11 圈乘运算问题
算法实现题3-12 最少费用购物
算法实现题3-13 最大长方体问题
算法实现题3-14 正则表达式匹配问题
算法实现题3-15 双调旅行售货员问题
算法实现题3-16 最大k乘积问题
第4章 贪心算法
习题4-1 活动安排问题的贪心选择
习题4-2 背包问题的贪心选择性质
习题4-3 特殊的0-1背包问题
习题4-4 程序最优存储问题
习题4-5 最优装载问题的贪心算法
习题4-6 Fibonacci序列的Huffman编码
习题4-7 最优前缀码的编码序列
习题4-8 任务集独立性问题
习题4-9 矩阵拟阵
习题4-10 最小权最大独立子集拟阵
习题4-11 整数边权Prim算法
习题4-12 最大权最小生成树
习题4-13 最短路径的负边权
习题4-14 整数边权Dijkstra算法
算法实现题4-1 会场安排问题
算法实现题4-2 最优合并问题
算法实现题4-3 磁带最优存储问题
算法实现题4-4 磁盘文件最优存储问题
算法实现题4-5 程序存储问题
算法实现题4-6 最优服务次序问题
算法实现题4-7 多处最优服务次序问题
算法实现题4-8 d森林问题
算法实现题4-9 汽车加油问题
算法实现题4-10 区间覆盖问题
算法实现题4-11 硬币找钱问题
算法实现题4-12 删数问题
算法实现题4-13 数列极差问题
算法实现题4-14 嵌套箱问题
算法实现题4-15 套汇问题
算法实现题4-16 信号增强装置问题
算法实现题4-17 磁带最大利用率问题
算法实现题4-18 非单位时间任务安排问题
算法实现题4-19 多元Huffman编码问题
算法实现题4-20 多元Huffman编码变形
算法实现题4-21 区间相交问题
算法实现题4-22 任务时间表问题
第5章 回溯法
习题5-1 装载问题改进回溯法(一)
习题5-2 装载问题改进回溯法(二)
习题5-3 0-1背包问题的最优解
习题5-4 最大团问题的迭代回溯法
习题5-5 旅行售货员问题的费用上界
习题5-6 旅行售货员问题的上界函数
算法实现题5-1 子集和问题
算法实现题5-2 最小长度电路板排列问题
算法实现题5-3 最小重量机器设计问题
算法实现题5-4 运动员最佳匹配问题
算法实现题5-5 无分隔符字典问题
算法实现题5-6 无和集问题
算法实现题5-7 n色方柱问题
算法实现题5-8 整数变换问题
算法实现题5-9 拉丁矩阵问题
算法实现题5-10 排列宝石问题
算法实现题5-11 重复拉丁矩阵问题
算法实现题5-12 罗密欧与朱丽叶的迷宫问题
算法实现题5-13 工作分配问题
算法实现题5-14 独立钻石跳棋问题
算法实现题5-15 智力拼图问题
算法实现题5-16 布线问题
算法实现题5-17 最佳调度问题
算法实现题5-18 无优先级运算问题
算法实现题5-19 世界名画陈列馆问题
算法实现题5-20 世界名画陈列馆问题(不重复监视)
算法实现题5-21 部落卫队问题
算法实现题5-22 虫蚀算式问题
算法实现题5-23 完备环序列问题
算法实现题5-24 离散01串问题
算法实现题5-25 喷漆机器人问题
算法实现题5-26 n2－1谜问题
第6章 分支限界法
习题6-1 0-1背包问题的栈式分支限界法
习题6-2 用最大堆存储活结点的优先队列式分支限界法
习题6-3 团顶点数的上界
习题6-4 团顶点数改进的上界
习题6-5 修改解旅行售货员问题的分支限界法
习题6-6 解旅行售货员问题的分支限界法中保存已产生的排列树
习题6-7 电路板排列问题的队列式分支限界法
算法实现题6-1 最小长度电路板排列问题(一)
算法实现题6-2 最小长度电路板排列问题(二)
算法实现题6-3 最小权顶点覆盖问题
算法实现题6-4 无向图的最大割问题
算法实现题6-5 最小重量机器设计问题
算法实现题6-6 运动员最佳匹配问题
算法实现题6-7 n后问题
算法实现题6-8 圆排列问题
算法实现题6-9 布线问题
算法实现题6-10 最佳调度问题
算法实现题6-11 无优先级运算问题
算法实现题6-12 世界名画陈列馆问题
算法实现题6-13 骑士征途问题
算法实现题6-14 推箱子问题
算法实现题6-15 图形变换问题
算法实现题6-16 行列变换问题
算法实现题6-17 重排n2宫问题
算法实现题6-18 最长距离问题
第7章 概率算法
习题7-1 模拟正态分布随机变量
习题7-2 随机抽样算法
习题7-3 随机产生m个整数
习题7-4 集合大小的概率算法
习题7-5 生日问题
习题7-6 易验证问题的拉斯维加斯算法
习题7-7 用数组模拟有序链表
习题7-8 O(n3/2)舍伍德型排序算法
习题7-9 n后问题解的存在性
习题7-10 整数因子分解算法
习题7-11 非蒙特卡罗算法的例子
习题7-12 重复3次的蒙特卡罗算法
习题7-13 集合随机元素算法
习题7-14 由蒙特卡罗算法构造拉斯维加斯算法
习题7-15 产生素数算法
习题7-16 矩阵方程问题
算法实现题7-1 模平方根问题
算法实现题7-2 集合相等问题
算法实现题7-3 逆矩阵问题
算法实现题7-4 多项式乘积问题
算法实现题7-5 皇后控制问题
算法实现题7-6 3-SAT问题
算法实现题7-7 战车问题
算法实现题7-8 圆排列问题
算法实现题7-9 骑士控制问题
算法实现题7-10 骑士对攻问题
第8章 NP完全性理论与近似算法
习题8-1 析取范式的可满足性
习题8-2 2-SAT问题的线性时间算法
习题8-3 整数规划问题
习题8-4 划分问题
习题8-5 最长简单回路问题
习题8-6 平面图着色问题的绝对近似算法
习题8-7 最优程序存储问题
习题8-8 树的最优顶点覆盖
习题8-9 顶点覆盖算法的性能比
习题8-10 团的常数性能比近似算法
习题8-11 售货员问题的常数性能比近似算法
习题8-12 瓶颈旅行售货员问题
习题8-13 最优旅行售货员回路不自相交
习题8-14 集合覆盖问题的实例
习题8-15 多机调度问题的近似算法
习题8-16 LPT算法的最坏情况实例
习题8-17 多机调度问题的多项式时间近似算法
算法实现题8-1 旅行售货员问题的近似算法
算法实现题8-2 可满足问题的近似算法
算法实现题8-3 最大可满足问题的近似算法
算法实现题8-4 子集和问题的近似算法
算法实现题8-5 子集和问题的完全多项式时间近似算法
算法实现题8-6 实现算法greedySetCover
算法实现题8-7 装箱问题的近似算法First Fit
算法实现题8-8 装箱问题的近似算法Best Fit
算法实现题8-9 装箱问题的近似算法First Fit Decreasing
算法实现题8-10 装箱问题的近似算法Best Fit Decreasing
算法实现题8-11 装箱问题的近似算法Next Fit
第9章 串与序列的算法
习题9-1 简单子串搜索算法最坏情况复杂性
习题9-2 后缀重叠问题
习题9-3 改进前缀函数
习题9-4 确定所有匹配位置的KMP算法
习题9-5 特殊情况下简单子串搜索算法的改进
习题9-6 简单子串搜索算法的平均性能
习题9-7 带间隙字符的模式串搜索
习题9-8 串接的前缀函数
习题9-9 串的循环旋转
习题9-10 失败函数性质
习题9-11 输出函数性质
习题9-12 后缀数组类
习题9-13 最长公共扩展查询
习题9-14 最长公共扩展性质
习题9-15 后缀数组性质
习题9-16 后缀数组搜索
习题9-17 后缀数组快速搜索
算法实现题9-1 安全基因序列问题
算法实现题9-2 最长重复子串问题
算法实现题9-3 最长回文子串问题
算法实现题9-4 相似基因序列性问题
算法实现题9-5 计算机病毒问题
算法实现题9-6 带有子串包含约束的最长公共子序列问题
算法实现题9-7 多子串排斥约束的最长公共子序列问题
第10章 算法优化策略
习题10-1 算法obst的正确性
习题10-2 矩阵连乘问题的O(n2)时间算法
习题10-3 货物储运问题的费用
习题10-4 Garsia算法
算法实现题10-1 货物储运问题
算法实现题10-2 石子合并问题
算法实现题10-3 最大运输费用货物储运问题
算法实现题10-4 五边形问题
算法实现题10-5 区间图最短路问题
算法实现题10-6 圆弧区间最短路问题
算法实现题10-7 双机调度问题
算法实现题10-8 离线最小值问题
算法实现题10-9 最近公共祖先问题
算法实现题10-10 达尔文芯片问题
算法实现题10-11 多柱Hanoi塔问题
算法实现题10-12 线性时间Huffman算法
算法实现题10-13 单机调度问题
算法实现题10-14 最大费用单机调度问题
算法实现题10-15 飞机加油问题
第11章 在线算法设计
习题11-1 在线算法LFU的竞争性
习题11-2 多读写头磁盘问题的在线算法
习题11-3 带权页调度问题
算法实现题11-1 最优页调度问题
算法实现题11-2 在线LRU页调度
算法实现题11-3 k服务问题
正文结束
参考文献
近期出版书目
📜 SIMILAR VOLUMES
为了适应培养我国２１世纪计算机各类人才的需要，结合我国高等学校教育工作的现状，立足培养学生能跟上国际计算机科学技术的发展水平，更新教学内容和教学方法，提高教学质量，本书以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为计算机科学与技术学科的学生提供广泛而坚实的计算机算法基础知识。另有配套的《算法设计与分析（第4版）习题解答》，对本书的全部习题做了详尽的解答。 本书内容丰富，观点新颖，理论联系实际。不仅可用作高等学校计算机专业本科生和研究生学习计算机算法设计的教材，而且也适合广大工程技术人员和自学读者学习参考。
本书是作者在多年从事算法设计与分析课程教学和研究的基础上编写而成，系统地介绍了算法设计与分析的理论、方法和技术。内容围绕两条主线来组织。一条主线是介绍典范性的算法问题，如排序、选择、图遍历等。 另一条主线是介绍典范性的算法设计分析策略，如分治、贪心、动态规划等算法设计策略和对手分析、平摊分析等算法分析策略。本书中两条主线交替进行，每条主线又各自分为基本和进阶两部分。 已附上书签
《算法设计与分析》系统地介绍了算法设计与分析的概念和方法，共4篇内容。第1篇介绍算法设计与分析的基本概念，结合穷举法、排序问题及其他一些算法，对算法的时间复杂性的概念及复杂性的分析方法作了较为详细的叙述；第2篇以算法设计技术为纲，从合并排序、堆排序、离散集合的union和find操作开始，进而介绍递归技术、分治法、贪婪法、动态规划、回溯法、分支与限界法和随机算法等算法设计技术及其复杂性分析；第3篇介绍计算机应用领域里的一些算法，如图和网络流，以及计算几何中的一些问题；第4篇介绍算法设计与分析中的一些理论问题，如NP完全问题、计算复杂性问题、下界理论问题，最后介绍近似算法及其性能分析。 《算法
<p>本书为计算机类专业核心课程“算法设计与分析”教材. 全书以算法设计技术和分析方法为主线来组织各知识单元. 主要内容包括基础知识、分治策略、动态规划、贪心法、回溯与分支限界、线性规划、网络流算法、算法分析与问题的计算复杂度、NP完全性、近似算法、随机算法、处理难解问题的策略等. 力求突出对问题本身的分析和求解方法的阐述，从问题建模、算法设计与分析、改进措施等方面给出适当的建议，同时也简要介绍了计算复杂性理论的核心内容和处理难解问题的一些新技术.</p>
<p>本书将经典问题和算法设计技术结合，以读者容易理解和接受的方式，系统介绍了算法设计技术，包括模拟法、递推法、蛮力法、分治法、减治法、贪心法、动态规划法、深度优先搜索、广度优先搜索、回溯法、A*算法、限界剪枝法、近似算法、概率算法和群智能算法；同时以通俗易懂的方式，系统介绍了算法分析技术，包括算法的时间复杂度分析、空间复杂度分析、算法、确定性算法、非确定性算法、P类问题、NP类问题和NP完全问题。所有问题都用伪代码给出了算法描述，并提供了C++语言程序源码，且在C++语言的典型编程环境下调试通过。 本书案例丰富，叙述清晰，深入浅出，结合应用，符合算法学习者的认知规律，可作为高等院校计算机专