算法的概念简单算法举例算法的特性怎样表ppt课件

1、2.1算法的概念算法的概念2.2简单算法举例简单算法举例2.3算法的特性算法的特性2.4怎样表示一个算法怎样表示一个算法2.5构造化程序设计方法构造化程序设计方法习题习题第2章 程序的灵魂算法一个程序应包括以下两方面内容一个程序应包括以下两方面内容:(1) 对数据的描画。在程序中要指定数据的类型和数对数据的描画。在程序中要指定数据的类型和数据的组织方式，即数据构造据的组织方式，即数据构造(data structure)。(2) 对操作的描画。即操作步骤，对操作的描画。即操作步骤， 也就是算法也就是算法(algorithm)。数据是操作的对象，操作的目的是对数据进展加工数据是操作的对象，操作的目

2、的是对数据进展加工处置，以得到期望的结果。作为程序设计人员，处置，以得到期望的结果。作为程序设计人员，必需仔细思索和设计数据构造和操作步骤必需仔细思索和设计数据构造和操作步骤(即算法即算法)。因此，著名计算机科学家沃思因此，著名计算机科学家沃思(Nikiklaus Wirth)提提出一个公式出一个公式数据构造数据构造 + 算法算法 = 程序程序实践上，一个程序除了以上两个主要要素之外，还实践上，一个程序除了以上两个主要要素之外，还该当采用构造化程序设计方法进展程序设计，并该当采用构造化程序设计方法进展程序设计，并且用某一种计算机言语表示。因此，可以这样表且用某一种计算机言语表示。因此，可以这样

3、表示：示：程序程序 = 算法算法 + 数据构造数据构造 + 程序设计方法程序设计方法 + 言语工具言语工具和环境和环境也就是说，以上也就是说，以上4个方面是一个程序设计人员所应具个方面是一个程序设计人员所应具备的知识。在设计一个程序时要综合运用这几方备的知识。在设计一个程序时要综合运用这几方面的知识。在这面的知识。在这4个方面中，算法是灵魂，数据构个方面中，算法是灵魂，数据构造是加工对象，言语是工具，编程需求采用适宜造是加工对象，言语是工具，编程需求采用适宜的方法。算法是处理的方法。算法是处理“做什么和做什么和“怎样做的怎样做的问题。程序中的操作语句，实践上就是算法的表问题。程序中的操作语句，

4、实践上就是算法的表达。显然，不了解算法就谈不上程序设计。达。显然，不了解算法就谈不上程序设计。我们的目的是使读者经过学习本书，可以知道怎样我们的目的是使读者经过学习本书，可以知道怎样编写一个编写一个C程序，并且可以编写出不太复杂的程序，并且可以编写出不太复杂的C程程序。书中将经过一些实例把以上序。书中将经过一些实例把以上4个方面的知识结个方面的知识结合起来，引见如何编写一个合起来，引见如何编写一个C程序。程序。由于算法的重要性，在本章中先引见有关算法的初由于算法的重要性，在本章中先引见有关算法的初步知识，以便为后面各章的学习建立一定的根底。步知识，以便为后面各章的学习建立一定的根底。2.1 算

5、算 法法 的的 概概 念念从事各种任务和活动，都必需事先想好进展从事各种任务和活动，都必需事先想好进展的步骤，然后按部就班地进展，才干防止产的步骤，然后按部就班地进展，才干防止产生错乱。生错乱。不要以为只需不要以为只需“计算的问题才有算法。广计算的问题才有算法。广义地说，为处理一个问题而采取的方法和步义地说，为处理一个问题而采取的方法和步骤，就称为骤，就称为“算法。算法。 对同一个问题，可以有不同的解题方法和步对同一个问题，可以有不同的解题方法和步骤。方法有优劣之分。有的方法只需进展很骤。方法有优劣之分。有的方法只需进展很少的步骤，而有些方法那么需求较多的步骤。少的步骤，而有些方法那么需求较多

6、的步骤。普通说，希望采用简单的和运算步骤少的方普通说，希望采用简单的和运算步骤少的方法。因此法。因此 ，为了有效地进展解题，不仅需，为了有效地进展解题，不仅需求保证算法正确，还要思索算法的质量，选求保证算法正确，还要思索算法的质量，选择适宜的算法。择适宜的算法。本书所关怀的当然只限于计算机算法，即计算机能本书所关怀的当然只限于计算机算法，即计算机能执行的算法。执行的算法。计算机算法可分为两大类别：数值算法和非数值算计算机算法可分为两大类别：数值算法和非数值算法。数值运算的目的是求数值解法。数值运算的目的是求数值解 。非数值运算包。非数值运算包括的面非常广泛，最常见的是用于事务管理领域。括的面非

7、常广泛，最常见的是用于事务管理领域。目前，计算机在非数值运算方面的运用远远超越目前，计算机在非数值运算方面的运用远远超越了在数值运算方面的运用。由于数值运算有现成了在数值运算方面的运用。由于数值运算有现成的模型，可以运用数值分析方法，因此对数值运的模型，可以运用数值分析方法，因此对数值运算的算法研讨比较深化，算法比较成熟。对各种算的算法研讨比较深化，算法比较成熟。对各种数值运算都有比较成熟的算法可供选用。人们经数值运算都有比较成熟的算法可供选用。人们经常把这些算法汇编成册常把这些算法汇编成册(写成程序方式写成程序方式)，或者将这，或者将这些程序存放在磁盘或磁带上，供用户调用。些程序存放在磁盘或

