《可视化计算》算法综合-加工了的.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,基本算法和策略,西安交大,可视化计算,学习目标,程序与算法有哪些异同,?,算法有哪些基本特性？,算法的效率如何度量？,如何为算法设计做准备？,2,算法定义,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。,通俗来说，就是通过计算来解决问题的过程，在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法,不同的是：前者是推理实现的算法，后者是操作实现的算法,所以，,程序是使用计算机实现的算法,；而,算法则不一定需要有计算机,才能实现,3,算法的特性,算法具有五个基本特性：,输入,（,具有,零个,或多个输入,）,输出,（,一或多,个输出）,有穷性,（,自动结束,而不会出现无限循环,）,确定性,（,每一步骤的含义，,不会,出现二义性,）,可行性,（,能够通过执行,有限次数,完成,）,4,算法设计的要求,正确性,可读性,健壮性,时间效率高,存储量需求低,5,正确性,的层次,算法程序没有语法错误,;,算法程序对于合法的输入数据能够产生满足要求的输出结果,;,算法程序对于非法的输入数据能够得出满足规格说明的结果,;,算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。,6,可读性,为了便于阅读、理解和交流,，,可读性,要素：,增加算法文件名、子图、子程序、算法样本数据文件名的可读性；,在算法语句中增加注,释,语句，说明重要变量、决策语句的用途；,将算法有关的文档整理在一个目录中,7,健壮性,能对输入数据不合法的情况做合适的处理,比如输入的时间或者距离不应该是负数,算法的健壮性表现在当输入数据不合法时，算法也能做出相关处理，而不是产生异常或无法解释的结果,8,时间效率高和存储量需求低,对于同一个问题，如果有多个算法能够达到同样的问题解决标准，执行时间最短的算法效率最高,存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间,，越少越好,9,算法效率的度量,一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素,：,编译产生的代码质量,；,算法采用的策略、方法,；,问题的输入规模,；,机器执行指令的速度。,10,2-end,学习目标,什么是基本算法？,哪些算法在计算问题求解中最为常用？,算法与算法策略有何区别？,哪些基本的算法策略在各种算法解决方案中被普遍采用,?,12,基本算法,蛮力法,分段函数,递推法,模运算,字符和字符串运算,递归,组合计算,迭代法,13,蛮力法,计算机问题求解的第一号方法被称为蛮力法,(,Brute Force,),，也称穷举法,采用蛮力算法解题的基本思路：,确定穷举对象、穷举范围和判定条件；,一一穷举可能的解，验证是否是问题的解,在蛮力算法中，穷举,对象的选择,也是非常重要的，它直接影响着算法的时间复杂度，选择适当的穷举对象可以获得更高的效率,14,百钱买百鸡问题,某个人有一百块钱，打算买一百只鸡。到市场上一看，公鸡五块钱一只，母鸡三块钱一只，小鸡一块钱三只。现在，请编一个算法，算出如何能刚好用一百块钱买一百只鸡,?,15,蛮力法求解,三种鸡的个数为穷举对象,分别设为,x,，,y,，,z,以三种鸡的总数（,x+y+z,）和买鸡用去的钱的总数,(x*5+y*3+z/3),为判定条件，穷举各种鸡的个数,由于三种鸡的和是固定的，只要穷举二种鸡（,x,，,y,），第三种鸡就可以根据约束条件求得（,z=100-x-y,），这样就,缩小了穷举范围,16,求解流程图,如果需要解决的问题规模不大,用蛮力法设计的算法其速度是可以接受的,17,分段函数,收费问题与我们的生活息息相关，如水费问题、电费问题、话费问题等,这些收费问题往往根据不同的用量，采用不同的收费方式,以收费为题材的数学问题多以分段函数的形式出现,18,阶梯电价问题,为鼓励节约用电，某市开始采取按月用电量分段收费办法，某户居民每月应交电费,y,（元）与用电量,x,（度）的函数如下：,请设计上述电费的收费算法。,19,阶梯电价流程图,20,分段函数求解中的,问题,最常见,的,错,误,的是将函数的数学表达式直接搬到算法中，例如：“,0=x=100,”,；,函数定义中，没有定义,x1,时）,42,斐波那契数列,的递归求解,43,递归的辨识,斐波那契递归,实现,，调用一次产生二个新的递归，调用次数呈指数增长，时间复杂度为,O,（,2,n,）。,这种使用递归的方式，被称为“,天真的递归（,Naive recursion,）,”。,而使用,递推算法,求,斐波那契,数列,，时间复杂度只是为,O,（,n,）,44,数论问题,数论的本质是对素数性质的研究,2000,多年前，欧几里得证明了有无穷个素数。寻找表示所有素数的,素数通项公式,，或者叫素数普遍公式，是古典数论最主要的问题之一,加法、减法和乘法这三种运算，在整数范围内可以毫无阻碍地进行,整数之间的除法,在整数范围内并不一定能够无阻碍地进行,大数密码体系,，至今仍然关系着国家的安全,45,测素子程序,测素子程序是解决数论问题的核心，所以在数论应用算法中，几乎都要用到。,因此它的计算效率，直接影响与数论相关的算法效率,46,一个测素子程序,如何改善测素子程序的效率？,47,组合计算,计算一些物品在特定条件下分组方法的数目。这些是关于,排列,、,组合,和整数分拆问题的求解，属于组合数学研究的范畴,例如，求解从,n,个元素中取出,m,个元素的不同组合，用,C(n,m,),表示。根据组合的性质有如下公式成立：,1.,C(n,，,m)=,n!/(m,!*(,n-m,)!),但：,13,！,是,6227020800,会超出,32,位机的字长,48,组合计算,另，,用,C(n,，,m),表示从,n,个元素中取出,m,个元素的不同组合数，也可使用递归的形式定义：,2.,C(n,，,m)=C(n-1,，,m)+C(n-1,，,m-1),49,求,n,个数中取,m,个数的所能产生组合形式的数量,根据组合的递归形式的数学定义：公式（,2,）可知，从从,n,个元素中取出,m,个元素的基本案例和递归案例分别为：,m=n,，,c=1,m=1,，,c=n,mn,，,c=C(n-1,，,m)+C(n-1,，,m-1),50,递归实现,组合数,51,迭代法,迭代是数值计算中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程,为实现这一过程所使用的方法统称为迭代法（,Iterative Method,）,52,一个简单的代数方程,三种迭代法,53,三种迭代方法的比较,54,测试的目的,迭代法是数值计算中求解非线性方程的基本思想方法，其构造方法可以有多种多样,关键,使迭代收敛且有较快收敛速度,取定某个初始值，分别计算（,3.3,）,（,3.5,）迭代结果，它们的收敛性如何？,对三个迭代法中的某个，取不同的初始值进行迭代，结果如何？,55,牛顿迭代法求方程解,请用牛顿迭代法（,3.6,式）求方程,在区间,-3,3,上误差不大于,10,-9,的根，分别取初值,X0=1.5,X0=0,X0=1,分别进行计算，比较它们的迭代次数,56,牛顿迭代法基本原理,设,令其解为,得：,这称为,f(x,)=0,的牛顿迭代格式，,给定初值,x0,迭代产生数列：,X0,，,X1,，,X2,Xk,57,牛顿迭代法的主要算法语句,迭代语句：,x1=x0-(x0*3-x0-1)/(3*x0*2-1),决策语句,abs(x1-x0)10*-9,58,牛顿迭代法流程,三个初值,得到同样的结果,但迭代次数,有差异,59,End-3,基本策略,算法设计过程中，发现问题、分析问题及解决问题的思路、步骤与其他学科中的方法是一致的，就是,寻找规律,计算机科学家在算法研究过程中总结了一些具有普遍意义的算法策略和一些可循的规律，能够帮助我们较快地找到算法,61,基本策略,贪心策略,分治策略,回溯策略,动态规划,将递归算法转成非递归实现,62,贪心策略,贪心算法,在对问题求解时，总是做出在当前看来是最好的选择，因此它仅仅是某种意义上的,局部最优解,但在相当广泛范围内，对许多问题它能产生整体最优解或者是整体最优解的近似解,“鼠目寸光”,是对贪心算法的最好描述,63,贪心算法的特点,以当前情况为基础根据某个偏好原则作最优选择，而不考虑各种可能的整体情况,省去了为寻找最优解要穷尽所有可能而必须耗费的大量时间,采用自顶向下,以迭代的方法做出相关的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,64,贪心算法的特点,通过每一步贪心选择,可得到问题的一个,局部,最优解,但由此得到的全局解却不一定都是是最优的,65,求解数字三角形,有任意一个数字三角形，只能自第一层,(,顶层,),向下行走,且只能走下接的相邻两个结点,如第三层的,1,只能走第四层的,3,或,1,问能否找到一条路径，使得路径上的权值之和最大？,66,贪心法求解的算法设计,使用,文件保存,三角形的层数和所有数据,描述一个,n,层的三角形，需要,(n*,（,n+1,）,)/2,个数据和一个描述层次的数据,;,使用二维数组,a,，保存数字三角形的所有数据,二维数组的大小为,N*N,，当然，其中有一半的元素为空值,0;,67,贪心法求解的算法设计,使用,line,，,colum,两个变量在二维数组中，作为数字定位的指针；,x,作为保存权值累计的变量；,line,的值同时用来控制路径行走的循环,68,流程图,69,分治策略,分治法（,Divide and Conquer,）,的基本思想是，将一个较大规模的问题,分解,为若干个较小规模的,子问题,，找出子问题的解，然后把各个子问题的,解合并,从而得到整个问题的解,分治法的分（,Divide,）是指将较大的问题划分为若干个较小的问题，然后用递归法求解子问题；,分治法的治（,Conquer,）是指从小问题的解来构建大问题的解,70,分治策略,分治法算法中至少包含有,两次递归过程,，只有一个递归过程的算法在严格意义上不能算作分治算法,71,求用分治法进行幂运算降序求解,在公钥加密的,RSA,算法中将高次幂运算转换为低次幂运算可以加快加密和解密的计算过程，从而提高了,RSA,算法的运算速度,算法一：采用递推循环的方式实现类似,a*b,的计算过程；,算法二：采用递归方式实现分治算法：,a*b=(a*a)*(b/2)b=,偶数,a*b=a*(a*(b-1)b=,奇数,72,分治法的计算效率,以求,5,20,为例，使用分治方法与不使用分治方法的递归算法比较，分治法可以节省近三分之二时间,73,分治方法乘幂运算,流程图,74,回溯策略,如果问题的规模（数量）是按指数速度增加的，那么这些算法的能力将受到一定的限制,在这种情况下，回溯法（,Backtracking,）也许是一个更好的选择,回溯法也叫穷尽搜索法（,Brute-Force Search,），其基本思想是尝试分步地去解决一个问题,75,现有,n,种物品，对,1=i=n,，已知第,i,种物品的重量为正整数,W,i,，价值为正整数,V,i,，背包能承受的最大载重量为正整数,W,现要求找出这,n,种物品的一个子集，使得子集中物品的总重量不超过,W,且总价值尽量大,0-1,背包问题的数学描述,76,设有物件,n,项，重量为,w(5,3,2),价值,v(9,7,8),，如果背包只能装,5,斤，求可以放背包的物品最大价值。,使用回溯算法，决策树的建树过程为：,深度有限，左侧优先,，左侧分支不取东西，,右侧取当前物件,0-1,背包问题求解,（,3,，,5,，,0,）,（,2,，,3,，,8,）,（,2,，,5,，,0,）,（,1,，,2,，,7,）,（,1,，,5,，,0,）,（,1,，,3,，,8,）,i,：红色，,表示物品的编号,aw,：绿色，当前可用空间,V,：蓝色，当前物品价值,（,1,，,0,，,15,）,（,-,，,3,，,8,）,（,-,，,5,，,0,）,（,-,，,0,，,9,）,（,-,，,2,，,7,）,（,-,，,-3,，,16,）,（,-,，,-2,，,17,）,77,k,元组的概念,元组,(,tuple,),是一种有穷序列，,k,个元素的序列称为,k,元组。,与集合不同,，集合不考虑元素的顺序，但元组中的元素有严格的顺序规定,在,0-1,背包问题中的决策树中的元素和重量为,w(5,3,2),价值,v(9,7,8),，皆为,三元组,k,元组的概念在下一章的,有限状态机,和,图灵机,中还会用到,78,0-1,背包回溯算法的,main,子图,建议测试案例从简单的方案开始,79,0-1,背包问题,-,回溯法求解流程图,80,0-1,背包回溯算法说明,Maxvalue,是一个递归实现的子程序，其中的主要传递参数如下：,w：,项目物体的重量数组,v：,项目物体的价值数组,length_of(w),：重量数组的长度，也是最后一个物件下标，遍历循环的开始点，直到第一个元素,max_weight：,背包的最大容量,：,最后的返回值，即背包中物体的价值,81,动态规划,计算,Fibonacci,数列的第,n,项：当项数大于,2,时，,F,（,n,）,=F,（,n-1,）,+F,（,n-2,）,如果计算,Fibonacci,数列第,n,项，这需要计算从第,3,项到第,n-1,项,随着,n,值的增大，递归解法的算法时间复杂性会按几何级数增长,这类问题的关键是,子问题,（,sub-problem,）有重叠，因而分治法并不适合于此类问题的求解,82,动态规划,基本思想是：如果一个较大问题可以被分解为若干个子问题，并且子问题有重叠，那么，可以将每个子问题的,解存放到一个表中,，然后通过,查表,来解决问题，减少不必要的重复计算,动态规划是,20,世纪,50,年代美国数学家,Richard Bellman,提出的,在这个术语中，,Programming,与编程没有关系，而是规划和设计的意思,83,动态规划,解,Fibonacci,数列第,n,项,84,算法说明,算法,递归子程序,中的三个传递参数的作用分别是：,a,：第,n,项的输入参数,b,：第,n,项的结果输出,c,：计算过程中的中间结果存留数组（也就是一个线形表）,在计算过程中，每次计算的结果都保存在,c,数组中，出现重叠子问题时，直接到,c,数组中调取结果,85,动态规划,的分析,要消除计算过程中的,重复性过程,，动态规划是比较好的选择,这也是计算机科学中，进行问题求解的重要途径之一,由于动态规划需要保存中间计算结果，势必占用较大的内存空间（这点贪心法就完全不同），但时间复杂性则会降低,这就是所谓“,空间换时间,“的策略,86,动态规划,的分析,动态规划与贪心法不同的地方，它是一种,最优化算法,当所有的解空间可以遍历的前提下，利用动态规划的思想保存所有可能的解,再通过比较就可以得到最优的解,实现原理非常简单，但,非常实用,，也是计算机科学中最常用的算法策略,请设计使用,动态规划,求解数字三角形,87,将递归算法转成非递归的实现,递归是计算机科学中非常重要的概念，其主要优点是递归的代码量比非递归的代码量少，算法可以设计的非常简洁,这是由于递归所使用的方式是函数调用,这在计算机算法实现中属于非常自然的栈结构,不,需要,记录位置信息，,不需要,添加控制语句,这些工作都由函数调用的特性自行解决,88,递归算法的弱点,递归算法的执行效率比一般非递归的执行效率要低,因为递归的实质既然是函数调用，而函数调用必然要进行,线程栈空间,的分配，记录每一次函数调用前的状态等工作，开销是比较大的,这个情况读者可以自行应用递归实现汉诺塔案例，输入,不同的,铁饼数，运行并观察,89,非递归算法,的特点,非递归算法则不需要进行这些工作,（,线程栈空间,的分配,等）,因为非递归使用额外的变量记录当前所处的位置信息，以及额外的控制语句,递归与非递归调用最主要区别就是在函数调用上,90,递归与非递归策略思想,因此对解决某些问题时，希望用,递归算法分析问题,，但用,非递归算法解决问题,这就需要把递归算法转换为非递归算法,91,递归算法转化为非递归算法,有如下三种基本方法,：,通过分析，跳过分解过程，直接用循环结构的算法实现求解过程。,自己用栈模拟系统的运行栈，通过分析只保存必须保存的信息，从而用非递归算法替代递归算法,利用栈保存参数，由于栈的后进先出特性吻合递归算法的执行过程，因而可以用非递归算法替代递归算法,92,使用非递归方法实现汉诺塔算法,93,算法说明,将三个柱子分别命名为,na1,，,na2,，,na3,，初始状态，所有的盘子都在,na1,上，三个柱子按逆时针方向排列成一个圆环,其中存在一个规律，当对于规模为,n,的汉诺塔问题时：,1,奇数编号盘子总是移动移动到它后的第,2,个柱子上；,2,偶数编号的盘子总是移动移动到它的后第,1,个柱子上,94,基本算法策略的讨论,最优化和非最优化,：,什么不去追求最优化的解？,因为,存在一个解空间的规模问题，如果在规定时间里，可以找到所有的解，那么选出其中的最优解；,但是，如果不可能（有许多,O(2,n,）,以上时间复杂度的问题,),，那么，只好退而求其次，用次优解来解决问题,而贪心策略就是求次优解的常用思,95,基本算法策略的讨论,时间换空间（或空间换时间）,大部分递归算法编写简单，但运行的时间会随着问题规模的增长而急剧增长,而分治方法，一般要花费较多的时间将问题划分成为较小规模，增加了程序的复杂性；递归程序的非传参实现，也是如此,但较为复杂的算法，却换来几何级数的运行时间节省,96,基本算法策略的讨论,回溯策略,所解的一些问题往往是不能用数学公式去直接求解的,它需要通过一个过程，此过程要经过若干个步骤才能完成，每一个步骤又分为若干种可能；,同时，为了完成任务，还必须遵守一些规则和约束,；,对于这样一类问题，一般采用搜索的方法来解决，回溯法就是搜索算法中的一种控制策略，它能够解决许多搜索中问题,97,基本算法策略的讨论,使用递归算法的思路分析问题，但用非递归算法解决问题。,使用递归的思路分析问题，可以得到简便、可行但运行效率低下的算法,通过非递归将该算法进行再实现，可以得到极高效率的优秀算法,98,小结与回顾,基本算法包含了穷举、分段函数、递推、递归、迭代、组合、模运算、数论问题等，这种问题分类和针对性方法的比对可以避免毫无方向的试错和摸索过程,而基本策略则是计算机科学中解决战略性问题的重要手段，本章专门选择了若干相对简单的案例来分别说明贪心、分治、回溯和动态规划的基本思想,而使用递归的方法分析问题，使用非递归的方法实现算法，具有更为深邃的战略意义,99,第,4,章 模型化,可视化计算,如何,实现数据类型抽象,无论是进行科学计算或数据处理、过程控制等，都是对数据进行加工处理的过程,必须研究数据的特性及数据间的相互关系及其对应的存储表示,利用这些特性和关系设计出结构好、效率高的程序或算法,如何进行数据抽象,?,数据结构,是数据存在的形式,它用来反映一个数据的内部构成，即一个数据由哪些成分的数据构成，以什么方式构成，呈现什么结构,数据（,Data,）,是信息的载体,能够被计算机识别、存储和加工处理,数据元素（,Data Element,）,数据基本单位,在计算机程序中作为一个整体考虑和处理,如何进行数据抽象,?,数据结构（,Data Structure,）,是指互相之间存在着一种或多种关系的数据元素的集合,四类基本,的数据,结构：,集合结构,线性结构,树型结构,图形结构,如何进行数据抽象,?,一个数据结构必须包含有数据元素的集合和数据关系的集合,这,两个,基本要素,数据结构包括数据的,逻辑结构,和数据的,物理结构,数据的逻辑结构,可以看作是从具体问题抽象出来的数学模型，它与数据的,存储无关,研究数据结构的,目的,是为了在计算机中实现对它的,操作,，为此还需要研究如何在计算机中表示一个数据结构,数据的物理结构,指,数据结构在计算机中的,表示方式,，,也,称存储结构,或映像,它所研究的是数据结构在计算机中的实现方法，包括数据结构中,元素,和,元素间关系,的表示,例如：,顺序存储,方法是把逻辑上相邻的元素存储在物理位置上相邻的存储单元中，,可以,借助于程序设计语言中的数组来实现,抽象数据类型,抽象数据类型,(Abstract Data Type,，,ADT),是指一个与某种类型的数据结构行为模式有关的数学模型以及定义在此模型上的一组运算,而所有的运算必需在该类型的数据结构的数学限制条件下才是有效的,抽象数据类型,举例,一个数据堆栈,（,Stack,）,，可以定义三种运算：,压栈,(push),：将一些数据插入该结构,；,弹出,(pop),：从结构中取出并清除数据（按照后入先出的顺序）；,检查（,peek,），检查结构顶端的数据而不做清除,抽象数据类型,的实现,一般抽象数据类型需要通过某个系统子,已有的数据类型,来间接定义与实现,对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即子图、子程序或函数名，并且规定这些运算的参数性质,抽象数据类型,的程序实现,在,RAPTOR,中实现所定义的抽象数据类型数据部分用一种已知的数据类型（如,一维、二维数组，字符串等,）来实现,抽象数据类型,操作部分,中的每个操作用,RAPTOR,子图或子程序来实现,这样能够同其他计算机程序语言实现算法具有一定的,可比性,线性表的基本概念,数据结构分线性结构和非线性结构,线性结构包括线性表、栈、队列、数组和字符串,线性结构,特点,：在数据元素的非空有限集中,存在,唯一,的一个被称作“,第一个,”的数据元素,存在,唯一,的一个被称作“,最后一个,”的数据元素,除第一个外，集合中的每个数据元素均,只有一个前趋,除最后一个外，集合中的每个数据元素均,只有一个后继,线性表的逻辑结构,一个线性表是,n,个数据元素的有限序列,特征：,元素个数,n,表长度，,n=0,：,空表,1,ian/2,，则需要在数组,a,的右半部继续搜索,直至找到,x,为止或得出关键字不存在的结论,算法实现的前提,1.,必须采用顺序存储结构,2.,必须按关键字大小有序排列,177,178,二分查找,的算法说明,子程序先将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；,否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表,否则将继续查找后一子表,重复以上过程，直至找到满足条件的记录，或者根本查不到子表，此时查找失败,179,二分查找,的算法分析,+,折半查找法每执行一次，都可以将查找空间减少一半，是计算机科学中分治思想的完美体现,-,其缺点是要求待查表为有序表，而有序表的特点则是插入删除困难,因此，折半查找方法适用于不经常变动而查找频繁的,有序列表,180,分块查找,使用扑克牌计算,24,点,该算法是从数字为,110,的扑克牌中任意抽出四张，运用加、减、乘、除，在运算中可以引入括号，每张牌只能用一次，使其计算结果为,24,在广泛的社会实践的基础上可以分析和认识到：,在一副牌（只保留数字点数的,40,张）中任意抽取,4,张，总共有,715,种不同组合形式，其中有,149,种组合的运算结果不可能为,24,181,不可计算,24,的牌组,(149,个,),182,不可计算的牌组如何确定？,计算搜索开始前，先检查某个特定牌组的计算可能性呢？,如果肯定得不到,24,的计算结果（例如，,1,，,1,，,1,，,1,和,10,，,10,，,10,，,10,），那么就可以马上重新发牌，开始新一轮计算,可以使用查表的方式来解决！,183,问题,每次查阅这张表也不是一个简单的过程，因为该表列出的关键字是使用字符串实现的，尽管字符串也可以转换成数字进行排序，但显然会增加查找过程的计算工作量,能否设计一个算法，不用转换关键值，又可以减少顺序查找的扫描工作量？,可以考虑采用,分块查找算法,，该算法又称,索引顺序查找,，它是顺序查找的一种改进方法,184,分块查询的基本思想,将,n,个数据元素,按块有序,划分为,m,块,（,m n,）,每一块中的节点不必有序，但块与块之间必须,按块有序,；,即第,1,块中任一元素的关键字都必须小于第,2,块中任一元素的关键字；,而第,2,块中任一元素又都必须小于第,3,块中的任一元素，,185,分块查找的实现,不可计算牌组保存在（以文本格式）文件中,从文件读入后，产生一个索引数组,保存各块的起始元素下标,186,分块算法设计的说明,主要子图,Main,：主流程控制；输入,/,输出,Input_list_stringc,：从文件读入,149,个牌组,Indexing,：建立分块索引表,Random_number,：产生测试牌组,a,Sort,：将测试牌组,a,排序,Setsample,:,将测试牌组,a,转成测试字符串,Block_search_test,:,进行分块查找,187,分块查询,Main,子图,188,分块查询,主要数据结构,:,Str_list,:,保存文件读入的,149,个牌组，字符串,A,：保存随机产生的,4,张牌（,110,），数值,In_key,:,保存排序完成的牌组样本，字符串,Index,，,：保存分块索引表，,189,分块查询,Set_sample,子图,190,分块查询,Indexing,子图,191,分块算法设计的分析,分块查找的第一部分是进行索引表的查询,一般来说，索引表长度在,10,以内，就可以使用顺序查找，否则使用二分查找,为了简化算法，本例将,149,组,数据只划分了,9,个块，以,10,开始的牌组只有一个，这里将其与,9,开始的牌组合并了,24,点牌组的不可计算,比,为,149/715,，将查询初值,ok,赋值为,true,，可以减少赋值运算的次数,192,分块算法的运行说明,由于采用随机数产生测试牌组，所以测试无需输入样本，只要回答，,y/n,即可,需要自行输入样本，可以自行修改样例算法，再进行测试,193,分块查找的时间复杂度,分块查找的时间复杂度：,O,（索引表查找,+,块内查找）,O,（索引表二分查找,+,块内顺序查找）,O(log,2,B),+,(M+1,）,/2,O,（索引表顺序查找,+,块内顺序查找）,O,（,(B+1,）,/2,+,(M+1,）,/2,）,一般描述：,O,（）,分析：,实际应用中不一定分成大小相等的块，可按表的特征分块（如本例所设计）,提高了顺序查找的效率，但付出了空间的代价（索引表）,194,哈希查找,哈希是,hash,的音译，意为“杂凑”，也称散列,哈希表是一种重要的存储方式，哈希查找技术是一种按照关键字编址的检索方法,哈希查找不同于前面的几种查找方法，它是通过对记录的关键字值进行某种运算，直接求出记录文件的地址,是,关键字到地址,的直接转换方法，而不需要反复比较,，所以计算复杂性为常数阶：,O,（,1,）,195,哈希查找的实现过程,仍以,24,点不可计算作为基本查找的数据集,由于哈希查找需要对牌组内的牌面进行计算,注意这一点与分块查找不同,每个牌组内的每张牌面，都,必须转变成可以计算的数字,需要设计哈希函数并构建哈希表,196,哈希表查找方法的基本思想,如果在记录的存储位置与它的关键字之间建立一个确定的关系,H,（）,使每个关键字和一个唯一的存储位置相对应,在查找时，只需要根据对应关系计算出给定的关键字值,k,对应的值,H(k,),，就可以得到记录的存储位置,在使用,哈希方法解决,24,点不可计算牌组,时，就是将牌面数字计算后查表，可以查到为不可计算；不可查到就是可以计算,197,哈希表的构建,哈希函数（,hash function,），,记录的关键字值与记录的存储位置的对应关系,H,称为哈希函数，,H(k,),的结果被称为,哈希地址,哈希表（,hash table,）,，是根据哈希函数建立的表，以记录的关键字值为自变量，根据哈希函数，计算出对应的哈希地址，并在此,存储该记录的内容,198,哈希冲突与解决,冲突（,collision,）,，不同的关键字值其哈希函数计算的哈希地址相同，具有相同函数值的关键字值称为,同义词（,synonym,）,本例中处理,同义词,冲突的方法是,拉链法,，当发生冲突时，在冲突位置的二维数组行上寻找存放记录的空闲单元,199,24,点算法的不可计算案例哈希,设定哈希表的长度为,149,，,H,关系为：,H(key,)=key mod 149+1,Key,的获取原则为：,所有,10,牌面模除,7,余,3,，再参与其他牌面的计算，例如，,10,10,10,10,等同,3 3 3 3,去掉,10,以后的所有牌面数：,key,=d1*1000+d2*100+d3*10+d4,H(Key,)=,3333 mod 149+1=56,200,计算所得的哈希表（局部）,不可计算牌组直接转换成为字符串；,按哈希规则寻址保存在文件记录中,201,构建哈希表的一些要点,可以采用,149,行，,N,列的二数组保存哈希表（也就是将同义词的牌组，按计算顺序在一行中排放）,在运行后，发现最大的冲突数为,3,，因此该算法的实际哈希表为,149*3=447,个数据单元,在本例构建的哈希表（,hash_1,）的初始化过程中，所有数组元素皆为数值,0,，在保存牌组时，首先要,检测当前数组元素的数据类型,如果不是数值类型，则说明已经填入了数据，需要寻找,邻接的,属于数值类型的元素再写入,202,哈希表的应用,在应用时，先载入已准备的哈希表,随机生成,24,点牌组，应用哈希规则得到哈希表的地址,进行查表操作，可以查到，则为不可计算牌组；不可查到，则为可计算牌组,查找的效率在,1,到,3,次之间，时间复杂度为：,O,（,1,）,203,小结与回顾,查找策略则与数据的排序与否，数据自身的属性有重大关系。,顺序查找针对未排序数据，,二分查找针对已排序数据，,分块查找针对按块有序、块内无序的数据,而最能体现计算机科学精髓的查找方法则是哈希查找，哈希查找是通过计算数据元素的存储地址进行查找的算法,204,