算法的基本元素.ppt

《算法的基本元素.ppt》由会员分享，可在线阅读，更多相关《算法的基本元素.ppt（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第6章 算法 第第6章章 算法算法6.1 算法算法 6.2 算法的基本元素算法的基本元素6.3 算法的表示算法的表示6.4 循环结构和递归结构循环结构和递归结构6.5 算法的效率算法的效率6.6 计算的限制计算的限制第6章 算法6.1 算算 法法 求解两个整数的最大公约数问题的方法如下：(1)令M为两个整数中的较大者，N为两个整数中的较小者；(2)用M除以N，令R为M除以N的余数；(3)若R不等于0，则令M等于N，N等于R，返回步骤(2)继续；若R等于0，则N中的数值就是两个整数的最大公约数。第6章 算法显然，上述方法满足算法所要求的三点：第一，上述方法的每一个操作步骤都是含义确定的；第二，当

2、两个整数M和N为有限数值时，上述方法可在有限的操作步骤后结束；第三，上述方法的每一个操作步骤都是可以具体执行的。因此，上述方法是一个算法。但是，下面的方法就不是一个算法：(1)构造一个包含所有正整数数值的表；(2)把这个表按从大到小的次序排序。第6章 算法虽然上述方法的两个操作步骤都满足确定性，但是，步骤(1)要求构造包含所有正整数数值的表，所以不满足有穷性；步骤(2)要求把包含无限个正整数数值的表按从大到小的次序排序，而这样的要求是无法作到的，因此不满足可执行性。所以，上述方法不是一个算法。第6章 算法从算法所具有的确定性、可终止性和可执行性，可以得出如下结论：(1)由于算法中所有的操作步骤

3、都具有确定性，而任何确定的、无二义的操作，计算机都可以按部就班地一步步执行，所以，我们很容易就可以把求解问题的算法转变为计算机可以执行的程序。(2)计算机求解任何问题，必须在一个有限的时间段内得到处理结果，算法的可终止性保证了这一点。(3)算法的可执行性保证了所有操作步骤都是在计算机上可以执行的。第6章 算法6.2 算法的基本元素算法的基本元素1.变量大多数算法描述的问题求解过程都是高度概括的，适合于求解同类型的各种具体问题的。例如，6.1节讨论的求解两个整数的最大公约数问题的算法，就可以求解任意整数M和整数N的最大公约数。当把该算法用于求解某个具体问题，如求整数48和整数36的最大公约数时，

4、即是要用整数48代表M，用整数36代表N。第6章 算法2.赋值在算法中，赋值是实现给变量赋值，或对变量中的数值进行修改的一种操作。我们用符号ASSIGN表示赋值，赋值语句格式为ASSIGNnamevalue或ASSIGNnamevalueExpression前一个赋值语句表示把一个具体的数值value赋给符号名字为name的变量。后一个赋值语句表示把一个表达式valueExpression的运算结果(其值为一个确定的数值)赋给符号名字为name的变量。第6章 算法例如，若定义age为一个变量，就可以用如下赋值语句把数值20存放在变量age中：ASSIGNage20又如，当要表示某人的年龄要在原

5、来年龄的基础上加一岁时，就可以用如下赋值语句实现：ASSIGNageage+1其中，age+1就是一个表达式，当变量age中原来存放的数值是20时，则该表达式的运算结果就是21。该赋值语句执行完后，变量age中的数值就不再是20，而变成了21。第6章 算法3.分支在算法描述中，经常要根据不同的情况进行不同的处理。例如，对于一个分段函数，当自变量x满足某种条件时，函数y=f(x)就取某个数学表达式；当自变量x满足另一种条件时，函数y=f(x)就取另一个数学表达式。算法中的这种结构称作分支结构。设符号IF、THEN和ELSE是算法中表示分支结构的符号，分支语句的格式为：IF(condition)T

6、HENactivityOneELSEactivityTwo或IF(condition)THENactivity第6章 算法其中，condition表示条件，activityOne表示一种处理方法，activityTwo表示另一种处理方法。前一种语句格式的含义是：当条件condition成立时，执行处理方法activityOne；否则(即条件condition不成立时)，执行处理方法activityTwo。前一种语句的执行过程如图6-1(a)所示。后一种语句格式是分支语句的一种简单情况，其含义是：当条件condition成立时，执行处理方法activity；否则，不作任何处理。后一种语句的执行过