8、磁带上，供用户调用。而非数值运算的种类繁多，要求各异，难以规范化，而非数值运算的种类繁多，要求各异，难以规范化，因此只对一些典型的非数值运算算法因此只对一些典型的非数值运算算法(例如排序算例如排序算法法)作比较深化的研讨。其他的非数值运算问题，作比较深化的研讨。其他的非数值运算问题，往往需求运用者参考已有的类似算法重新设计处往往需求运用者参考已有的类似算法重新设计处理特定问题的专门算法。理特定问题的专门算法。本书不能够罗列一切算法，只是想经过一些典型算本书不能够罗列一切算法，只是想经过一些典型算法的引见，协助读者了解如何设计一个算法，推法的引见，协助读者了解如何设计一个算法，推进读者举一反三。

9、希望读者经过本章引见的例子进读者举一反三。希望读者经过本章引见的例子了解怎样提出问题，怎样思索问题，怎样表示一了解怎样提出问题，怎样思索问题，怎样表示一个算法。个算法。2.2 简单算法举例简单算法举例例例2.1 求求12345。可以用最原始的方法进展。可以用最原始的方法进展。步骤步骤1： 先求先求12，得到结果，得到结果2。步骤步骤2： 将步骤将步骤1得到的乘积得到的乘积2再乘以再乘以3，得到，得到结果结果6。步骤步骤3： 将将6再乘以再乘以4，得，得24。步骤步骤4： 将将24再乘以再乘以5，得，得120。这就是最后的。这就是最后的结果。结果。这样的算法虽然是正确的，但太繁琐。假设这样的算法

10、虽然是正确的，但太繁琐。假设要求要求121000，那么要写，那么要写999个步骤，个步骤，显然是不可取的。而且每次都直接运用上一显然是不可取的。而且每次都直接运用上一步骤的数值结果步骤的数值结果(如如2，6，24等等)，也不方便。，也不方便。该当找到一种通用的表示方法。该当找到一种通用的表示方法。可以设两个变量，一个变量代表被乘数，一个变量可以设两个变量，一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。今设每一步骤的乘积放在被乘数变量中。今设p为被乘为被乘数，数，i为乘数。用循环算法来求结果。可以将

11、算法为乘数。用循环算法来求结果。可以将算法改写如下：改写如下：S1： 使使p=1S2： 使使i=2S3： 使使pi，乘积仍放在变量，乘积仍放在变量p中，可表示为中，可表示为pi=pS4： 使使i的值加的值加1，即，即i+1 = iS5： 假设假设i不大于不大于5，前往重新执行步骤，前往重新执行步骤S3以及其后以及其后的步骤的步骤S4和和S5；否那么，算法终了。最后得到；否那么，算法终了。最后得到p的的值就是值就是5!的值。的值。上面的上面的S1，S2代表步骤代表步骤1，步骤，步骤2S是是step(步步)的缩写。这是写算法的习惯用法。的缩写。这是写算法的习惯用法。请读者仔细分析这个算法，能否得到

12、预期的结果。请读者仔细分析这个算法，能否得到预期的结果。显然这个算法比前面列出的算法简练。显然这个算法比前面列出的算法简练。假设标题改为求假设标题改为求1357911。算法只需作很少的改动即可：算法只需作很少的改动即可： S1： 1=pS2： 3=iS3： pi=pS4： i+2=iS5： 假设假设i11，前往，前往S3； 否那么，终了。否那么，终了。可以看出，用这种方法表示的算法具有通用性、灵可以看出，用这种方法表示的算法具有通用性、灵敏性。敏性。S3到到S5组成一个循环，在实现算法时，要组成一个循环，在实现算法时，要反复多次执行反复多次执行S3、S4、S5等步骤，直到某一时辰，等步骤，直到

13、某一时辰，执行执行S5步骤时经过判别，乘数步骤时经过判别，乘数i已超越规定的数值已超越规定的数值而不前往而不前往S3步骤为止。此时算法终了，变量步骤为止。此时算法终了，变量p的值的值就是所求结果。就是所求结果。由于计算机是高速进展运算的自动机器，实现循环由于计算机是高速进展运算的自动机器，实现循环是轻而易举的，一切计算机高级言语中都有实现是轻而易举的，一切计算机高级言语中都有实现循环的语句。因此，上述算法不仅是正确的，而循环的语句。因此，上述算法不仅是正确的，而且是计算机能实现的较好的算法。且是计算机能实现的较好的算法。请读者仔细分析循环终了的条件，即请读者仔细分析循环终了的条件，即S5步骤。

14、假设步骤。假设在求在求1211时，将时，将S5步骤写成步骤写成S5： 假设假设i11，前往，前往S3。这样会有什么问题这样会有什么问题?会得到什么结果会得到什么结果?例例2.2 有有50个学生，要求将他们之中成果在个学生，要求将他们之中成果在80分以上分以上者打印出来。用者打印出来。用n表示学生学号，表示学生学号，n1代表第一个学代表第一个学生学号，生学号，ni代表第代表第i个学生学号。用个学生学号。用g代表学生成果，代表学生成果，gi代表第代表第i个学生成果，算法可表示如下。个学生成果，算法可表示如下。S1：1=iS2：假设：假设gi80，那么打印，那么打印ni和和gi，否那么不打印，否那么

15、不打印S3：i+1=iS4：假设：假设i50，前往，前往S2，继续执行；否那么，算法，继续执行；否那么，算法终了。终了。本例中，变量本例中，变量i作为下标，用它来控制序号作为下标，用它来控制序号(第几个学第几个学生，第几个成果生，第几个成果)。当。当i超越超越50时，表示已对时，表示已对50个学个学生的成果处置终了，算法终了。生的成果处置终了，算法终了。例例2.3 断定断定20002500年中的每一年能否闰年，将结年中的每一年能否闰年，将结果输出。果输出。闰年的条件是：闰年的条件是： 能被能被4整除，但不能被整除，但不能被100整除的整除的年份都是闰年，如年份都是闰年，如1996年，年，200

