黄淮学院《计算机基础》课件-第9章算法

黄淮学院《计算机基础》第9章算法E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B410目录经典算法设计3.算法的描述2.算法的概念1.E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4101.算法的概念算法概述没有算法，就没有计算机程序算法(algorithm)是一组解决问题的有穷规则的集合欧几里得算法

算法9.1：(1)输入任意两个整数m和n，使得m>n；(2)计算：m除以n得余数r；(3)若r=0，则n为求得的最大公约数，算法结束；否则执行(4)；(4)将m的值修改为n，将n的值修改为r，再重复执行(2)。E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4101.算法的概念算法的特征有限性：算法在执行有限步以后必须终止确定性：算法的每一个步骤都有精确的定义可行性：算法中有待实现的运算都是可以实现的输入：一个算法可以有0个或多个输入数据，作为算法开始执行的初始值输出：一个算法必须有一个或者多个输出数据，这些输出的结果与输入的数据有特定的关系E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4102.算法的描述自然语言这种方法是用人们日常使用的语言来描述算法。它无需专门训练就可以描述出通俗易懂的算法。例如第一节的算法9.1，就是用自然语言描述的。但是，自然语言固有的不严密性使得我们很难做到简单清晰的描述算法，并且自然语言不便于翻译成计算机设计语言，所以伪代码应运而生E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4102.算法的描述伪代码伪代码是自然语言和类编程语言组成的混合结构，它比自然语言更精确，更简洁，如果熟悉一门现代编程语言就更容易理解了。

欧几里得算法的伪代码：1.r=m%n//%是求余数运算符2.whiler<>=0//<>代表不等于//这条语句的功能是当r不等于0的前提下循环下面三行代码m=nn=rr=m%n3.输出nE6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4102.算法的描述流程图用一组标准图形符号来描述算法。

欧几里得算法的流程图：

它的主要优点是画法简单、结构清晰、逻辑性强、容易理解，便于初学者掌握。但是流程图本质上不是逐步求精的好工具，复杂的算法用流程图描述时会占用很大篇幅。实践证明，除了一些非常简单的算法以外，这种表示方法使用起来非常不便。所以，已经有越来越多的人不再使用流程图了E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计穷举法穷举法，也被称为枚举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的，能使命题成立者即为问题的解。1）百元百鸡：

公元5世纪末，我国古代数学家张丘建在他编写的《算经》中提出这样一个问题：“鸡翁一值钱五；鸡母一值钱三；鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”意思是说，公鸡每只5元，母鸡每只3元，3只小鸡1元，用100元钱买100只鸡，求公鸡、母鸡和小鸡各多少只。这里设每种鸡至少一只。E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计1）百元百鸡：【算法分析】

我们假设公鸡、母鸡、小鸡的只数分别为x、y、z。我们以三种鸡总数（x+y+z）和买鸡的总钱数（5*x+3*y+z/3）都等于100为判定条件，穷举出各种鸡的只数。

算法9.2：forx=1to100//公鸡数从1枚举到100fory=1to100//母鸡数从1枚举到100forz=1to100//小鸡数从1枚举到100if(x+y+z)=100and(5*x+3*y+z/3)=100则

输出x、y、z的值这个算法对x、y、z都从1开始枚举到100，计算机需要做100*100*100次比较操作，虽然这点“规模”对计算机来说不算什么，可以很快完成计算，但是，这个算法仍然后很大的改进空间。E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计1）百元百鸡：

因为公鸡5元钱一只，所以100元最多买20只公鸡。同理，100元最多买33只母鸡，而小鸡的数目是100-x-y，因此没必要枚举。改进后的算法如下：

算法9.3：forx=1to20//公鸡数从1枚举到100fory=1to33//母鸡数从1枚举到100z=100-x-yif(5*x+3*y+z/3)=100则

输出x、y、z的值

改进后的算法让计算机执行操作的次数减少到大约660次。这个程度的优化在实际运行中是感觉不到的。但是算法优化的思想还请读者记在心里E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计2）旅行商问题：

我们以图9.2所示的5个城市为例来讲解这个算法，并要求商人从A城市出发，来求得最短路径。这时只需考虑用A开头的排列即可，也就是有4!种可能的排列解算法9.4：1）城市数目为5，从A城市出发，列出所有可能的路线和距离2）路线距离路线距离ABCDE38ADBCE49ABCED40ADBEC45ABDCE44ADCBE45ABDEC38ADCEB41ABECD41ADECB39ABEDC34ADEBC39ACBDE42AEBCD45ACBED39AEBDC44ACDEB34AECBD49ACDBE44AECDB44ACEBD45AEDBC42ACEDB38AEDCB383）在上述路线中找出最小值34，距离为34的路线有两条：ABEDCA和ACDEBA

E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计3）冒泡法排序：

