常用的算法思想.ppt

第三章 常用的算法思想 对对于计计算机科学而言，算法(Algorithm)是一个非常重 要的概念。它是程序设计设计 的灵魂，它是将实际问题实际问题 同解决 该问题该问题 的计计算机程序建立起联联系的桥桥梁。可以这样讲这样讲 ，我 们们在编编写任何一个计计算机程序时时（无论论使用什么编编程语语言 ），都不可回避地进进行算法的设计设计 。本章将重点介绍绍算法 的基本概念，以及一些常用的算法思想。 3.1 什么是算法 一个程序往往要包含两个方面的描述，一是对对数据组组 织织的描述；一是对对程序操作流程的描述。对对数据组织组织 的描 述主要是指定数据的类类型和数据的组织组织 形式（例如数组组） ，称作数据结结构（data structure），在下一节节将会讲讲到。 对对程序操作流程的描述就是程序的操作步骤骤，也本节节所要 介绍绍的所谓谓算法（algorithm）。正如Nikiklaus Wirth提出 的公式： 数据结结构+算法=程序 一样样，算法是一个程序中不可缺少的一部分。如果把 一个可运行的程序比喻喻成一个具有生命的人，那么数据结结构 就是这这个人的躯体，而算法则则是这这个人的灵魂或者说说精神 。 所谓谓算法，广义义地讲讲就是解决问题问题 的方法和过过程。 3.2算法的分类表示及测评 1、算法的分类类。 2、算法的表示。 3、算法性能的测评测评 3.3 穷举法思想 穷举穷举 法(Exhaustive Attack method)，又称为为强力法(Brute -force method)，它是一种最为为直接，实现实现 最为简单为简单 ，同时时又最 为为耗时时的一种解决实际问题实际问题 的算法思想。本节节将详细详细 介绍穷举绍穷举 法的算法思想。 3.3.1 基本概念 穷举穷举 法算法的基本思想是：在可能的解空间间中穷举穷举 出 每一种可能的解，并对对每一个可能解进进行判断，从中得到 问题问题 的答案。 使用穷举穷举 法思想解决实际问题实际问题 ，最关键键的步骤骤是划定 问题问题 的解空间间，并在该该解空间间中一一枚举举每一个可能的解 。这这里有两点需要注意。一是解空间间的划定必须须保证证覆盖 问题问题 的全部解。如果解空间间集合用H表示，问题问题 的解集用h 表示，那么只有当时时，才能使用穷举穷举 法求解。二是解空间间 集合及问题问题 的解集一定是离散的集合，也就是说说集合中的 元素是可列的、有限的。 3.3.2 寻找给定区间的素数 【实实例3-3】寻寻找1，100之间间的素数。 分析： 解决这这个问题问题 最简简便的方法就是使用穷举穷举 法。在1， 100中对对每一个整数进进行判断，看它是不是素数。在这这里 ，问题问题 的解空间间自然就是1，100中的全部整数，因为为不 会有任何一个解超出这这个范围围，同时该时该 解空间间构成的集合 元素是可列有限的。算法描述如下： for(i=1;i=100;i+) if (i是素数) 输输出i ; 判断一个数是否是素数的算法描述在3.2节节中已详细详细 介 绍绍，这这里不再赘赘述。 3.3.3 TOM的借书方案 【实实例3-4】TOM共有5本新书书，要借给给A,B,C三位同学， 每人只能借1本书书，则则TOM可以有多少种不同的借书书方法。 分析： 这这个问题问题 仍然可以用穷举穷举 法轻轻松地解决。假设设TOM的5 本书编书编 号为为1，2，3，4，5，每个同学可能借到的书书的范围围 就限定在1，2，3，4，5之中。因此TOM借书给书给 3位同学的 组组合方案不可能超过过53=125种。由这这125种借书书方案构成的解 空间间可描述为为(x1,x2,x3)|1xi5,且xiR，该该解空间间是由3 个各包含5个元素（图书编图书编 号）的集合排列组组合而成。应应用穷穷 举举法在该该空间间中搜索答案。 3.4 递归与分治思想 递归递归 与分治的算法思想往往是相伴而生的，它们们在各 类类算法中使用非常频频繁，应应用递归递归 和分治的算法思想有时时 可以设计设计 出代码简洁码简洁 且比较较高效的算法来。本章将详细详细 介 绍递归绍递归 与分治的算法思想。 3.4.1 基本概念 在解决一些比较较复杂杂的问题问题 ，特别别是解决一些规规模较较大 的问题时问题时 ，我们们常常将问题进问题进 行分解。具体来说说，就是将一 个规规模较较大的问题问题 分割成规规模较较小的同类问题类问题 ，然后将这这些 小的子问题问题 逐个加以解决，最终终也就将整个大的问题问题 解决了 。这这种分而治之的思想称作分治的思想。在解决一些问题问题 比 较较复杂杂、计计算量庞庞大的问题时经问题时经 常被用到。 一个最为经为经 典的使用分治思想设计设计 的算法就是第二章中 介绍过绍过 的“折半查查找算法”。折半查查找算法利用了元素之间间的 顺顺序关系（有序序列），采用分而治之的策略，不断缩缩小问问 题题的规规模，每次都将问题问题 的规规模减小至上一次的1/2。采用顺顺 序查查找的方法对对关键键字进进行搜索的时间时间 复杂杂度为为O(n)，而采 用折半查查找方法的时间时间 复杂杂度仅为仅为 O(log2n)。 3.4.2 计算整数的划分数 【实实例3-6】将一个正整数n表示成一系列的正整数之 和： 被称作正整数n的一个划分。一个正整数n可能存在着 不同的划分，例如正整数6的全部的划分为为： 6=6 6=5+1 6=4+2 6=4+1+1 6=3+3 6=3+2+1 6=3+1+1+1 6=2+2+2 6=2+2+1+1 6=2+1+1+1+1 6=1+1+1+1+1+1 3.4.3 递归的折半查找算法 【实实例3-7】有一个数组组A10，里面存放了10个整数， 顺顺序递递增。 A10 = 2,3,5,7,8,10,12,15,19,21 任意输输入一个用数字n，用折半查查找法找到n位于数组组中 的位置。如果n不属于数组组A，显显示错误错误 提示。要求用递归递归 的 方法实现实现 折半查查找。 分析： 在第二章中曾详细详细 地介绍过绍过 折半查查找的算法，它是一种 针对针对 有序序列（或文件记录记录 ）的高效的查查找算法。折半查查找 的基本思想是：减小查查找序列的长长度。它的查查找过过程是：先 确定待查查找记录记录 的所在的范围围，然后逐渐缩渐缩 小查查找的范围围， 直至找到该记录为该记录为 止（也可能查查找失败败）。因此它也是一种 基于分治的算法思想设计设计 出来的查查找算法。 3.5 贪心算法思想 贪贪心算法的思想非常简单简单 而且算法效率很高，在一些 问题问题 的解决上有着明显显的优势优势 。本章将详细详细 介绍贪绍贪 心算法 的基本思想。 3.5.1 基本概念 所谓贪谓贪 心算法，就是总总是做出在当前看来是最好的选选 择择的一种方法。以上述的找零钱为钱为 例，为为了找给顾给顾 客的硬 币币数量最少，在选择选择 硬币币的面值时值时 ，当然是尽可能地选择选择 面值值大的硬币币。因此严严格意义义上讲讲，要使用贪贪心算法求解 问题问题 ，该问题应该问题应 当具备备以下性质质。 （1）贪贪心选择选择 性质质： （2）最优优子结结构性质质： 3.5.2 最优装船问题 【实实例3-8】有一批集装箱要装入一个载载重量为为C的货货船 中，每个集装箱的重量由用户户自己输输入指定，在货货船的装载载 体积积不限的前提下，如何装载载集装箱才能尽可能多地将集装箱 装入货货船中。 分析： 这这个问题问题 可以用贪贪心算法求得最优优解。只要每次装船时时 ，采取重量最轻轻的集装箱先装船的策略，就可以得到最优优装船 问题问题 的一个最优优解。 3.6 回溯法 回溯法是一种非常有效，适用范围围相当广泛的算法设设 计计思想。许许多复杂杂的问题问题 ，规规模较较大的问题问题 都可以使用回 溯法求解。因此回溯法又有“通用解题题方法”的美称。本章 将详细详细 介绍绍回溯法的算法思想。 3.6.1 基本概念 回溯法的基本思想是：在包含问题问题 的所有解的解空间间 树树中，按照深度优优先搜索的策略，从根结结点出发发深度探索 解空间树间树 。当探索到某一结结点时时，要先判断该结该结 点是否包 含问题问题 的解，如果包含，就从该结该结 点出发继续发继续 探索下去； 如果该结该结 点不包含问题问题 的解，那就说说明以该结该结 点为为根结结点 的子树树一定不包含问题问题 的最终终解，因此要跳过对过对 以该结该结 点 为为根的子树树的系统统探索，逐层层向其祖先结结点回溯。这这个过过 程叫做解空间树间树 的“剪枝”操作。 如果应应用回溯法求解问题问题 的所有解，要回溯到解空间间 树树的树树根，这样这样 根结结点的所有子树树都被探索到才结结束。如 果只要求解问题问题 的一个解，那么在探索解空间树时间树时 ，只要 搜索到问题问题 的一个解就可以结结束了。 3.6.2 四皇后问题求解 【实实例3-9】应应用回溯法的思想求解四皇后问题问题 。 分析： 上面一节节中已经详细经详细 介绍绍了回溯法解决四皇后问题问题 的 基本过过程。在这这里将给给出具体的算法描述和程序清单单。 其实实在解决四皇后问题时问题时 ，并不一定要真的构建出这这 样样一棵解空间树间树 ，它完全可以通过过一个递归递归 回溯来模拟拟。 所谓谓解空间树间树 只是一个逻辑逻辑 上的抽象。当然也可以用树结树结 构来真实实地创创建出一棵解空间树间树 ，不过过那样样会比较较浪费费空 间资间资 源。 3.7 数值概率算法 在解决实际问题时实际问题时 ，有时时会用到所谓谓的概率算法。概 率算法允许许在执执行过过程中随机地选择选择 下一步的计计算步骤骤， 因此使用概率算法有时时会大大地提高算法的效率，但有时时也 可能得不到问题问题 的全部答案。 3.7.1 基本概念 概率算法大致分为为四类类：数值值概率算法，蒙特卡洛 (Monte Carlo)算法，拉斯维维加斯(Las Vegas)算法，和舍伍 德(Sherwood)算法。这这里只介绍绍最为为基础础的数值值概率算法 。 数值值概率算法常应应用于解决数值计值计 算的问题问题 。应应用数 值值概率算法往往只能得到问题问题 的近似解，并且该该近似解的精 度一般随着计计算时间时间 的增加而不断提高。因为为在一些数值问值问 题题中，不可能也没有必要计计算出问题问题 的精确解（例如：计计算 无理数的取值值等），因此，在解决一些数值计值计 算的问题时问题时 ，数值值概率算法常能派上用场场。 3.7.2 计算定积分 【实实例3-10】设