16、4年是闰年；能年是闰年；能被被100整除，又能被整除，又能被400整除的年份是闰年。如整除的年份是闰年。如1600年、年、2000年是闰年。不符合这两个条件的年年是闰年。不符合这两个条件的年份不是闰年。份不是闰年。算法可表示如下：算法可表示如下： 设设y 为被检测的年份。可采取以下步骤：为被检测的年份。可采取以下步骤： S1：2000=yS2： y不能被不能被4整除，那么输出整除，那么输出y “不是闰年。然不是闰年。然后转到后转到S6S3：假设：假设y能被能被4整除，不能被整除，不能被100整除，那么输出整除，那么输出y “是闰年。然后转到是闰年。然后转到S6S4：假设：假设y能被能被100整

17、除，又能被整除，又能被400整除，输出整除，输出y“是闰年；否那么输出是闰年；否那么输出“不是闰年。不是闰年。 然后转然后转到到S6S5：输出：输出y “不是闰年不是闰年S6：y+1=yS7：当：当y2500时，转时，转S2继续执行，如继续执行，如y2500，算法，算法停顿。停顿。在这个算法中，采取了多次判别。先判别在这个算法中，采取了多次判别。先判别y能否被能否被4整除，如不能，那么整除，如不能，那么y必然不是闰年。如必然不是闰年。如y 能被能被4整整除，并不能马上决议它能否闰年，还要看它能否除，并不能马上决议它能否闰年，还要看它能否被被100整除。如不能被整除。如不能被100整除，那么一定

18、是闰年整除，那么一定是闰年(例如例如1996年年)。如能被。如能被100整除，还不能判别它能整除，还不能判别它能否闰年，还要被否闰年，还要被400整除，假设能被整除，假设能被400整除，那整除，那么它是闰年，否那么不是闰年。么它是闰年，否那么不是闰年。在这个算法中，每做一步，都分别分别出一些范围在这个算法中，每做一步，都分别分别出一些范围(巳能断定为闰年或非闰年巳能断定为闰年或非闰年)，逐渐减少范围，使被，逐渐减少范围，使被判别的范围愈来愈小，直至执行判别的范围愈来愈小，直至执行S5时，只能够是时，只能够是非闰年。见图非闰年。见图2.1表示。表示。图图 2.1从图从图2.1可以看出：可以看出：

19、“其他这一部分，包括能被其他这一部分，包括能被4整除，又能被整除，又能被100整除，而不能被整除，而不能被400整除的那些整除的那些年份年份(如如1900年年) ，是非闰年。，是非闰年。在思索算法时，该当仔细分析所需判别的条件，如在思索算法时，该当仔细分析所需判别的条件，如何一步一步减少被判别的范围。有的问题，判别何一步一步减少被判别的范围。有的问题，判别的先后次序是无所谓的，而有的问题，判别条件的先后次序是无所谓的，而有的问题，判别条件的先后次序是不能恣意颠倒的，读者可根据详细的先后次序是不能恣意颠倒的，读者可根据详细问题决议其逻辑。问题决议其逻辑。例例2.4 求求1-1/2+1/3-1/4

20、+1/99-1/100。算法可以表示如下：算法可以表示如下：S1：1=signS2：1=sumS3：2=denoS4：(-1)sign=signS5：sign(1/deno)=termS6：sum+term=sumS7：deno+1=denoS8：假设：假设deno100前往前往S4；否那么算法终了。；否那么算法终了。在步骤在步骤S1中先预设中先预设sign代表级数中各项的符号，代表级数中各项的符号，它的值为它的值为1或或-1。在步骤。在步骤S2中使中使sum等于等于1 ，相当，相当于已将级数中的第一项放到了于已将级数中的第一项放到了sum中。在步骤中。在步骤S3中中使分母的值为使分母的值为2

21、。在步骤。在步骤S4中使中使sign的值变为的值变为-1。在步骤在步骤S5中求出级数中第中求出级数中第2项的值项的值-1/2。在步骤。在步骤S6中将刚刚求出的第二项的值中将刚刚求出的第二项的值-1/2累加到累加到sum中。至中。至此，此，sum的值是的值是1-1/2。在步骤。在步骤S7中使分母中使分母deno的的值加值加1变成变成3。执行。执行S8步骤，由于步骤，由于deno100，故前往故前往S4步骤，步骤，sign的值改为的值改为1，在，在S5中求出中求出term的值为的值为1/3，在，在S6中将中将1/3累加到累加到sum中。然后中。然后S7再再使分母变为使分母变为4。按此规律反复执行。

22、按此规律反复执行S4到到S8步骤，直步骤，直到分母大于到分母大于100为止。一共执行了为止。一共执行了99次循环，向次循环，向sum累参与了累参与了99个分数。个分数。sum最后的值就是级数的最后的值就是级数的值。值。例例2.5 对一个大于或等于对一个大于或等于3的正整数，判别它是不是的正整数，判别它是不是一个素数。一个素数。所谓素数，是指除了所谓素数，是指除了1和该数本身之外，不能被其他和该数本身之外，不能被其他任何整数整除的数。例如，任何整数整除的数。例如，13是素数，由于它不是素数，由于它不能被能被2，3，4，12整除。整除。判别一个数判别一个数n(n3)能否素数的方法是很简单的：将能否