冒泡排序法的思想比较简单，对于n个元素，从第一个开始依次比较相邻的两个，如果是逆序就交换它们的位置。重复多次以后，最大（或最小）的元素就“沉到”列表的最后一个位置。第二遍操作将第二大（或小）的元素沉下去，这样一直操作，直到n-1遍后，列表就排好序了。我们以10个数字的升序排列为例讲解这个算法。

E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计3）冒泡法排序：【算法分析】

首先将第1个数字和第2个数字进行比较，若为逆序（即第1个数字大于第2个数字），则交换两个变量的值。然后比较第2个数字和第3个数字的值，若为逆序则交换之。依次类推，直到第9个和第10个数字比较完为止。这个过程称为第一趟冒泡排序，其结果是将最大的数字转移到最后一个位置上。然后进行第二趟冒泡排序，对前9个数字进行同样操作，将第二大的数字转移到第九个数字的位置。这样的冒泡排序一共需要进行9趟。由此得到算法9.5。图9.3展示了冒泡排序的一个实例，从图中可以看出，在冒泡排序的过程中，小的数字好比水中的气泡逐渐向上漂浮，大的数字就像石块一样逐渐下沉，每一趟都会有一个“最大”的石块沉到水底E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B410冒泡法排序E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B410冒泡法排序算法9.5：1.10个数字存在数组a[i]中，i从1到102.fori=1to9//i代表第几趟冒泡排序forj=1to10-i//每次参加比较的列表元素ifa[j]>a[j+1]then//如果是逆序a[j]<-->a[j+1]//交换两个变量的值3.输出排序后的结果E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B410穷举法

穷举法也被称为蛮力法，它可能是唯一一种几乎什么问题都能解决的一般性方法。它的优点是思路简单，程序编写和调试方便。但是它最大缺点是运算量比较大，解题效率不高。在旅行商问题中，城市的数量越多，计算的时间成本越大。假如城市数n=20，则有19!条路线，约等于1.2*1017，如果每秒钟列出1亿条路线，还需要超过114年才能全部列出。E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计分治法分治法可以算得上是最著名的通用算法设计技术了。它的主要设计思想是将一个问题划分为同一类型的若干子问题，对这些子问题求解，子问题较原问题无疑是要容易些，有必要的话，合并这些子问题的解，由此得到原问题的解。这就是“分而治之”的意思1）二分查找：

二分法查找就是分治法的典型例题，它适用于在一组有序的数据中查找某个关键字的情形。二分查找又被称为折半查找，下面通过一个实例来了解这种查找方法。E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B410二分查找假定有一组数据：-19627323446708192

这组数据已按从小到大的顺序排列好，我们要查找81这个数字，如果存在，给出它的位置，如果不存在，给出相应的提示信息。【算法分析】

第1次比较的数字范围是整个数字序列，如图9.4中第一行数字下的框线所示。首先找到全部数字的中间位置，也就是34，它将数字序列一分为二。要找的数字81>34，因此，继续在后半部分查找。此时要查找的数字范围是从34后面一个数字开始的，如图9.4中第二行数字下的框线所示，问题规模减小了一半。第2次比较的中间位置是数字70，要找的数字81>70，则在后半部分继续查找。第3次比较的中间位置是数字81，至此查找成功。E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B410二分查找算法9.6：1)将n个有序数字保存在变量a(i)中，i=1…n

要查找的关键字保存在变量key中2)使用两个变量low和high分别代表要查找范围的下限和上限。显然它们的初值分别是：low=1，high=n（n为全部数字的个数）3)如果low<high，计算中间位置用变量mid保存：mid=(low+high)/2（如果无法整除，则取小于它的最大整数）。然后给变量y赋值：y=a(mid)，转向(4)。如果low≥high，转向(7)。4)如果y=key，则转向(6)。否则，转向(5)。5)如果y<key，则修改low的值：low=mid+1，转向(3)。如果y>key，则修改high的值：high=mid-1，转向(3)。6)输出k。7)输出提示信息：没有要查找的数字。E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计分治法2）快速排序：

快速排序是冒泡排序的一种改进算法，也是基于分治技术的一种重要排序算法。它的基本思想是：通过一趟排序将待排数据分割成独立的两部分，其中一部分数字均比另一部分的数字小，这时再分别对这两部分继续进行排序，以达到整个列表有序。【算法分析】

首先任意选取一个数字作为枢轴，这个数字通常选择第一个数字，也就是i位置处的数字。然后将所有比它小的数字都安置在它的位置之前，所有比它大的数字都安置在它的位置之后。由此，以这个数字为分界线，整个数字序列被分为了两部分，这个过程叫一趟快速排序。图9.5展示了一趟快速排序的实例。E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B410快速排序E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B410快速排序算法9.7：1)定义partition函数，实现将数字序列分成两个部分的功能。Partition(数列L，下标i，上标j)

