37986-00钟晴江-大学计算机大学计算机4 1-4 2

1、第4章 数据的处理算法,目录,4.1 引子：渡河游戏 4.2 算法 4.2.1 算法的控制结构 4.2.2 算法的表示 4.2.3 排序算法 4.2.4 查找算法 4.3 算法策略 4.3.1 枚举算法：百钱买百鸡 4.3.2 递归算法：汉诺塔问题 4.3.3 回溯算法：八皇后问题 4.3.4 分治算法：找出伪币 4.3.5 并行算法：国王的婚姻 4.4 可计算性与计算的复杂性 4.4.1 计算机处理的局限性 4.4.2 计算复杂性与可计算性,重点和难点,重点： 什么是算法？算法的控制结构。 几个常用排序算法的理解。 顺序和二分查找算法的理解。 典型算法策略的理解。 难点： 算法的描述。 不同

2、算法的优劣比较。 计算复杂性和可计算性。,4.1 引子：渡河游戏,两个大人和两个小孩一起渡河，渡口只有一条小船，每次只能渡1 个大人或两个小孩，他们四人都会划船，但都不会游泳，试问他们怎样渡过河去？请写出一个渡河方案。,根据条件，我们考虑如下方案： S1：两个小孩同船过河去 S2：一个小孩划船回来； S3：一个大人划船过河去 S4：对岸的小孩划船回来； S5：两个小孩同船渡过河去； S6：一个小孩划船回来； S7：余下的一个大人独自划船渡过河去； S8：对岸的小孩划船回来； S9：两个小孩再同时划船渡过河去。,按照上述渡船的步骤一定可以把两个大人和两个小孩渡到河对岸去。 因此，在解决问题时，按

3、预先设计好的一系列可操作或可计算的步骤完成任务，这些解决问题的方法和步骤就是算法。 本章我们就来学习算法，算法是程序的灵魂，也是计算机的灵魂，计算机中所有执行的程序都有算法，算法有好坏之分，有些问题到目前为止还没有找到好的算法。,4.2 算法,其实，日常生活中处处都有“算法”，如烧一壶水的算法如下： （1）往壶内注水； （2）点火加热； （3）观察：如果水开，则停止烧火，否则继续烧火并重复第3步； 再比如菜谱中描述的“西红柿炒鸡蛋”的制作过程就是一个算法，一首贝多芬“命运”的钢琴曲谱就是一个算法。 事实上，我们完成任何事，都要有一个明确的步骤，合理安排步骤，就会达到事半功倍的效果。,算法的基本

4、思想就是我们分析问题时的想法，由于想法不同、思考问题的角度不同、着眼点不一样，对同一个问题，可以有不同的解题方法和步骤。 方法有优劣之分，有的方法只需进行很少的步骤，而有些方法则需要较多的步骤。因此，为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。 进一步说，既然算法是解决给定问题的方法，算法的处理对象就必然是该问题所涉及的相关数据，程序的目的是加工数据，而如何加工数据是算法的问题。程序就是数据结构与算法的统一，因此有如下著名公式： 程序=算法+数据结构,上述公式意思就是程序是由一种解决问题的方法加上和解决方法有关的数据组成的。比如：你要做一道菜“香菇炒青菜”这就

5、是一个程序。而你的算法就是,你的数据就是。由这些数据加上算法（你做菜时采用的策略）就是程序。 这个公式揭示了：不能离开数据结构去抽象地分析程序的算法，也不能脱离算法去孤立地研究程序的数据结构，而只能从算法与数据结构统一上去认识程序。,4.2.1算法的控制结构,在计算机程序解决问题的过程中，一个算法的功能不仅取决于所选用的操作，而且还决定于各操作之间的执行顺序，即控制结构。 算法的控制结构给出了算法的框架，决定了各操作的执行次序。 用流程图可以形象地表示出算法的控制结构。,1顺序结构 程序执行时按部就班，从上到下依次执行。 2选择结构 根据条件进行判断，再决定具体的执行步骤。 3循环结构 根据条

6、件判断，反复做某一部分操作。,任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成，称之为算法的三种基本控制结构。 如果把每种基本控制结构看成是一个积木，则整个算法便是由这三种积木搭建而成的，这样的算法结构清晰，容易阅读也容易理解，我们称之为结构化的算法。,4.2.2算法的表示,有了求解问题的方法、思路后，就必须用一种规范的，可读性强的，容易转换成程序的形式描述出来。 程序是计算机语言描述的算法，流程图是图形化了的算法。除此之外，算法的描述方法还有自然语言、伪代码等。,分析：求最大数常用的方法就是“打擂台”。一圈“擂台”打下来，最终站在“擂台”上的就是最大值。 算法描述如下： 步骤1：假