23、素数的方法是很简单的：将n作为被除数，将作为被除数，将2到到(n-1)各个整数轮番作为除数，各个整数轮番作为除数，假设都不能被整除，那么假设都不能被整除，那么n为素数。为素数。算法可以表示如下：算法可以表示如下：S1：输入：输入n的值的值S2：2=i i作为除数作为除数S3：n被被i除，得余数除，得余数rS4：假设：假设r=0，表示，表示n能被能被i整除，那么打印整除，那么打印n“不是不是素数，算法终了；否那么执行素数，算法终了；否那么执行S5S5：i+1=iS6：假设：假设in-1，前往，前往S3；否那么打印；否那么打印 n “是素数，是素数，然后终了。然后终了。实践上实践上n不用被不用被2

24、到到(n-1)的整数除，只需被的整数除，只需被2到到n的开的开方间整数除即可，甚至只需被方间整数除即可，甚至只需被2到到n之间的整数除之间的整数除即可。例如，判别即可。例如，判别13能否素数，只需将能否素数，只需将13被被2、3除即可，如都除不尽，除即可，如都除不尽，n 必为素数。必为素数。S6步骤可改为：步骤可改为：S6：假设：假设in，前往，前往S2；否那么算法终了。；否那么算法终了。经过以上几个例子，可以初步了解怎样设计一个算经过以上几个例子，可以初步了解怎样设计一个算法。法。2.3 算法的特性算法的特性一个算法应该具有以下特点：一个算法应该具有以下特点：1.有穷性有穷性一个算法应包含有

25、限的操作步骤，而不能是一个算法应包含有限的操作步骤，而不能是无限的。无限的。现实上，现实上，“有穷性往往指有穷性往往指“在合理的范围在合理的范围之内。终究什么算之内。终究什么算“合理限制，并无严合理限制，并无严厉规范，由人们的常识和需求而定。厉规范，由人们的常识和需求而定。2.确定性确定性算法中的每一个步骤都该当是确定的，而不算法中的每一个步骤都该当是确定的，而不该当是模糊的、模棱两可的。该当是模糊的、模棱两可的。3.有零个或多个输入有零个或多个输入所谓输入是指在执行算法时需求从外界获得必要的所谓输入是指在执行算法时需求从外界获得必要的信息。一个算法也可以没有输入。信息。一个算法也可以没有输入

26、。4. 有一个或多个输出有一个或多个输出算法的目的是为了求解，算法的目的是为了求解，“解解 就是输出。没有输就是输出。没有输出的算法是没有意义的。出的算法是没有意义的。 5. 有效性有效性算法中的每一个步骤都该当能有效地执行，并得到算法中的每一个步骤都该当能有效地执行，并得到确定的结果。确定的结果。对于不熟习计算机程序设计的人来说，他们可以只对于不熟习计算机程序设计的人来说，他们可以只运用他人已设计好的现成算法，只需根据算法的运用他人已设计好的现成算法，只需根据算法的要求给以必要的输入，就能得到输出的结果。对要求给以必要的输入，就能得到输出的结果。对他们来说，算法好像一个他们来说，算法好像一个

27、“黑箱子一样黑箱子一样 ，他们，他们可以不了解可以不了解“黑箱子中的构造，只是从外部特黑箱子中的构造，只是从外部特性上了解算法的作用，即可方便地运用算法。例性上了解算法的作用，即可方便地运用算法。例如，对一个如，对一个“输入输入3个数，求其中最大值的算法，个数，求其中最大值的算法，可以用图可以用图2.2表示，只需输入表示，只需输入a，b，c3个数，执行个数，执行算法后就能得到其中最大的数。但对于程序设计算法后就能得到其中最大的数。但对于程序设计人员来说，必需会设计算法，并且根据算法编写人员来说，必需会设计算法，并且根据算法编写程序。程序。图图2.22.4 怎样表示一个算法怎样表示一个算法为了表

28、示一个算法，可以用不同的方法。常为了表示一个算法，可以用不同的方法。常用的有自然言语、传统流程图、构造化流程用的有自然言语、传统流程图、构造化流程图、伪代码、图、伪代码、PAD图等。图等。2.4.1 用自然言语表示算法用自然言语表示算法在在2.2节中引见的算法是用自然言语表示的。节中引见的算法是用自然言语表示的。用自然言语表示通俗易懂，但文字冗长，用自然言语表示通俗易懂，但文字冗长， 容易出现容易出现“歧义性。自然言语表示的含义歧义性。自然言语表示的含义往往不太严厉，要根据上下文才干判别其正往往不太严厉，要根据上下文才干判别其正确含义。此外，用自然言语描画包含分支和确含义。此外，用自然言语描画

29、包含分支和循环的算法，不很方便循环的算法，不很方便(如例如例2.5的算法的算法)。因。因此，除了很简单的问题以外，普通不用自然此，除了很简单的问题以外，普通不用自然言语描画算法。言语描画算法。2.4.2 用流程图表示算法用流程图表示算法流程图是用一些图框表示各种操作。用图形表示算流程图是用一些图框表示各种操作。用图形表示算法，直观笼统，易于了解。美国国家规范化协会法，直观笼统，易于了解。美国国家规范化协会ANSI(American National Standard Institute)规定规定了一些常用的流程图符号了一些常用的流程图符号(见图见图2.3)。 图图2.3中菱形框的作用是对一个给

30、定的条件进展判别，中菱形框的作用是对一个给定的条件进展判别，根据给定的条件能否成立来决议如何执行其后的根据给定的条件能否成立来决议如何执行其后的操作。它有一个入口，两个出口。见图操作。它有一个入口，两个出口。见图2.4。衔接点衔接点(小圆圈小圆圈)是用于将画在不同地方的流程线衔接是用于将画在不同地方的流程线衔接起来。如图起来。如图2.5中有两个以为标志的衔接点中有两个以为标志的衔接点(在衔在衔接点圈中写上接点圈中写上“1)，它表示这两个点是相互衔接，它表示这两个点是相互衔接在一同的。实践上它们是同一个点，只是画不下在一同的。实践上它们是同一个点，只是画不下才分开来画。用衔接点，可以防止流程线的