7、程如图6-1(b)所示。在分支语句中，一种处理方法既可以是一条语句，也可以是一组语句。第6章 算法图6-1分支语句的执行过程第6章 算法(a)分支类型1；(b)分支类型2例如，下面例子就描述了x大于0和x小于或等于0两种情况时两个分支的不同处理：IF(x0)THENASIGNyx+3ELSEASIGNyx+5又例如，下面例子描述了当x大于10时y等于y+1，而当x小于或等于10时不作任何处理的分支处理：IF(x10)THENASIGNyy+1第6章 算法分支语句可以嵌套使用，嵌套形式的分支语句可以表示三种或三种以上的不同处理情况。例如，下面例子就描述了当x等于0、x小于0、x大于0三种情况时的

8、分支处理：IF(x=0)THENASIGNyx+3ELSEIF(x0)ASIGNyx+5ELSE ASIGNyx-5第6章 算法4.循环在算法描述中，经常要在满足某种条件的情况下，连续不断地执行某个相同的处理方法。例如，要完成1到100的累加运算，就可以令变量sum初始为数值0，令变量x初始为数值1，然后判断变量x是否小于或等于100，当x小于或等于100时，令变量sum等于sum+x，并且令变量x等于x+1；当x大于100时，结束这种处理过程。算法中的这种结构称作循环结构。设符号WHILE和DO是算法中表示循环结构的符号，循环语句的格式为WHILE(condition)DOactivity第

9、6章 算法图6-2循环语句的执行过程第6章 算法其中，condition表示条件，activity表示一种处理方法。循环语句的含义是：当条件condition成立时，执行处理方法activity。这里所说的处理方法既可以是一条语句，也可以是一组语句。为了使循环过程在有限步后结束，在处理方法activity中一定要对条件condition作某种改变，并要使这种改变每次都更逼近条件condition不成立。循环语句的执行过程如图6-2所示。第6章 算法例如，求1到100的累加和问题的算法就可以描述如下：ASIGNsum0ASIGNx1WHILE(x=100)DOASIGNsumsum+xASIGN

10、xx+1第6章 算法上述算法中语句ASIGNsumsum+x完成累加运算，语句ASIGNxx+1既完成变量数值增1，又完成对条件x=100作某种改变，并使这种改变每次都更逼近条件x=100不成立。由于上述循环结构的循环体部分有两条语句，所以在书写时要用一对花括号括起来。如果算法中没有对变量x的改变，或没有使这种改变每次都更逼近条件x=100不成立(若语句为ASIGNxx-1，就不会更逼近条件x=100不成立)，则上述算法就永远不会结束。永远不会满足循环结束条件的循环结构称为死循环。我们知道，算法的定义限制算法必须具有有穷性，所以，算法设计要避免出现死循环。第6章 算法5.过程一个算法可以在许多

11、地方使用，若要把一个算法表示成许多地方都能使用的形式，就需要规定一种固定格式，这就是过程。设符号PROCEDURE是算法中表示过程的符号，过程语句的格式为：PROCEDUREName(ParameterList)过程体第6章 算法其中，Name是过程名，一对花括号括起来的部分是过程体。过程体可以是任意语句序列。ParameterList是过程的参数表，一个过程通常有若干个参数，这若干个参数称为该过程的参数表。参数是一个数值未定的变量，这样就可以用一个带参数表的过程表示一个范围很宽的算法。例如，求1100的累加和问题的算法是一个使用范围较窄的算法，具体算法如前所述；而求1n(n为任意的整数)的累

12、加和问题的算法就是一个使用范围较宽的算法，可以把后一个问题表示成带一个参数的过程。求1n的累加和问题的过程如下：第6章 算法PROCEDURESum1(n)ASIGNsum0ASIGNx1WHILE(x=n)DOASIGNsumsum+xASIGNxx+1其中，符号Sum1是过程名，n是该过程的参数。第6章 算法一个过程可以有若干个参数。例如，求n1n2的累加和问题就可以表示成如下过程：PROCEDURESum2(n1,n2)ASIGNsum0ASIGNxn1WHILE(x=n2)DOASIGNsumsum+xASIGNxx+1第6章 算法其中，符号Sum2是过程名，n1和n2是该过程的两个参

