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