本书以“算法概述→算法框架(或步骤)→算法设计→算法分析”为技术线路,系统地介绍了各种常用的算法设计策略,包括穷举法、分治法、回溯法、分支限界法、动态规划和贪心法等,并以专题形式讨论了图算法、计算几何、概率算法和近似算法设计原理及其应用,帮助读者迅速掌握算法设计要点,规范算法设计、分析及实现的方法。书中列举了大量的经典示例和在线编程示例并予以解析,全方位地帮助读者提高算法设计与分析实践能力和理论水平。 本书既便于教师课堂讲授,又便于自学者阅读,适合作为高等学校计算机及相关专业学生的算法设计与分析课程教材,也可供ACM和各类程序设计竞赛者学习参考。

扫一扫 源码下载 第1章绪论/ 1.1算法概述/ 1.1.1什么是算法/ 1.1.2算法描述/ 1.1.3算法设计的基本步骤/ 1.2算法分析/ 1.2.1算法时间复杂度分析/ 1.2.2算法空间复杂度分析/ 1.3算法设计工具——STL/ 1.3.1STL概述/ 1.3.2vector(向量容器)/ 1.3.3string(字符串容器)/ 1.3.4deque(双端队列容器)/ 1.3.5list(链表容器)/ 1.3.6stack(栈容器)/ 1.3.7queue(队列容器)/ 1.3.8priority_queue(优先队列容器)/ 1.3.9set(集合容器)/multiset(多重集合容器)/ 1.3.10map(映射容器)/multimap(多重映射容器)/ 1.3.11unordered_set(哈希集合容器)/ 1.3.12unordered_map(哈希映射容器)/ 1.4练习题/ 1.5在线编程实验题/ 第2章递归算法设计技术/ 2.1递归概述/ 2.1.1什么是递归/ 2.1.2何时使用递归/ 2.1.3递归模型/ 2.1.4递归算法的执行过程/ 2.1.5递归算法的时间复杂度和空间复杂度分析/ 2.2递归算法的设计方法/ 2.2.1递归与数学归纳法/ 2.2.2递归算法设计的一般步骤/ 2.2.3基于递归数据结构的递归算法设计/ 2.2.4基于归纳思想的递归算法设计/ 2.3直接插入排序/ 2.40/1背包问题/ 2.5求表达式的值/ 2.6计算递推式/ 2.6.1直接展开法/ 2.6.2递归树方法/ 2.6.3主方法/ 2.6.4*特征方程方法/ 2.7练习题/ 2.8在线编程实验题/ 第3章穷举法/ 3.1穷举法概述/ 3.1.1什么是穷举法/ 3.1.2穷举算法的框架/ 3.2算法优化中常用的数据结构/ 3.2.1前缀和数组/ 3.2.2并查集/ 3.3求回文串的个数/ 3.4求*大连续子序列和/ 3.5求幂集/ 3.60/1背包问题/ 3.7求全排列/ 3.8n皇后问题/ 3.9任务分配问题/ 3.10旅行商问题/ 3.11练习题/ 3.12在线编程实验题/ 第4章分治法/ 4.1分治法概述/ 4.1.1什么是分治法/ 4.1.2分治法的求解过程/ 4.1.3分治算法分析/ 4.2快速排序/ 4.3二路归并排序/ 4.4二分查找/ 4.4.1基本二分查找/ 4.4.2二分查找的扩展/ 4.5求*大连续子序列和/ 4.6棋盘覆盖问题/ 4.7循环日程安排问题/ 4.8旅行商问题/ 4.9练习题/ 4.10在线编程实验题/ 第5章回溯法/ 5.1回溯法概述/ 5.1.1问题的解空间/ 5.1.2什么是回溯法/ 5.1.3回溯算法分析/ 5.2基于子集树的回溯算法框架/ 5.2.1解空间树的类型/ 5.2.2求幂集/ 5.2.3子集树回溯算法框架/ 5.3图的路径搜索/ 5.4构造表达式/ 5.5图的m着色问题/ 5.6子集和问题/ 5.7简单装载问题/ 5.80/1背包问题/ 5.9*完全背包问题/ 5.10基于排列树的回溯算法框架/ 5.10.1求全排列/ 5.10.2排列树回溯算法框架/ 5.11n皇后问题/ 5.12任务分配问题/ 5.13旅行商问题/ 5.14练习题/ 5.15在线编程实验题/ 第6章分支限界法/ 6.1分支限界法概述/ 6.1.1什么是分支限界法/ 6.1.2分支限界法的设计要点/ 6.1.3分支限界法的时间性能/ 6.2广度优先搜索/ 6.2.1图的广度优先搜索/ 6.2.2广度优先搜索的应用/ 6.3队列式分支限界法的框架/ 6.4图的单源*短路径/ 6.50/1背包问题(1)/ 6.6优先队列式分支限界法的框架/ 6.70/1背包问题(2)/ 6.8任务分配问题/ 6.9旅行商问题/ 6.10*A*算法及其应用/ 6.10.1A*算法概述/ 6.10.2启发式函数/ 6.11练习题/ 6.12在线编程实验题/ 第7章动态规划/ 7.1动态规划概述/ 7.1.1从一个简单的示例入门/ 7.1.2动态规划的原理/ 7.1.3动态规划求解问题的类型、性质和步骤/ 7.1.4动态规划与其他方法的比较/ 7.2求*大连续子序列和/ 7.3*长递增子序列/ 7.4三角形的*小路径和/ 7.5*长公共子序列/ 7.6编辑距离/ 7.70/1背包问题/ 7.8*完全背包问题和多重背包问题/ 7.8.1完全背包问题/ 7.8.2多重背包问题/ 7.9扔鸡蛋问题/ 7.10资源分配问题/ 7.11旅行商问题/ 7.12*少士兵数问题/ 7.13矩阵连乘问题/ 7.14练习题/ 7.15在线编程实验题/ 第8章贪心法/ 8.1贪心法概述/ 8.1.1什么是贪心法/ 8.1.2用贪心法求解的问题具有的性质/ 8.1.3用贪心法求解问题的一般过程/ 8.2区间问题/ 8.2.1*大兼容区间个数/ 8.2.2区间合并/ 8.2.3**少资源问题/ 8.3背包问题/ 8.4田忌赛马问题/ 8.5零钱兑换问题/ 8.6哈夫曼编码/ 8.7*拟阵/ 8.7.1拟阵概述/ 8.7.2求加权拟阵*优子集的贪心算法/ 8.7.3带期限和惩罚的任务调度问题/ 8.8练习题/ 8.9在线编程实验题/ 第9章图算法/ 9.1图的*小生成树/ 9.1.1什么是*小生成树/ 9.1.2Prim算法/ 9.1.3Kruskal算法/ 9.2图的*短路径/ 9.2.1Dijkstra算法/ 9.2.2BellmanFord算法/ 9.2.3SPFA算法/ 9.2.4Floyd算法/ 9.3网络流/ 9.3.1问题的引入/ 9.3.2FordFulkerson算法/ 9.3.3EdmondsKrap算法/ 9.3.4Dinic算法/ 9.4练习题/ 9.5在线编程实验题/ 第10章计算几何/ 10.1向量运算/ 10.1.1向量的基本运算/ 10.1.2判断点是否在矩形内/ 10.1.3判断点是否在线段上/ 10.1.4判断两条线段是否平行/ 10.1.5判断两条线段是否相交/ 10.1.6判断点是否在多边形内/ 10.1.7求3个点构成的三角形的面积/ 10.1.8求多边形的面积/ 10.2凸包问题/ 10.2.1礼品包裹算法/ 10.2.2Graham算法/ 10.3*近点对问题/ 10.3.1用穷举法求*近点对/ 10.3.2用分治法求*近点对/ 10.4*远点对问题/ 10.4.1用穷举法求*远点对/ 10.4.2用旋转卡壳法求*远点对/ 10.5练习题/ 10.6在线编程实验题/ 第11章计算复杂性/ 11.1P类和NP类/ 11.1.1易解问题和难解问题/ 11.1.2判定问题和优化问题/ 11.1.3计算模型/ 11.1.4P类问题/ 11.1.5NP类问题/ 11.2多项式时间变换和问题归约/ 11.3NP完全问题/ 11.3.1什么是NP完全问题和NP难问题/ 11.3.2**个NP完全问题/ 11.3.3其他NP完全问题/ 11.4练习题/ 第12章概率算法和近似算法/ 12.1概率算法/ 12.1.1什么是概率算法/ 12.1.2数值概率算法/ 12.1.3蒙特卡洛算法/ 12.1.4拉斯维加斯算法/ 12.1.5舍伍德算法/ 12.2近似算法/ 12.2.1什么是近似算法/ 12.2.2多机调度问题的近似算法/ 12.2.30/1背包问题的近似算法/ 12.2.4旅行商问题的近似算法/ 12.3练习题/ 参考文献/