13、数，n1表示要累加的起始数值，n2表示要累加的结束数值。一个过程也可以没有一个参数。例如，求1100的累加和问题就可以表示成不带参数的如下过程：PROCEDURESum3ASIGNsum0ASIGNx1WHILE(x=100)DO第6章 算法ASIGNsumsum+xASIGNxx+1其中，符号Sum3是过程名，该过程没有参数。过程使我们可以把一个复杂问题的大算法表示成若干个简单问题的小的过程模块的合成，这就像我们可以把制造一个汽车的过程，分解成先分别制造发动机、轮胎、车灯等部件，然后再把这些部件组装起来一样。第6章 算法6.3 算法的表示算法的表示在第1章和本章前两节中，我们在表示算法时使用

14、了几种不同的表示方法，这也就是说，一个相同含义的算法可以有几种不同的表示方法。概括来说，算法主要有三种表示形式，即文字形式、伪码形式和程序设计语言形式。第6章 算法1.文字形式算法的步骤可以用文字形式来表示。求解两个整数的最大公约数的文字形式的算法重述如下：(1)令M为两个整数中的较大者，N为两个整数中的较小者；(2)用M除以N，令R为M除以N的余数；(3)若R不等于0，则令M等于N，N等于R，返回步骤(2)继续；若R等于0，则N中的数值就是两个整数的最大公约数。第6章 算法2.伪码形式算法的步骤可以用6.2节讨论的基本语句格式来构成。由于6.2节讨论的基本语句不是计算机能直接理解和执行的程序

15、语句，而是一种仿程序语句的形式，所以也称作伪码。这样的算法表示方法称作算法的伪码形式。求解两个整数的最大公约数的伪码形式的算法如下：PROCEDURECommDivisor(m,n)IF(mn)THEN第6章 算法ASIGNtempmASIGNmnASIGNntempASIGNrm%nWHILE(r!=0)DOASIGNmnASIGNnr第6章 算法ASIGNrm%n由于伪码规定了特定符号的含义和固定的语句格式，所以伪码形式的算法结构非常固定。虽然伪码形式的算法只能用在人类之间传递思想和智能，但是，由于伪码的每个基本语句和任何计算机高级语言的语句格式都非常接近，所以，可以很方便地把伪码形式的算

16、法转变为计算机可以直接理解和执行的任何计算机高级语言的程序。第6章 算法3.程序设计语言形式在第1章我们就定义过，程序是用程序设计语言表示出来的算法，或者说，程序是处理特定问题的计算机可识别的步骤集合。因此，算法也可以用某种计算机程序设计语言来表示，这称为算法的程序形式。求解两个整数的最大公约数的C语言函数(C语言中的函数相当于伪码中的过程)如下：intCommDivisor(intm,intn)第6章 算法inttemp,r;if(mn)temp=m;m=n;n=temp;r=m%n;while(r!=0)第6章 算法m=n;n=r;r=m%n;returnr;第6章 算法对比求解两个整数的

17、最大公约数算法的伪码形式和C语言程序形式，可以发现，其差别主要有以下三点：(1)在C语言程序中，所有变量在第一次出现时，前边都增加了符号int，这称为变量定义。在所有高级语言中，变量定义是指给变量分配一个具体大小的存储单元空间。(2)在C语言程序中，赋值语句采用了更为简单的表示形式。例如，C语言程序中的语句“temp=m;”就表示伪码形式算法的语句“ASIGNtempm”。第6章 算法(3)在C语言程序中，每条语句结束后都增加了语句的结束标记符号“;”。(4)在C语言程序的最后一行，增加了一条“returnr;”语句，该语句是C语言程序实现过程的数据传送所必须的。上述C语言程序中增加的部分，都

18、属于把算法转换为程序时要考虑的“细节”。这是因为，程序是要让计算机具体运行的，如果没有上述“细节”，计算机就无法运行程序。第6章 算法语言程序中不定义变量temp，计算机就无法知道变量temp需要分配多大的存储单元空间，该变量是需要占用4个字节呢，还是需要占用8个字节？我们在第2章讨论过，存储单元的字节数不同，该存储单元存放的数据(即这里的变量)的数值范围就不同。4个字节的存储单元可表示的数据的数值范围为-32768+32767，如果要处理的数据大于这个范围，就要定义占用更大存储单元空间的变量。第6章 算法6.4 循环结构和递归结构循环结构和递归结构用计算机求解问题(或称处理数据)的效率非常高