31、交叉才分开来画。用衔接点，可以防止流程线的交叉或过长，使流程图明晰。或过长，使流程图明晰。 图图 2.3图图 2.4 图图 2.5下面对下面对2.2节中所举的几个算法例子，改用流程图表节中所举的几个算法例子，改用流程图表示。示。例例2.6 将例将例2.1求求5!的算法用流程图表示，流程图见图的算法用流程图表示，流程图见图2.6。菱形框两侧的菱形框两侧的“Y和和“N代表代表“是是(yes)和和“否否(no)。假设需求将最后结果打印出来，可以在菱。假设需求将最后结果打印出来，可以在菱形框的下面再加一个输出框，见图形框的下面再加一个输出框，见图2.7。例例2.7 将例将例2.2的算法用流程图表示。将

32、的算法用流程图表示。将50名学生中名学生中成果在成果在80分以上者的学号和成果打印出来，见图分以上者的学号和成果打印出来，见图2.8。在此算法中没有包括输入。在此算法中没有包括输入50个学生数据的部个学生数据的部分，假设包括这个输入数据的部分，流程图如图分，假设包括这个输入数据的部分，流程图如图2.9所示。所示。 图图2.6 图图2.7 图图2.8例例2.8 将例将例2.3断定闰年的算法用流程图表示。断定闰年的算法用流程图表示。见图见图2.10。显然，用图。显然，用图2.10表示算法要比用文字描画表示算法要比用文字描画算法逻辑明晰、易于了解。算法逻辑明晰、易于了解。请读者思索，假设例请读者思索

33、，假设例2.3所表示的算法中，所表示的算法中，S2步骤内步骤内没有最后没有最后“转到转到S6这一句话，而只是这一句话，而只是S2：假设：假设y不能被不能被4整除，那么打印整除，那么打印y “不是闰年不是闰年这样就意味着执行完这样就意味着执行完S2步骤后，不论步骤后，不论S2的执行情况的执行情况如何都应执行如何都应执行S3步骤。请读者画出相应的流程图。步骤。请读者画出相应的流程图。请思索这样的算法在逻辑上有什么错误，从流程请思索这样的算法在逻辑上有什么错误，从流程图上是很容易发现其错误的。图上是很容易发现其错误的。图图2.9 图图2.10例例2.9 将例将例2.4的算法用流程图表示。见图的算法用

34、流程图表示。见图2.11。例例2.10 将例将例2.5判别素数的算法用流程图表示，见图判别素数的算法用流程图表示，见图2.12。一个流程图包括以下几部分：表示相应操作的框；一个流程图包括以下几部分：表示相应操作的框；带箭头的流程线；框内外必要的文字阐明。带箭头的流程线；框内外必要的文字阐明。需求提示的是流程线不要忘记画箭头，由于它是需求提示的是流程线不要忘记画箭头，由于它是反映流程的执行先后次序的。反映流程的执行先后次序的。用流程图表示算法直观笼统，比较清楚地显示出各用流程图表示算法直观笼统，比较清楚地显示出各个框之间的逻辑关系。但是这种流程图占用篇幅个框之间的逻辑关系。但是这种流程图占用篇幅

35、较多，尤其当算法比较复杂时，画流程图既费时较多，尤其当算法比较复杂时，画流程图既费时又不方便。在构造化程序设计方法推行之后，许又不方便。在构造化程序设计方法推行之后，许多书刊已用多书刊已用 N-S构造化流程图替代这种传统的流程构造化流程图替代这种传统的流程图。但是每一个程序编制人员都该当熟练掌握传图。但是每一个程序编制人员都该当熟练掌握传统流程图。统流程图。 图图2.11 图图2.122.4.3 三种根本构造和改良的流程图三种根本构造和改良的流程图1. 传统流程图的弊端传统流程图的弊端传统的流程图用流程线指出各框的执行顺序，对流传统的流程图用流程线指出各框的执行顺序，对流程线的运用没有严厉限制

36、。因此，运用者可以不程线的运用没有严厉限制。因此，运用者可以不受限制地使流程随意地转来转去，使流程图变得受限制地使流程随意地转来转去，使流程图变得毫无规律。这种情况如图毫无规律。这种情况如图2.13所示。所示。这种算法难以阅读，也难以修正，从而使算法的可这种算法难以阅读，也难以修正，从而使算法的可靠性和可维护性难以保证。假设我们写出的算法靠性和可维护性难以保证。假设我们写出的算法能限制流程的无规律恣意转向，阅读起来就很方能限制流程的无规律恣意转向，阅读起来就很方便。便。图图2.13但是，算法上难免会包含一些分支和循环，而不能但是，算法上难免会包含一些分支和循环，而不能够全部由一个一个框顺序组成

37、。例如图够全部由一个一个框顺序组成。例如图2.6到图到图2.12都不是由各框顺序进展的，都包含一些流程的都不是由各框顺序进展的，都包含一些流程的向前或向后的非顺序转向。为理处理这个问题，向前或向后的非顺序转向。为理处理这个问题，人们想象，规定出几种根本构造，然后由这些根人们想象，规定出几种根本构造，然后由这些根本构造按一定规律组成一个算法构造本构造按一定规律组成一个算法构造(好像用一些好像用一些根本预制构件来搭成房屋一样根本预制构件来搭成房屋一样)，整个算法的构造，整个算法的构造是由上而下地将各个根本构造顺序陈列起来的。是由上而下地将各个根本构造顺序陈列起来的。假设能做到这一点假设能做到这一点

