1.3 算法与算法描述

算法解决“做什么”和“怎么做”的问题，算法设计在程序设计中的地位非常重要。打个比方，厨师制作菜肴，需要有菜谱，菜谱上一般应有说明：①所用原料，指出为了做出顾客所指定的菜肴，应该使用哪些材料；②操作步骤，指出有了这些原料，应按照怎样的步骤进行加工，才能做出所需的菜肴。没有原料是无法加工成所需菜肴的，而对同一些原料可以加工出不同风味的菜肴。这里的“原料”相当于数据结构，“操作步骤”相当于算法。

本书由于篇幅所限，不可能将这些知识都详细讲解，感兴趣的读者可以深入学习相关的专业知识。本节主要对算法的有关知识做初步介绍，以便为后面各章的学习奠定一些基础。

1.3.1 算法概念

算法是指为解决某个特定问题而采取的方法和步骤。算法是根据具体问题而设计的，问题不同，所设计的算法就不同。当然，即使对于同一个问题，也可以用不同的算法加以解决。我们这里所说的算法一般是指用计算机解决问题的方法和步骤，即计算机算法。

一个算法的设计具备如下特点。

（1）有穷性。它包含两个方面：一方面是指一个算法应在有限的操作步骤内完成，另一方面是指算法操作应在有限的时间范围内完成。

（2）确定性。算法中的每一个步骤都是确定的，即不能有二义性，这样才能确保对于同一个算法，相同的输入必然得出相同的执行结果。

（3）有零个或多个输入。输入是指算法所需要的外部信息。在计算机上实现的算法，是用来处理数据对象的，在大多数情况下这些数据对象需要通过输入来得到。

（4）有一个或多个输出。算法是有目的的操作，算法的目的是为了求解，这些解只有通过输出才能得到。没有输出的算法是没有意义的。

（5）有效性。算法中的每一个步骤都应当能有效地执行，并得到确定的结果。

算法有顺序结构、选择结构和循环结构这三种基本的控制结构。

【例1-4】任意输入两个数，按降序（从大到小排列）输出到屏幕上。请给出解决问题的算法。

分析：将任意两个数按降序排列，首先要比较大小，如果前一个数小就交换并输出，否则按原顺序输出。

步骤1：将输入的任意两个数赋给两个变量。

步骤2：比较这两个变量中的数，如果前一个数小就交换，否则不交换。

步骤3：将结果输出到屏幕上。

1.3.2 算法描述

对算法的描述有自然语言、流程图、N-S图、伪代码等表示方法，下面分别进行介绍。

1. 自然语言

自然语言即人们日常生活中使用的语言。使用自然语言描述算法，通俗易懂，初学者容易掌握。【例1-4】就是采用自然语言进行的描述。然而自然语言的含义有时会模糊，易发生歧义，描述文字显得冗长。这都容易造成理解上的偏差，因而不易直接转化为程序，所以用自然语言描述算法不太合适。通常除了一些很简单的问题外，一般不用自然语言表示算法。

2. 流程图

流程图是一种被广泛使用的算法描述方法，它用一些图框和流程线来表示各种类型的操作。常见的流程图符号如图1-5所示。流程图方法形象直观，易于理解，便于发现算法出现的错误，可直观地将算法转化为程序。

图1-5　流程图符号

流程图描述的3种基本控制结构如图1-6所示。图1-6（a）为顺序结构，只有A、B两个操作步骤。图1-6（b）为选择结构，其中P为一个条件，当P成立，则执行操作A，否则执行操作B。图1-6（c）为当型循环结构，当P成立重复执行操作A，直到P不成立，循环结束。图1-6（d）为直到型循环结构，先执行操作A，然后判断P，若P不成立则重复执行操作A，直到P成立，循环结束。

图1-6　三种控制结构流程图

流程图描述法的缺点是占用篇幅较多，画流程图时既费时又不方便，若有错也不易修改。另一方面，由于流程线没有约束，可以任意转向，从而造成程序阅读和修改上的困难，不利于结构化程序的设计。

3. N-S图

随着结构化程序设计方法的出现，1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式。这种流程图完全去掉了流程线，算法的每一步都用一个矩形框来描述，把一个个矩形框按执行的次序连接起来就是一个完整的算法描述。这种流程图用两位学者名字的第一个英文字母命名，称为N-S图。用N-S图表示算法的三种基本控制结构如图1-7所示。其中图1-7（a）为顺序结构、图1-7（b）为选择结构、图1-7（c）为当型循环结构、图1-7（d）为直到型循环结构。

