计算机算法设计、分析与实现

章节摘录

版权页：   插图：   第8章分治算法 分治法顾名思义“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单地直接求解，原问题的解即子问题解的合并。这个技巧是很多高效算法的基础，如排序算法（快速排序、归并排序）、傅里叶变换（快速傅里叶变换）、……，任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算；当n=2时，只要作一次比较即可排好序；当n=3时，只要作3次比较即可，……；当咒较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。对于一个规模为n的问题，若该问题可以容易地解决（n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 分治法的设计思想是：将一个难以直接解决的大问题分割成一些规模较小的相同问题，以便各个击破，分而治之。 分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模，2较小）则直接解决；否则，将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。 如果原问题可分割成k个子问题（1

书籍目录

前言 第1章与算法相关的数学问题 1.1复杂性分析初步 1.1.1空间复杂度 1.1.2时间复杂度 1.2复杂性的计量 1.3数学归纳法 1.3.1第一数学归纳法 1.3.2第二数学归纳法 1.3.3结构归纳法 1.4生成函数 1.4.1基本性质 1.4.2生成函数的计算 1.5递归方程求解 1.5.1递推法 1.5.2公式解法 1.5.3母函数法 1.6 NP问题 思考题 第2章递归的应用 2.1第1类递归 2.2二叉树的递归遍历 2.3图的遍历 2.3.1图的深度优先搜寻法 2.3.2图的广度优先算法 2.4递归与非递归的转换 思考题 第3章迭代算法 3.1常见的迭代 3.2求方程的根 3.2.1牛顿迭代法 3.2.2二分法 3.2.3实例  3.3雅可比迭代法与高斯一塞德尔迭代法 3.3.1雅可比迭代法 3.3.2高斯一塞德尔迭代法 3.3.3迭代收敛的充分条件 思考题 第4章常见排序算法 4.1常见的内排序 4.1.1插入排序法 4.1.2交换排序 4.1.3选择排序 4.1.4基数排序 4.1.5归并排序 4.1.6计数排序 4.2算法性能分析 思考题 第5章动态规划法 5.1最短路径问题 5.1.1 Dijkstra算法 5.1.2 Bellman—Ford算法 5.1.3 Floyd算法 5.2最长公共子序列 5.3 01背包问题 5.4计算矩阵连乘积 5.5 Bitonic旅行路线问题 思考题 第6章回溯法 6.1 4皇后问题 6.2排列组合问题 6.3 01背包问题 6.4任务分配问题 6.5数码串珠 6.6桥本分数式 思考题 第7章贪心算法 7.1 01背包 7.2哈夫曼编码 7.3拓扑排序 7.4最小生成树 7.4.1 Kruskal算法 7.4.2 Prim算法 7.5汽车加油问题 思考题 第8章分治算法 8.1二分查找 8.2大整数的乘法 8.3棋盘覆盖问题 8.4循环赛日程表 8.5全排列 8.6矩阵乘法 思考题 第9章概率算法 9.1数值概率算法 9.1.1随机数 9.1.2用随机投点法计算pi值 9.1.3计算定积分 9.2舍伍德算法 9.3拉斯维加斯算法 9.4蒙特卡罗算法 思考题 第10章近似算法 10.1旅行售货员问题 10.2装箱问题 10.3集合覆盖问题 10.4子集和问题 思考题 第11章分支限界法 11.1 01背包 11.2最短路径 11.3装载问题 11.4旅行售货员问题 11.5布线问题 思考题 第12章遗传算法 12.1遗传算法的基本原理 12.1.1全局优化问题 12.1.2遗传编码 12.1.3群体设定 12.1.4适应度函数 12.1.5遗传算子 12.1.6循环终止条件 12.1.7控制参数 12.2 01背包问题 12.3旅行家问题 思考题 第13章蚁群算法 13.1蚁群算法简介 13.2 TSP问题 思考题 第14章查找 14.1查找的基本概念 14.1.1查找表和查找 14.1.2查找表的数据结构表示 14.1.3平均查找长度ASL 14.2顺序查找 14.2.1顺序查找方法适用于线性表的顺序存储结构 14.2.2顺序查找的平均查找长度 14.2.3该算法的优缺点 14.3二分查找 14.3.1基本思想 14.3.2查找算法 14.3.3平均查找长度 14.3.4二分查找的优点和缺点 14.4分块查找  14.4.1存储结构 14.4.2基本思想 14.4.3算法分析 14.4.4分块查找的优缺点 14.5二叉排序树的查找 14.6哈希查找 思考题 主要参考文献

编辑推荐

《计算机算法设计分析与实现》内容丰富，深入浅出，图例丰富，可作为计算机专业本科高年级学生和研究生学习算法的教材，也可供工程技术人员、软件设计师和自学者参考。

作者简介

算法设计、分析与实现是计算机软件开发人员应掌握的基本要素，在大型程序开发中越来越受到重视。《计算机算法设计分析与实现》将典型的经典问题和算法设计技术巧妙地进行结合，系统地论述算法设计技术及其在经典问题中的应用。《计算机算法设计分析与实现》共14章，第1章介绍算法的基本概念和算法分析相关的数学问题，第2～13章分别介绍递归的应用、迭代算法、常见排序算法、动态规划法、回溯法、贪心算法、分治算法、概率算法、近似算法、分支限界法、遗传算法、蚁群算法等算法设计技术，第14章介绍查找。书中所有算法均在VC6.0环境下调试通过，并截图显示其运行过程。

图书封面

---

 计算机算法设计、分析与实现下载

---