38、 ，算法的质量就能得到保证和，算法的质量就能得到保证和提高。提高。2. 三种根本构造三种根本构造1966年，年，Bohra和和Jacopini提出了以下三种根本构造，提出了以下三种根本构造，作为表示一个良好算法的根本单元。作为表示一个良好算法的根本单元。(1) 顺序构造，如图顺序构造，如图2.14所示，虚线框内是一个顺序所示，虚线框内是一个顺序构造。构造。(2) 选择构造，或称选取构造，或称分支构造，如图选择构造，或称选取构造，或称分支构造，如图2.15所示。所示。请留意，无论请留意，无论 p 条件能否成立，只能执行条件能否成立，只能执行A框或框或B框框之一，不能够既执行之一，不能够既执行A框

39、又执行框又执行B框。无论走哪一框。无论走哪一条途径，在执行完条途径，在执行完A或或B之后，都经过之后，都经过b点，然后点，然后脱离本选择构造。脱离本选择构造。A或或B两个框中可以有一个是空两个框中可以有一个是空的的 ，即不执行任何操作，如图，即不执行任何操作，如图2.16所示。所示。图图2.14 图图2.15 图图2.16(3) 循环构造，它又称反复构造。有两类循环构造：循环构造，它又称反复构造。有两类循环构造： 当型当型(While型型)循环构造循环构造见图见图2.17(a)。它的功能是当给定的条件。它的功能是当给定的条件p1成立时，成立时，执行执行A框操作，执行完框操作，执行完A后，再判别

40、条件后，再判别条件p1能否成能否成立，假设依然成立，再执行立，假设依然成立，再执行A框，如此反复执行框，如此反复执行A框，直到某一次框，直到某一次p1条件不成立为止，此时不执行条件不成立为止，此时不执行A框，而从框，而从b点脱离循环构造。点脱离循环构造。 直到型直到型(Until型型)循环循环见图见图2.17(b)。它的功能是先执行。它的功能是先执行A框，然后判别给定框，然后判别给定的的p2条件能否成立，假设条件能否成立，假设p2条件不成立，那么再条件不成立，那么再执行执行A，然后再对，然后再对p2条件作判别，假设条件作判别，假设p2条件依然条件依然不成立，又执行不成立，又执行A如此反复执行如

41、此反复执行A，直到给定，直到给定的的p2条件成立为止，此时不再执行条件成立为止，此时不再执行A，从，从b点脱离点脱离本循环构造。本循环构造。图图2.18是当型循环的运用例子，图是当型循环的运用例子，图2.19是直到型循环是直到型循环的运用例子。的运用例子。图图2.17 图图2.18 图图2.19图图2.18和图和图2.19的作用都是打印的作用都是打印5个数：个数：1，2，3，4，5。可以看到，。可以看到， 对同一个问题既可以用当型循环来对同一个问题既可以用当型循环来处置，也可以用直到型循环来处置。处置，也可以用直到型循环来处置。以上三种根本构造，有以下共同特点：以上三种根本构造，有以下共同特点

42、：(1) 只需一个入口。只需一个入口。(2) 只需一个出口。请留意，一个菱形判别框有两个只需一个出口。请留意，一个菱形判别框有两个出口，而一个选择构造只需一个出口。不要将菱出口，而一个选择构造只需一个出口。不要将菱形框的出口和选择构造的出口混淆。形框的出口和选择构造的出口混淆。(3) 构造内的每一部分都有时机被执行到。对每一个构造内的每一部分都有时机被执行到。对每一个框来说，都应有一条从入口到出口的途径经过它。框来说，都应有一条从入口到出口的途径经过它。图图2.20中没有一条从入口到出口的途径经过中没有一条从入口到出口的途径经过A框。框。(4) 构造内不存在构造内不存在“死循环死循环(无终止的

43、循环无终止的循环)。图。图2.21就是一个死循环。就是一个死循环。图图2.20 图图2.21曾经证明，由以上三种根本构造顺序组成的算法构曾经证明，由以上三种根本构造顺序组成的算法构造，可以处理任何复杂的问题。由根本构造所构造，可以处理任何复杂的问题。由根本构造所构成的算法属于成的算法属于“构造化的算法，它不存在无规构造化的算法，它不存在无规律的转向，只在本根本构造内才允许存在分支和律的转向，只在本根本构造内才允许存在分支和向前或向后的跳转。向前或向后的跳转。其实，根本构造不一定只限于上面三种，只需具有其实，根本构造不一定只限于上面三种，只需具有上述上述4个特点的都可以作为根本构造。人们可以本个

44、特点的都可以作为根本构造。人们可以本人定义根本构造，并由这些根本构造组成构造化人定义根本构造，并由这些根本构造组成构造化程序。例如，可以将图程序。例如，可以将图2.22和图和图2.23这样的构造定这样的构造定义为根本构造。图义为根本构造。图2.23所示的是一个多分支选择构所示的是一个多分支选择构造，根据给定的表达式的值决议执行哪一个框。造，根据给定的表达式的值决议执行哪一个框。图图2.22和图和图2.23虚线框内的构造也是一个入口和一虚线框内的构造也是一个入口和一个出口，并且有上述全部的个出口，并且有上述全部的4个特点。由它们构成个特点。由它们构成的算法构造也是构造化的算法。但是，可以以为的算

45、法构造也是构造化的算法。但是，可以以为像图像图2.22和图和图2.23那样的构造是由三种根本构造派那样的构造是由三种根本构造派生出来的。因此，人们都普遍以为最根本的是本生出来的。因此，人们都普遍以为最根本的是本节引见的三种根本构造。节引见的三种根本构造。图图2.22 图图2.232.4.4 用用N-S流程图表示算法流程图表示算法既然用根本构造的顺序组合可以表示任何复杂的算既然用根本构造的顺序组合可以表示任何复杂的算法构造，那么根本构造之间的流程线就属多余的法构造，那么根本构造之间的流程线就属多余的了。了。1973年美国学者年美国学者I.Nassi和和B.Shneiderman提出了一种提出了一