19、的原因，是计算机的运行速度非常快。计算机是通过运行程序来求解相应问题的，如果程序中的每条语句都只执行一次，那么这样的程序要么只能求解非常简单的问题，要么程序设计人员编写的程序中语句行将非常之多。实际的情况是上述两种情况都不是，原因是程序中的每条语句都只执行一次的假设不成立。第6章 算法6.4.1循环结构循环结构是算法中最主要和最基本的一种重复结构。下面首先给出循环结构算法的两个例子，然后用例6-2算法的执行过程讨论循环结构算法的执行流程。1.循环结构算法的设计【例6-1】设计表的查找问题的文字形式的顺序查找算法。分析：对于有n个数据元素的表，查找表中是否存在一个数据元素为x的数据元素的顺序查找

20、过程是：用数据元素x依次和表中的第一个数据元素到表中的最后一个数据元素比较，第6章 算法果表中的某一个数据元素和数据元素x相同，则查找成功(即表中存在数据元素x)，查找过程结束；如果表中的所有数据元素都和数据元素x不相同，则查找失败(即表中不存在数据元素x)，查找过程结束。这样的顺序查找算法是一个循环结构的算法。下面给出使用了伪码WHILE-DO的文字形式的循环结构的查找算法：(1)取表中的第一个数据元素赋给变量temp；第6章 算法(2)WHILE(如果变量temp的数值不等于变量x中数值，并且表中还存在下一个数据元素)顺序执行，否则转到(4)；(3)DO(取表中的下一个数据元素赋给变量te

21、mp)转到(2)继续执行；(4)如果temp的数值等于变量x数值，则查找成功；否则查找失败；(5)结束。第6章 算法【例6-2】设计计算阶乘n!问题的伪码形式的循环结构算法。分析：n!等于n(n-1)(n-2)21，所以，计算阶乘n!的算法是一个循环结构的算法。下面给出计算阶乘n!的伪码形式的循环结构的算法。为简化表示以及和高级语言程序比较方便起见，下面的 赋 值 语 句 采 用 符 号“=”表 示。例 如，语 句“pro=1”等同于语句“ASIGNpro1”。算法如下：第6章 算法PROCEDUREFactorial(n)pro=1;m=1;WHILE(m=n)DOpro=pro*m;m=m

22、+1;第6章 算法2.循环结构算法的执行流程下面用例6-2算法的执行过程讨论循环结构算法的执行流程。对于计算阶乘问题的算法，若要计算4！，则n=4，执行过程是：(1)执行pro=1和m=1;(2)由于m=1,n=4,mn，所以执行pro=pro*m和m=m+1；(3)由于m=2,n=4,mn，所以执行pro=pro*m和m=m+1；(4)由于m=3,n=4,mn，所以结束循环语句的执行。(7)结束。我们再来讨论循环算法的执行流程。以计算阶乘问题的算法为例来讨论。n=4时的阶乘问题算法的执行过程上面已给出，这样的执行过程可以归纳如下：(1)赋循环过程的初始数值pro=1和m=1；(2)测试循环过

23、程的条件m1)IF(n%2!=0)THENn=3*n+1;ELSEn=n/2;第6章 算法其中，算术表达式n%2表示结果为n除以2后的余数，所以分支判断条件n%2!=0，是判断数值n是否为奇数。算术表达式n/2表示结果为n除以2的整数部分。分析：这段程序代码对所有输入整数n都会停机吗？没有人知道答案。很多研究者做过的许多试验只能表明：已经试过的每一个输入数值该代码段都会停机。算法要求具有确定性，但是，许多问题的求解步骤不具有确定性的答案。我们把不具有确定性答案的问题称为不可解问题。第6章 算法我们希望计算机解决的许多问题是不可解的问题。例如，判断任意一个程序中是否存在计算机病毒的问题是一个有实用意义的问题。所谓计算机病毒，就是怀有恶意的一些人蓄意强加在计算机中的一段“捣乱”程序。但遗憾的是，我们不能肯定地确定任意一个程序是否包含计算机病毒。因此，所有反病毒程序测试出的某个程序包含病毒的诊断，都只能基于“可能”的基础上。这就像医生诊断某个患者的病因，只能基于“可能”的基础上，不可能百分之百的正确。