2.2 算法描述_C语言从入门到精通（第5版）-QQ阅读男生科幻网

上QQ阅读APP看书，第一时间看更新

2.2　算法描述

算法包含算法设计和算法分析两个方面。算法设计主要研究怎样针对某一特定类型的问题设计出求解步骤，算法分析则要讨论所设计出来的算法步骤的正确性和复杂性。

对于一些问题的求解步骤，需要一种表达方式，即算法描述。他人可以通过算法描述来了解算法设计者的思路。表示一个算法，可以用不同的方法，常用的有自然语言法、流程图法、N-S流程图法等。

2.2.1　自然语言

自然语言就是人们日常所用的语言，这种表述方式通俗易懂，下面通过实例具体介绍。

【例2.1】求n！。

算法描述步骤如下：

（1）定义3个变量i、n及mul，为i和mul均赋初值为1。

（2）从键盘中输入一个数，赋给n。

（3）将mul乘以i的结果赋给mul。

（4）i的值加1，判断i的值是否大于n，如果大于n，则执行步骤（5），否则执行步骤（3）。

（5）将mul的结果输出。

【例2.2】农夫、羊、狼及白菜过河。

一名农夫要将一只狼、一只羊和一袋白菜运到河对岸。农夫的船很小，每次只能载下农夫本人以及狼、羊、白菜中的一个。但是，他不能把羊和白菜留在岸边，因为羊会把白菜吃掉；也不能把狼和羊留在岸边，因为狼会吃掉羊。那么，农夫该怎样将这3样东西送过河呢？

算法描述步骤如下：

（1）先把羊运过去。

（2）回来运狼。

（3）把狼运到对岸后，把羊装上船运回来。

（4）把羊放到开始的地方，把白菜运过去。

（5）再把羊运过去。

例2.1和例2.2的算法实现过程就是采用自然语言来描述的。从上面的描述中可以发现，自然语言描述的好处就是易懂，弊端是容易产生歧义。例如，将例2.1步骤（3）中的“将mul乘以i的结果赋给mul”改为“mul等于i乘以mul”，这样就产生了歧义。并且，用自然语言来描述较为复杂的算法时，会显得不是很方便，因此一般情况下不采用自然语言来描述。

2.2.2　流程图

流程图是一种传统的算法表示法，它用一些图框来代表各种不同性质的操作，用流程线来指示算法的执行方向。由于它直观形象，易于理解，所以应用广泛。特别是在语言发展的早期阶段，只有通过流程图才能简明地表述算法。

1．流程图符号

流程图使用一些图框来表示各种操作。如图2.1所示为一些常见的流程图符号，其中，起止框用来标识算法的开始和结束；判断框用于对一个给定的条件进行判断，根据条件成立与否来决定如何执行后续操作；输入／输出框用来表示输入／输出；处理框用来表示变量的计算或赋值；流程线用于表示算法的流向；注释框用于表示算法的注释；连接点用于将画在不同地方的流程线连接起来。

2．3种基本结构

Bohra和Jacopini为了提高算法的质量，提出了3种基本结构，即顺序结构、选择结构和循环结构，因为任何一个算法都可由这3种基本结构组成。这3种基本结构之间可以并列，可以相互包含，但不允许交叉，不允许从一个结构直接转到另一个结构的内部去。

任何算法都是由3种基本结构组成的，所以只要规定好3种基本结构的流程图的画法，就可以画出任何算法的流程图。

1）顺序结构

顺序结构是最简单的线性结构。在顺序结构的程序中，各操作按照它们出现的先后顺序执行。如图2.2所示，在执行完A框所指定的操作后，接着执行B框所指定的操作。这个结构中只有一个入口点A和一个出口点B。

图2.1　流程图符号

图2.2　顺序结构

【例2.3】输出数学、语文成绩。

输入两个数，分别代表数学、语文成绩，并分别赋给变量math和chinese，再将这两个数分别输出。

本实例的流程图可以采用顺序结构来实现，如图2.3所示。

2）选择结构

选择结构也称为分支结构，其常见形式有两种，如图2.4和图2.5所示。

图2.3　输出数学、语文成绩

图2.4　选择结构1

图2.5　选择结构2

选择结构中必须包含一个判断框。图2.4所代表的含义是根据给定的条件P是否成立选择执行A框还是B框。图2.5所代表的含义是根据给定的条件P进行判断，如果条件成立则执行A框，否则什么也不做。

【例2.4】判断是否为偶数。

输入一个数，判断该数是否为偶数，并给出相应提示。

本实例的流程图可以采用选择结构来实现，如图2.6所示。

3）循环结构

在循环结构中，反复地执行一系列操作，直到条件不成立时才终止循环。按照判断条件出现的位置，可将循环结构分为当型循环结构和直到型循环结构。

当型循环的流程结构如图2.7所示。先判断条件P是否成立，如果成立，则执行A框；执行完A框后，再判断条件P是否成立，如果成立，接着再执行A框；如此反复，直到条件P不成立为止，此时不执行A框，跳出循环。

直到型循环的流程结构如图2.8所示。先执行A框，然后判断条件P是否成立，如果条件P成立则再执行A；然后判断条件P是否成立，如果成立，接着再执行A框；如此反复，直到条件P不成立，此时不执行A框，跳出循环。

图2.6　判断一个数是否为偶数

图2.7　当型循环

图2.8　直到型循环

【例2.5】计算1+2+3+…+100的结果。

求1和100之间（包括1和100）所有整数之和。

本实例的流程图可以用当型循环结构来表示，如图2.9所示。也可以用直到型循环结构来表示，如图2.10所示。

图2.9　当型循环结构求和

图2.10　直到型循环结构求和

2.2.3　N-S流程图

N-S流程图是另一种算法表示法，是由美国人I.Nassi和B.Shneiderman提出的。其根据是：既然任何算法都可以由顺序、选择和循环3种结构组成，则各基本结构之间的流程线就是多余的，因此可以去掉所有流程线，将全部的算法写在一个矩形框内。N-S图也是算法的一种结构化描述方法，同样也有3种基本结构，下面分别进行介绍。