7、设v(1)为最大数，令max为v(1) 步骤2：max与后面的所有数v(i)（i=210）逐个比较： 若max小于v(i) 则令max=v(i) 步骤3：打印输出max的值，即为数组v的最大值,1算法的自然语言描述,【例41】数组v有10个元素，即v(1), v(2)v(10)，求其中的最大数。,上述用自然语言描述的算法，其优点是语言熟悉，易懂，缺点是繁琐冗长，易产生歧义。,2算法的流程图描述,【例42】求1+2+3+100的和。用流程图描述算法。,用图形化方法描述算法形象直观，但它最大的不足是画画“麻烦”。,分析：设1100的累加和放在变量s中，这个问题的本质就是重复做累加的动作：s=s+i

8、，让加数项i从1变化到100。流程图如下：,鉴于自然语言语义有歧义，而流程图又太麻烦，人们往往采用意义精确、唯一且已形式化的类计算机语言伪代码来描述。 伪代码兼有自然语言和计算机语言的特点，它结构性较强，自由、灵活、容易书写和理解，特别是它不拘泥于特定语言的语法结构，是一种准计算机语言。而根据伪代码写程序又比较方便，因此用伪代码描述算法目前最为流行。,3算法的伪代码描述,【例43】求三角形面积 设三角形三边长分别为a、b、c，借助海伦公式s= p pa pb pc 计算三角形面积S，其中p为半周长。请用伪代码描述。,分析：用海伦公式求三角形面积，需要知道三边长，如果这三边长能构成三角形，则可以

9、先计算半周长P，再计算面积S。,算法描述如下： 输入a,b,c 若（a+bc 且b+ca 且a+cb ) 则 p=(a+b+c)/2 s= p pa pb pc 输出s 否则： 输出 ”三角形边长不正确！”,最后，算法若用计算机语言来描述即成为程序，程序是算法在计算机上的特定实现。 算法侧重于问题的解决方法和步骤，程序侧重于机器上的实现，一个有效的程序首先要有一个有效的算法。因此算法设计是程序设计的核心。 反过来，针对同一问题，不同的算法所用的时间、空间开销不同，一个算法的优劣一般用空间复杂度与时间复杂度来衡量。 例如同样是排序的问题，不同的排序算法各有特点，算法质量不相同，应用场合也各不相同

10、。,4.2.3排序算法,排序的例子在日常生活中比比皆是，老师喜欢从高分到低分公布成绩，在上网购书时也发现了排序畅销图书榜，按图书销售量排序！ 当数据不多时，排序比较简单，有时手工都能做。但若排序对象是每年几百万高考考生，图书馆几百万册图书，购书网站上百万个数据，排序就成了一件非常重要且费时的事情。 近几十年来，人们设计了非常多的排序方法，它们各有特点，而选择一个合适的方法会大大提高排序效率。 目前常用的排序算法有：选择排序、插入排序、交换排序、归并排序等。让我们先从简单的入手吧！,【思考】,有7个形状大小一样但重量不同的砝码，请按重量从小到大排序。 由于砝码的形状大小一样，所以没有办法通过目测

11、来区分哪个重哪个轻，只有一个办法，就是用天平秤。天平秤的时候只能两两比较，假如从7个砝码中找出最轻的那个，要称6次才能辨别出来。 这里之所以用“形状大小一样但重量不同的砝码”来排序，主要是要大家注意计算机只能两两比较大小，不能象人那样一“看”就能在多个数中找出最小数。这是计算机排序的基本前提。,要把这7个砝码按重量从小到大排序，我们想出的最简单的方法就是先找到最轻的那个，放在第1个位置；在留下的6个砝码再找最轻的，放在第2个位置上； 每次在余下的砝码中找最轻的那个放在已排序的砝码的后面，这就是选择排序算法的基本思想。,1选择排序,【例44】对数据元素序列v(6)=8，3，5，2，4，1，用选择