这个函数有三个参数，分别是待排序的数列L，最低位置i和最高位置j，实现的功能是将数列L的i位置和j位置之间的数字以i位置的数字pointkey为枢轴分成两部分，前面的部分都小于pointkey，后面的部分都大于pointkey。2)定义quicksort函数，递归实现快速排序。Quicksort(数列L，下标i，上标j)

这个函数有三个参数，分别是待排序的数列L，最低位置i和最高位置j，实现的功能是将数列L在i位置和j位置之间的数字按从小到大的顺序排列。Quicksort(L，i，j){if(i<j){pointloc=partition(L，i，j);Quicksort(L，i，pointloc-1);Quicksort(L，pointloc+1，j);}}E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计贪婪法所谓贪婪算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪婪算法的基本思路是首先建立数学模型来描述问题，把求解的问题分成若干个子问题，然后对每一子问题求解，得到子问题的局部最优解。最后，把子问题的局部最优解合成原问题的一个解E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计贪婪法1）旅行商问题E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B410贪婪法解决旅行商问题算法9.8：1)从A出发，所有与A相连的路线中，找到距离最短的、值为6的路线。如图9.7中的(a)图所示。2)在与C相连的路线中，找到距离最短的、值为5的路线。如图9.7中的(b)图所示。3)按照相同的思路，继续向下查找，如图9.7中的(c)和(d)所示。4)得到最短路线ACDEBA。

与穷举法相比，贪婪法求解旅行商问题可以在很短的时间里完成，即便有20个城市也不会明显增加算法的计算成本，效率大大提高。读者需要注意的一点是，由于贪婪算法每次都是在城市的局部考虑距离值最小，当走完所有城市后，所得到的距离不一定是最小的，所以此算法得不到精确解.E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计贪婪法2）背包问题

背包问题是这样描述的：一个背包，最多可以放入重量为M的物品。现在有n个物体，每个物体重量分别是w1,w2,…,wn,每个物品的价值分别是p1,p2,…,pn。要求用这些物体把背包装满，且使背包内的物体价值最大。

有两类背包问题：物体可以分割的背包问题和物体不可分割的背包问题，后者通常被称为0/1背包问题。在这里主要讨论0/1背包问题，即物体或者全部放入背包，或者全部不放入背包。E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B410背包问题假设有5件物品，背包总容量是100，每件物品的价值和重量如表9-1所示。【算法分析】

贪婪算法求解0/1背包问题，是考虑物品的单位重量价值最大优先放入背包的策略。

表9-1的物体中，编号1~5的物品的单位重量价值分别是10、8、6、5、4。所以先放入背包的是物品1，然后是物品2，最后是物品3。放入3件物品后，背包重量为60，考虑到背包总容量是100，并且物品不可分割，所以剩余的物品4和物品5都无法放入背包。物品编号价值重量1505220025318030422545520050E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B410背包问题算法9.9：1)各物品重量分别存入变量w1~w5中，各物品价值分别存入变量p1~p5中。背包总重量为100。2)计算各物品单位重量价值，分别存入变量d1~d5中。3)从d1~d5中选择最大值所对应的物品装入背包，背包总重量减去该物品重量，在本例中选择物品1，背包剩余容量95。4)从d2~d5中选择最大值所对应的物品装入背包，本例中选择物品2，背包剩余容量为70。5)同样的思路，选择物品3装入背包，背包剩余容量为40。6)物品4和物品5无法装入背包，本题得解。即背包中装入物品1,、物品2和物品3，总价值为430。。E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计动态规划与贪婪算法的局部最优解策略不同，动态规划方法对问题进行全面的规划处理，从而弥补了贪婪法的不足。动态规划的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计动态规划

与贪婪算法的局部最优解策略不同，动态规划方法对问题进行全面的规划处理，从而弥补了贪婪法的不足。

动态规划的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

动态规划与分治法最大的差别是：适合用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的，即下一个子阶段的求解是建立在上一个子阶段的解的基础上，来进一步求解。E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计动态规划1）旅行商问题E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计回溯法回溯法实际上一个类似枚举的搜索尝试过程，在搜索尝试过程中寻找问题的解，当发现原来选择的路径达不到目标时，就退一步，也就是“回溯”，重新选择尝试别的路径。这种走不通就退回再走的技术就是回溯法。许多复杂的、规模较大的问题都可以使用回溯法，因此它有“通用解题方法”的美称。E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B4103.经典算法设计回溯法1）哈密顿回路问题

哈密顿回路，由天文学家哈密顿提出，它的意思是：由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。通过前面的学习我们知道，旅行商问题其实就是找出其中距离最小的一条哈密顿回路的问题。我们以图9.10为例，使用回溯法给出它的一条哈密顿回路E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73A72FC0F2BE2AA531FE6909217657FE514DBF2DB6715F2B3FBA76C24F6B410回溯法求哈密顿回路E6636B02012BD195C019CE06C16E30A4CA3D07EC2711A616D0819A163DE708FA8F631E03BC41BA960B43DCF0472B73