46、种新的流程图方式。在这种流程图中，完全去掉了新的流程图方式。在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框，或者在该框内还可以包含其他的从属于它的框，或者说，由一些根本的框组成一个大的框。这种流程说，由一些根本的框组成一个大的框。这种流程图又称图又称N-S构造化流程图。这种流程图适于构造化构造化流程图。这种流程图适于构造化程序设计，因此很受欢迎。程序设计，因此很受欢迎。N-S流程图用以下的流程图符号：流程图用以下的流程图符号：(1) 顺序构造顺序构造: 用图用图2.24方式表示。方式表示。A和和

47、B两个框组成两个框组成一个顺序构造。一个顺序构造。(2) 选择构造：用图选择构造：用图2.25表示。它与图表示。它与图2.15相应。当相应。当p条件成立时执行条件成立时执行A操作，操作，p不成立那么执行不成立那么执行B操作。操作。请留意图请留意图2.25是一个整体，代表一个根本构造。是一个整体，代表一个根本构造。图图2.24 图图2.25(3) 循环构造：循环构造： 当型循环构造用图当型循环构造用图2.26方式表示。方式表示。图图2.26表示当表示当p1条件成立时反复执行条件成立时反复执行A操作，直到操作，直到p1条件不成立为止。条件不成立为止。直到型循环构造用图直到型循环构造用图2.27方式

48、表示。方式表示。用以上用以上3种种N-S流程图中的根本框，可以组成复杂的流程图中的根本框，可以组成复杂的N-S流程图，以表示算法。流程图，以表示算法。该当阐明，在图该当阐明，在图2.24、图、图2.25、图、图2.26、图、图2.27中的中的A框或框或B框，可以是一个简单的操作框，可以是一个简单的操作(如读入数据或如读入数据或打印输出等打印输出等)，也可以是，也可以是3个根本构造之一。例如，个根本构造之一。例如，图图2.24所示的顺序构造，其中的所示的顺序构造，其中的A框可以又是一个框可以又是一个选择构造，选择构造，B框可以又是一个循环构造。如图框可以又是一个循环构造。如图2.28所示那样，由

49、所示那样，由A和和B这两个根本构造组成一个顺序这两个根本构造组成一个顺序构造。构造。图图2.26 图图2.27 图图2.28经过下面的几个例子，读者可以了解如何用经过下面的几个例子，读者可以了解如何用N-S流程流程图表示算法。图表示算法。例例2.11 将例将例2.1的求的求5!算法用算法用N-S图表示。见图图表示。见图2.29，它和图它和图2.7对应。对应。例例2.12 将例将例2.2的算法用的算法用N-S图表示。将图表示。将50名名 学生中学生中成果高于成果高于80分的学号和成果打印出来。见图分的学号和成果打印出来。见图2.30和和图图2.31，它们与图，它们与图2.8和图和图2.9对应。对

50、应。例例2.13 将例将例2.3断定闰年的算法用断定闰年的算法用N-S图表示。见图图表示。见图2.32，它和图，它和图2.10对应。对应。例例2.14 将例将例2.4的算法用的算法用N-S图表示。见图图表示。见图2.33，它和，它和图图2.11对应，只是最后加了一个对应，只是最后加了一个“打印打印sum框。框。例例2.15 将例将例2.5判别素数的算法用判别素数的算法用N-S流程图表示。流程图表示。图图2.29 图图2.30 图图2.31图图2.32 图图2.33由图由图2.12可以看出，这个流程图不是由三种根本构可以看出，这个流程图不是由三种根本构造组成的。图中间那个循环部分，有两个出口造组

51、成的。图中间那个循环部分，有两个出口(一一个从第二个菱形框下面出口，另一个在第一个菱个从第二个菱形框下面出口，另一个在第一个菱形框右边出口形框右边出口)，不符合根本构造的特点。由于不，不符合根本构造的特点。由于不能分解为三种根本构造，就无法直接用能分解为三种根本构造，就无法直接用N-S流程图流程图的三种根本构造的符号来表示。因此，应领先对的三种根本构造的符号来表示。因此，应领先对图图2.12做必要的变换。要将第一个菱形框做必要的变换。要将第一个菱形框(“r=0)的两个出口集合在一点，以处理两个出口问题。的两个出口集合在一点，以处理两个出口问题。当当r=0时不直接输出时不直接输出n“不是素数，而

52、只设一个不是素数，而只设一个标志值变量标志值变量w，它的初始形状为，它的初始形状为w=0。当。当r=0时时(表示表示n为非素数为非素数)使使w变成变成1。假设。假设r 0那么坚持那么坚持w=0。w的作用好像一个开关，有两个任务情况：的作用好像一个开关，有两个任务情况：w=0和和w=1。w=1表示表示n为非素数。为非素数。假设最终假设最终w=0，那么表示，那么表示n为素数。然后将为素数。然后将“1=w框的出口线改为指向第二个菱形框，同时将第二框的出口线改为指向第二个菱形框，同时将第二个菱形框中的条件改为个菱形框中的条件改为 “in和和w=0，即只需当，即只需当“in和和“w=0两个条件都满足时才

