2.1.1 算法及其表示

虽然用程序设计语言表示算法是程序设计的最终目的，但由于程序设计语言是一种形式化语言，要求严格，在初学阶段或设计比较复杂的问题时很难直接使用，因此，要了解和掌握几种直接表示算法的方法。

1.自然语言描述

采用自然语言描述算法，通俗易懂，但不太严格，烦琐冗长，不直观，不清晰。

【例2.1】 有两个存储单元a和b，要求将它们的值互换。

按存储器的性质，如果将单元a的值直接送到单元b中，那么就会覆盖b原来的内容，因此，需要借助一个临时单元c来交换。

具体算法如下。

步骤1：将单元a的值送给单元c。

步骤2：将单元b的值送给单元a。

步骤3：将单元c的值送给单元b。

【例2.2】 求1+2+3+4+…+10。

假设用存储单元S存放累加和，具体算法如下。

步骤1：把0存入S单元中。

步骤2：把1加到S中（即取S中的内容0加1后得到1，再把1送回S单元中）。

步骤3：把2加到S中。

步骤4：把3加到S中。

……

步骤10：把9加到S中。

步骤11：把10加到S中。

步骤12：把S中的结果输出。

这样的算法虽然正确，但不科学，不实用。可以设一个计数器单元n，每重复一次n增1，直到n大于10为止，求和操作可以改为“n+S送S”。修改后的算法如下：

步骤1：将0送到S中。

步骤2：将1送到n中。

步骤3：把n的值加到S中。

步骤4：n增1。

步骤5：若n≤10则转回步骤3，否则执行步骤6。

步骤6：输出S的值。

改进后的算法很科学，是适合编程的算法。

由于自然语言描述容易产生歧义，因此，除了很简单的问题外，一般不用自然语言表示算法。

2.流程图

流程图通常采用一些几何图形来代表各种类型的操作，在图形内标明文字或符号来表示操作的内容，并用箭头来表示操作的顺序。图2.1给出了流程图中使用的图形符号及代表的含义。

图2.2所示为例2.2的流程图。

用流程图表示算法，直观形象，易于理解。但由于流程图允许使用箭头随意跳转，对表示算法的层次结构非常不利，并且流程图所占的篇幅较大，作图工作量也很大。

3.N-S图

针对流程图存在的缺点，1973年，美国的计算机科学家I. Nassi和B. Shneiderman提出了结构化程序设计的流程图，因为他们二人的名字是以N和S开头的，所以称为N-S图。相对于流程图，N-S图更能体现结构化程序设计的思想，因此，本书推荐使用N-S图。

N-S图去掉了传统流程图中的箭头，全部算法写在一个大的矩形框内，组成N-S图的是一系列“方块”，因此N-S图又叫盒图。N-S图规定了一些图形元素，用来表示结构化程序设计的3种基本结构——顺序结构、选择结构、循环结构。一个算法可由若干个代表基本结构的图形元素像搭积木一样构造而成。

（1）顺序结构

顺序结构是一系列顺序执行的运算和处理。顺序结构的N-S图如图2.3所示，其中，A和B分别代表一个基本的操作。

（2）选择结构（判断结构、分支结构）

选择结构通常是根据一个条件P是否成立来选择下一步应该执行哪一种处理。图2.4所示为选择结构的N-S图，其中，T表示条件成立，F表示条件不成立。

（3）循环结构（重复结构）

循环结构根据条件P是否成立来判断是否重复执行操作A。通常有两种结构形式，一种是“先判后做”，另一种是“先做后判”。

“先判后做”称为当型循环：表示当条件P成立时就执行A，然后返回再判断P是否成立，若成立则再重复执行A，……，重复下去，直到条件P不成立。其N-S图如图2.5（a）所示。

“先做后判”称为直到型循环：表示先执行A，再判断条件P是否满足，不满足则重复执行A，……，直到条件成立。其N-S图如图2.5（b）所示。

结构化程序设计的三种基本结构具有以下共同的特点：

● 只有一个入口；

● 只有一个出口；

● 结构内的每一部分都有机会被执行到；

● 结构内不存在“死循环”。

图2.6所示为求1～10的10个正整数的和的算法描述（见例2.2），图2.7所示为求10个任意整数中的最大数的算法描述。读者可以通过这两个例子仔细体会顺序、选择和循环这三种基本结构的特点。