12、法排序。,【解】算法思想：,总结： n个元素需要“查找-交换”n-1次。,选择排序的基本思想：每一趟从待排序的元素中选出最小的数，放在已排好序的序列的最后面，直到全部记录排序完毕。,选择排序算法描述如下： 循环（i 从1到n-1） ki 循环（j 从i+1 到n） /找最小值 若(v(j)v(j+1)）则 交换 v(j) 和v(j+1),【分析】,冒泡排序算法中，若有6个待排序数，则第一轮冒泡相邻元素比较5次，第二轮冒泡比较4次，依此类推，最终需要比较：5+4+3+2+1=15次，这和选择排序算法的效率一样。 但冒泡排序法数据交换的次数比选择排序要多许多。事实上，冒泡排序是所有排序算法中效率最

13、低的一个。,3直接插入排序,大家都打过扑克牌，通常一边添牌一边排序。 左侧带下划线的就是有序队列，这个思想就是直接插入排序。,这种排序法和选择排序法的不同之处在于，该算法的重点是如何将数值放入左侧已排序好的序列中，而不是去考虑该在右侧序列中挑出哪一个数值。,【例46】对数据元素序列v(6)=5，2，4，10，7，3，用直接插入法排序。,【解】算法思想如下： 第1轮：首先设该序列中已存在一个有序的子序列（5）。 （5），2，4，10，7，3 接下来要将第2个元素2插入到这个子序列中。方法是，从元素5开始向左找。因为2小于5，因此将2插入到5之前。这样在原序列中得到一个新的按值有序的子序列（2，5

14、）。 （2，5），4，10，7，3,（2，4，5），10，7，3 第二轮插入4后的结果 （2，3，4，5，7，10） 第五轮插入3后的结果,由此可见，在进行第1轮插入排序时，可将第1个元素看成长度为1，按值有序的子序列，然后将第2个元素插入到这个子序列之中。 依次类推，第i轮排序时将序列中的第i+1个元素v(i+1)插入到一个已经按值有序的子序列v(1), v(2), v(i)中，使得插入后的序列仍然保持按值有序。 因此，n个元素的序列，需要n-1轮的直接插入排序。,直接插入排序算法描述如下： 循环（i 从2到n） 将v(i)临时存放在temp中 ji-1 当（j1且 temp0 时） 划分子

15、序列并对每一子序列排序 gapgap/2,【分析】,希尔排序法效率比较高，原因在于排序的初期阶段，由于gap值较大，每个子序列需要操作的元素个数很少，因此直接插入法效率很高。 后来当gap值减小时，虽然每一轮需要操作的数据增多，但此时已经接近于它们排序后的最终位置，从而直接插入法效率也较高。 正是这两种情况的结合才使希尔排序效率比直接插入排序高很多，它的时间复杂度是O(n 1.5)，希尔排序算法是突破“n2”排序法的第一批算法之一。,5快速排序,快速排序是一种划分交换排序。它采用一种分治的策略，通常称其为分治法。,该算法的基本思想是： （1）先从数列中取出一个数作为基准。 （2）分区：将比这个

16、数大的数全移到它的右边，小于或等于它的数全移到它的左边。 （3）再对左右区间重复第二步，直到各区间只有一个数为止。,例如：有8个形状大小一样但重量不同的砝码，用快速排序法对他们排序。,快速排序法中最妙的一步在于，我们对基准两侧的对象排序时，采用的仍是之前的方式选择其中的一组，然后重复上述“分裂”过程，直到每组中只有一个对象为止。,【例48】对数据元素序列v(8)=6，4，12，11，3，15，7，9，用快速排序算法排序。,【解】算法思想：,快速排序中我们用到了递归原理，即不断用相同的原则将序列划分成越来越小的部分，并采用相同的步骤对各部分排序，序列被重复地分割直至它足够小到直接导出结果。 实际

17、上，这种特殊的递归法被称为分治（分而治之）法。对于快速排序来说，序列将被分割到每组只剩下一个对象，而对一个对象排序是不言而喻的事情。 这里提到的递归和分治在后面将会详细展开，大家有一个初步的印象就可以了。,快速排序算法描述： QuickSort(SeqList R，int low，int high) /对R(low.high)快速排序 设变量pivotpos为基准记录的位置； 若(lowK，则由表的有序性可知v(midhigh)均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表v(1mid-1)中，故新的查找区间是左子表v(1.mid-1)。 类似地，若v(mid

18、)K，则要查找的K必定是在位置mid右边的子表v(mid+1high)中，即新的查找区间是右子表v(mid+1high)。 针对新的查找区间进行下一轮查找。,因此，从初始的查找区间v(lowhigh)开始，每经过一次与当前查找区间的中间结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间缩小一半。 重复这一过程直至找到关键字为K的结点，或者直至当前的查找区间为空（即查找失败）为止。,算法步骤描述如下： step1：确定查找区间的中间位置：mid = （low+high）/ 2 step2：用待查关键字值与中间位置的关键字值进行比较； 若相等，则查找成功 若大于，则在后（右）半个区域继

19、续进行折半查找 若小于，则在前（左）半个区域继续进行折半查找 Step3：对确定的缩小区域再按折半查找方式，重复上述步骤。,最后得到结果：要么查找成功，要么查找失败。,折半查找的存储结构采用一维数组存放。,【思考】,对给定的有序数列 3，5，11，17，21，23，28，30，32，50，按折半查找算法，查找关键字值为30的数据元素。需查找几次才能找到？如果有100个数，需要查找几次才能找到？,可见，二分查找的优点是比较次数少，查找速度快只要检查队列的中间项就可锁定搜索关键字位于哪一半队列，这样一来，每猜一次相当于将待查找的目标数量减少一半。 再回头看超市的例子，如果采用二分搜索方式在10 000件货品中查找，现在仅需要14次搜索，也许就是两百分之一秒的事快到让人无法察觉。 当然二分查找也有缺点，那就是要求待查表为有序表，且插入删除元素较困难。 因此，折半查找方法适用于不经常变动而查找频繁的有序列表。,3.二叉排序树查找,（1）二叉排序树的定义 二叉排序树又称二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树： 若左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若右子树不空，则右子树上所有结点的值均大于它的根结点的值； 左、右子树也分别为二叉排序树；,若查找树为空，查找失败。 查找树非空，将给定值k与查找树的根结点关键字