53、继续执行两个条件都满足时才继续执行循环。假设出现循环。假设出现in或或w0之一，都不会继续执行之一，都不会继续执行循环循环(见图见图2.34)。假设在某一次。假设在某一次r=0，那么应执行，那么应执行1=w，然后，由第二个菱形框判别为，然后，由第二个菱形框判别为“条件不成条件不成立，接着执行图下部的选择构造。此时，立，接着执行图下部的选择构造。此时，w0，表示表示n不是素数，应打印出不是素数，应打印出n不是素数的信息。假不是素数的信息。假设设w=0，那么表示在上面的每次循环中，那么表示在上面的每次循环中，n都不能都不能被每一个被每一个i整除，所以整除，所以n是素数，故输出是素数，故输出n是素数

54、的是素数的信息。信息。图图2.34已由三种根本构造组成，可以用已由三种根本构造组成，可以用N-S图表示此图表示此算法，见图算法，见图2.35。留意图。留意图2.34直到型循环的判别条直到型循环的判别条件为：件为： “直到直到in或或w0，即只需，即只需“in或或w0之一成立，就不再继续执行循环。对此务请读之一成立，就不再继续执行循环。对此务请读者弄清楚。者弄清楚。经过以上例子，可以看出用经过以上例子，可以看出用N-S图表示算法的优点。图表示算法的优点。它比文字描画直观、笼统、它比文字描画直观、笼统、 易于了解；比传统流易于了解；比传统流程图紧凑易画，尤其是它废除了流程线，整个算程图紧凑易画，尤

55、其是它废除了流程线，整个算法构造是由各个根本构造按顺序组成的。法构造是由各个根本构造按顺序组成的。N-S流程流程图中的上下顺序就是执行时的顺序，即图中位置图中的上下顺序就是执行时的顺序，即图中位置在上面的先执行，位置在下面的后执行。写算法在上面的先执行，位置在下面的后执行。写算法和看算法只需从上到下进展就可以了，非常方便。和看算法只需从上到下进展就可以了，非常方便。用用N-S图表示的算法都是构造化的算法图表示的算法都是构造化的算法(它不能够它不能够出现流程无规律的跳转，而只能自上而下地顺序出现流程无规律的跳转，而只能自上而下地顺序执行执行)。 图图2.34 图图2.35归纳起来可知，一个构造化

56、的算法是由一些根本构归纳起来可知，一个构造化的算法是由一些根本构造顺序组成的；每个根本构造又可以包含其他的造顺序组成的；每个根本构造又可以包含其他的根本构造；在根本构造之间不存在向前或向后的根本构造；在根本构造之间不存在向前或向后的跳转，流程的转移只存在于一个根本构造范围之跳转，流程的转移只存在于一个根本构造范围之内内(如循环中流程的跳转如循环中流程的跳转)；一；一 个非构造化的算法个非构造化的算法(如图如图2.12)可以用一个等价的构造化算法可以用一个等价的构造化算法(如图如图2.35)替代，其功能不变。假设一个算法不能分解为假替代，其功能不变。假设一个算法不能分解为假设干个根本构造，那么它

57、必然不是一个构造化的设干个根本构造，那么它必然不是一个构造化的算法。算法。N-S图好像一个多层的盒子，又称盒图图好像一个多层的盒子，又称盒图(box diagram)。2.4.5 用伪代码表示算法用伪代码表示算法用传统的流程图和用传统的流程图和N-S图表示算法，直观易懂，但画图表示算法，直观易懂，但画起来比较费事。因此，流程图适宜表示一起来比较费事。因此，流程图适宜表示一 个算法，个算法，但在设计算法过程中运用不是很理想。为了设计但在设计算法过程中运用不是很理想。为了设计算法时方便，常用一种称为伪代码算法时方便，常用一种称为伪代码(pseudo code)的的工具。工具。伪代码是用介于自然言语

58、和计算机言语之间的文字伪代码是用介于自然言语和计算机言语之间的文字和符号来描画算法。它好像一篇文章，自上而下和符号来描画算法。它好像一篇文章，自上而下地写下来。每一行地写下来。每一行(或几行或几行)表示一个根本操作。它表示一个根本操作。它不用图形符号，因此书写方便不用图形符号，因此书写方便 、格式紧凑，也比、格式紧凑，也比较好懂，便于向计算机言语算法较好懂，便于向计算机言语算法(即程序即程序)过渡。过渡。例如，例如， “打印打印x的绝对值的算法可以用伪代码表的绝对值的算法可以用伪代码表示如下：示如下：IF x is positive THENprint xELSEprint x它像一个英语句子

59、一样好懂，在国外用得比较普遍。也可以它像一个英语句子一样好懂，在国外用得比较普遍。也可以用汉字伪代码，如：用汉字伪代码，如：假设假设 x为正为正打印打印 x否那么否那么打印打印 x也可以中英文混用，如：也可以中英文混用，如：IF x 为正为正print xELSEprint x即计算机言语中具有的语句关键字用英文表示，其即计算机言语中具有的语句关键字用英文表示，其他的可用汉字表示。总之，以便于书写和阅读为他的可用汉字表示。总之，以便于书写和阅读为原那么。用伪代码写算法并无固定的、严厉的语原那么。用伪代码写算法并无固定的、严厉的语法规那么，只需把意思表达清楚，并且书写的格法规那么，只需把意思表达

60、清楚，并且书写的格式要写成明晰易读的方式。式要写成明晰易读的方式。将例将例2.1到例到例2.5的算法用伪代码表示如下。的算法用伪代码表示如下。例例2.16 求求5!。用伪代码表示的算法如下：。用伪代码表示的算法如下： 开场开场置置t的初值为的初值为1置置i的初值为的初值为2当当it2=iwhile iti+1=iprint tEND(算法终了算法终了)在本算法中采用当型循环第在本算法中采用当型循环第3行到笫行到笫5行是一个当型循环。行是一个当型循环。while意思为意思为“当，当， 它表示当它表示当iiwhile ii1=iwhile iiEND(算法终了算法终了)例例2.18 打印打印200