算法的基本元素

《算法的基本元素》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、体执行的。因此，上述方法是一个算法。但是，下面的方法就不是一个算法：(1)构造一个包含所有正整数数值的表；(2)把这个表按从大到小的次序排序。虽然上述方法的两个操作步骤都满足确定性，但是，步骤(1)要求构造包含所有正整数数值的表，所以不满足有穷性；步骤(2)要求把包含无限个正整数数值的表按从大到小的次序排序，而这样的要求是无法作到的，因此不满足可执行性。所以，上述方法不是一个算法。从算法所具有的确定性、可终止性和可执行性，可以得出如下结论：(1)由于算法中所有的操作步骤都具有确定性，而任何确定的、无二义的操作，计算机都可以按部就班地一步步执行，所以，我们很容

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

4、或对变量中的数值进行修改的一种操作。我们用符号ASSIGN表示赋值，赋值语句格式为ASSIGNnamevalue或ASSIGNnamevalueExpression前一个赋值语句表示把一个具体的数值value赋给符号名字为name的变量。后一个赋值语句表示把一个表达式valueExpression的运算结果(其值为一个确定的数值)赋给符号名字为name的变量。例如，若定义age为一个变量，就可以用如下赋值语句把数值20存放在变量age中：ASSIGNage20又如，当要表示某人的年龄要在原来年龄的基础上加一岁时，就可以用如下赋值语句实现：ASSIGNagea

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

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

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

8、==0)THENASIGNyx+3ELSEIF(x<