N-S图描述的算法在执行时只能从上到下顺序执行，从而避免了算法流程的任意转向，保证了程序的质量。N-S图的另一个优点是形象直观，结构紧凑节省篇幅，非常适合结构化程序的设计。

4. 伪代码

用流程图与N-S图表示算法直观易懂，但在设计时对其进行修改是很麻烦的，特别是当所设计的算法反复修改时。为了设计算法方便，常采用伪代码对算法进行描述。伪代码是一种近似高级语言但又不受语法约束的一种语言描述方式，它用一种介于自然语言和程序设计语言之间的文字和符号来描述算法，用一行或几行表示一个基本操作。它书写方便，格式紧凑，便于编码实现。

图1-7　三种控制结构的N-S图

【例1-5】将【例1-4】分别用流程图、N-S图和伪代码进行描述。

（1）用流程图描述的算法如图1-8（a）所示。

（2）用N-S图描述的算法如图1-8（b）所示。

图1-8　一个问题的流程图和N-S图描述

（3）用伪代码描述的算法如下。

输入任意两个数val1、val2赋给变量x与y。

val1→x
val2→y
if x<y then x→t, y→x, t→y, print x,y
else print x,y

上面介绍了常用的表示算法的几种方法，在程序设计中读者可以根据需要和习惯选用。计算机程序设计专业人员一般习惯使用伪代码表示算法。为便于理解，本书主要采用形象化的流程图和N-S图来表示算法。

1.3.3 结构化程序设计思想

1966年，C. Bohm和G. Jacopini证明了只用顺序、选择和循环这3种基本结构就能实现任何“单入口、单出口”的程序，这就是结构化程序设计的理论基础。

结构化程序设计的基本思想有如下3点。

（1）结构化编码

为了使程序具有良好的设计风格，编程时应使用以下三种控制结构进行编程。

① 顺序结构：顺序结构用来控制一个操作序列，从开始到结束顺序执行。

② 选择结构：根据条件判定的结果去执行不同分支中的语句。选择结构也称为分支结构，其为程序按不同情况自动选择步骤提供控制手段。

③ 循环结构：根据条件判定的结果决定是否重复多次执行或者一次也不执行同一组步骤。循环结构也被称为重复结构，其为程序描述重复操作提供了控制手段。

（2）结构化程序的特点

① 只有一个入口。

② 只有一个出口。

③ 不包含死循环（永远都执行不完的循环）。

④ 不包含死语句（永远也执行不到的语句）。

（3）结构化程序的分析方法

结构化程序设计对问题采取所谓的“自顶向下，逐步求精”的方法进行分析。这种分析方法是一种由抽象到具体，由复杂到简单的分析过程。在分析问题时，先按组织或功能将一个大的复杂的问题分解成几个子问题，并把这些问题划分为一个层次，如果这一层的问题仍然复杂，就对这些问题再分解，并做相应的层次划分，直到不需要分解为止。每一次分析都是自顶向下的层次划分过程，每一次分解都是对上层问题的细化求精过程，最终会形成一个树形的层次结构分析结果。

例如，开发一个程序用于统计教师所代课程的平均分、最高分数和最低分数。其层次结构如图1-9所示。

图1-9　教师所代课程统计程序的层次结构图

（4）模块化设计

在层次结构划分好之后，就开始模块化设计了。模块化设计是在结构化程序设计的概念提出以后，经过逐步完善而形成的设计方法。模块化设计采取分治策略，将一个复杂的任务划分成若干基本模块，然后再对每一个模块进行具体化，逐步细化出一个个功能独立的模块。最下层模块完成最具体的功能。每一个模块都遵循高聚合性、低耦合性的分解原则。高聚合是指一个模块只完成一项任务，功能相对独立。低耦合性是指模块间的联系越松散越好，模块间只交换那些必须的信息。依照模块化程序设计方法设计出的程序条理清晰，任务不重复、不丢失，整个程序任务连接逻辑性强，即使程序很长，也能保持程序的易读性、易维护性和正确性。

程序设计时，编程者根据要求分别完成一个或多个小模块，然后将这些模块分别测试、组装形成一个软件。

结构化程序设计思想是程序设计的重要内容，在后面的学习中读者会知道：C语言通过模块和函数两种手段来支持这种思想，C语言是一种理想的结构化程序设计的语言。