2.2 算法描述_零基础C语言学习笔记-QQ阅读男生中文科幻网

上QQ阅读APP看本书，新人免费读10天

设备和账号都新为新人

2.2　算法描述

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

算法描述是指解决某个特定类型的问题的具体描述。人们可以通过算法描述了解设计者的思路。常用的算法描述方法有自然语言、流程图、N-S流程图，下面分别介绍这3种算法描述方法。

2.2.1　自然语言

自然语言是指人们日常生活中使用的语言，这种表达方式通俗易懂。例如，将大象装进冰箱需要几步？答案描述如下：

（1）将冰箱门打开；

（2）将大象放进冰箱；

（3）将冰箱门关上。

以上实例的实现过程就是使用自然语言描述的。从这个实例的描述中我们发现，使用自然语言进行描述的优点是易懂，缺点是容易产生歧义。因此，在一般情况下不使用自然语言进行描述。

2.2.2　流程图

流程图是算法的图形化表示方法，它使用一些图框表示各种不同性质的操作，使用流程线指示算法的执行方向。由于流程图直观、形象、易于理解，因此应用非常广泛。

1.流程图符号

常用的流程图符号如表2.1所示。其中，起止框用于标识算法的开始和结束；判断框用于对一个给定的条件进行判断，根据该条件是否成立决定如何执行后续操作；连接点用于将不同位置的流程线连接起来。

表2.1　常用的流程图符号

下面通过实例介绍这些流程图符号的使用方法。例如，用流程图表示将大象装进冰箱的实现过程，如图2.4所示。

图2.4　将大象装进冰箱的流程图

2.3种基本结构

1966年，计算机科学家Bohm和Jacopini为了提高算法的质量，经过研究提出了3种基本结构，分别为顺序结构、选择结构和循环结构。任何算法都可以由这3种基本结构组成，可以并列，可以相互包含，但不允许交叉，不允许从一个基本结构直接转到另一个基本结构的内部。

1）顺序结构。

顺序结构是简单的线性结构。在顺序结构程序中，各操作是按照它们出现的先后顺序执行的。顺序结构的流程图如图2.5所示。

图2.5　顺序结构的流程图

在执行完A语句后，继续执行B语句。在这个结构中只有一个入口点A和一个出口点B。

2）选择结构。

选择结构又称为分支结构。在选择结构的流程图中必须包含一个判断框，如图2.6和图2.7所示。

图2.6　选择结构的流程图1

图2.7　选择结构的流程图2

图2.6中的选择结构，首先判断给定的条件P是否成立，如果成立，则执行A语句，否则执行B语句。

图2.7中的选择结构，首先判断给定的条件P是否成立，如果成立，则执行A语句，否则什么也不做。

3）循环结构。

在循环结构中，程序会反复地执行一系列操作，直到条件不成立，才终止循环。根据判断条件的位置，将循环结构分为当型循环结构和直到型循环结构。

当型循环结构的流程图如图2.8所示。在当型循环结构的流程图中，首先判断条件P是否成立，如果成立，则执行A语句；在执行完A语句后，再次判断条件P是否成立，如果成立，则再次执行A语句；如此反复，直到条件P不成立，此时不再执行A语句，跳出循环。

直到型循环结构的流程图如图2.9所示。在直到型循环结构的流程图中，首先执行A语句，然后判断条件P是否成立，如果条件P成立，则再次执行A语句；然后再次判断条件P是否成立，如果成立，则再次执行A语句；如此反复，直到条件P不成立，此时不再执行A语句，跳出循环。

图2.8　当型循环结构的流程图

图2.9　直到型循环结构的流程图

2.2.3　N-S流程图

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

1.顺序结构

顺序结构的N-S流程图如图2.10所示。例如，将大象装进冰箱，用N-S流程图表达的效果如图2.11所示。