1.2 算法的概念及其描述方法

在我们进行程序设计的过程中，不管选用哪种程序设计语言，编程者都要在程序中详细地说明想让计算机做什么以及如何做，即正确地描述出程序实现的算法，本节我们首先简要介绍一下算法的概念及描述方法。

1.2.1 算法的概念

要用计算机解决一个实际问题，首先应进行程序设计，而程序设计主要包括对数据以及处理问题的方法和步骤的完整而准确的描述。所谓对数据的描述，就是指明在程序中要用到的数据类型和数据组织形式，即数据结构；对问题的方法和步骤的描述，即计算机进行操作的步骤，也就是所采用的算法。

一个算法就是一个有穷规则的集合，其中的规则规定了解决某个特定类型的问题的运算序列。简单地说，任何解决问题的过程都是由一定的步骤组成的，我们把解决问题的方法和有限的步骤称为算法。

算法分为数值运算算法和非数值运算算法两种。数值运算算法是指对问题的数值求解，例如，对微分方程求解，对一元二次方程求解等；非数值运算算法包括非常广泛的领域，如信息检索、事务管理、数据处理等。数值运算有确定的数学模型，一般都有比较成熟的算法。许多常用的算法都已经被编写成通用程序或标准库，例如，数学程序库、数学软件包等，需要时可以直接调用。然而，非数值运算的种类繁多，要求不一，很难形成规范的算法，需要用户按不同要求进行设计。

那么如何衡量算法的正确性呢？一般可用如下五个基本特性来衡量：

1）有穷性。一个算法必须在执行有限步骤之后结束，即一个算法必须包含有限的操作步骤，而不是无限地执行下去。

2）确定性。算法的每一个步骤都应当是确定的、无二义性的，而不应当是含糊的、模棱两可的。所谓确定是指算法应当满足具体问题的要求，对于一切合法的输入都能产生满足规格说明要求的结果。

3）可行性。算法的每一步都是能够实现的，即可操作的，并得到确定的结果。这也称为算法的有效性。

4）允许没有输入或者有多个输入。所谓输入是指在执行算法时，计算机需要从外界获得的必要信息。有些算法不需要从外界输入数据，而有些算法则需要输入数据。

5）必须有一个或多个输出。算法的目的是求解，“解”就是输出。一个算法可以有一个或若干个输出，没有输出的算法是没有意义的。

一般来说，应该考虑采用方法简单、运算步骤少、占用计算机存储空间小的算法。也就是说，为了有效地进行解题，不仅需要保证算法的正确性，还要考虑算法的质量。

1.2.2 算法的描述方法

为了表示一个算法，可以使用不同的算法描述方法。

1.自然语言

所谓自然语言，就是人们日常使用的语言。可以使用汉语、英语或其他语言来描述算法。例如，用自然语言描述求n！的算法。如果n=5，即求1×2×3×4×5。假设s代表累乘之积，t代表乘数，那么自然语言表示的n！的算法为：

步骤1：使s=1，t=1；

步骤2：使s×t，得到的乘积放在s中；

步骤3：使t的值加1；

步骤4：如果t≤n，则返回步骤2，重新执行；否则，循环结束，此时，s中的值就是n!，输出s。

用自然语言描述算法通俗易懂，比较符合人们的日常思维习惯，但描述文字比较烦琐、冗长，容易产生歧义，难以清楚地表达算法的逻辑流程。因此，一般用自然语言描述较为简单的算法。

2.流程图

流程图是用一些几何图形、线条以及文字说明来描述算法的逻辑结构。该方法形象、简明直观、易于理解、便于交流。ANSI规定了一些常用的流程图符号，如图1-1所示。

传统流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受限制地使流程随意转向，这往往会使流程图变得毫无规律，难以阅读、修改，使算法的可靠性和可维护性难以得到保证。图1-2是用传统流程图表示的程序的三种基本结构。

N-S流程图是由美国学者I. Nassi和B. Shneiderman提出的表示算法的图形工具，用于简化控制流向。该表示方法的基本单元是矩形框，用不同的形状线作为分割。流程图中只有一个入口、一个出口，没有流程线。N-S流程图的优点是比文字描述直观、形象、易于理解，比传统流程图紧凑、易画。尤其是它废除了流程线，避免了流程任意转向，增加了可读性。图1-3是用N-S流程图表示的程序的三种基本结构。

3.伪代码

伪代码是介于自然语言和计算机语言之间的一种用文字和符号来描述算法的工具。伪代码并不对应于某种计算机语言，而是一种类似计算机语言的代码。这种伪代码表示方法不能被计算机所理解，但接近于用某种语言编写的程序，便于转换成计算机程序。

1.2.3 程序的基本控制结构

结构化程序设计的三种基本程序控制结构是顺序结构、选择结构和循环结构。各种程序设计语言一般都具有这三种结构，但是它们的表示形式有所差异。已经证明，由三种基本结构表示的算法，可以解决大多数复杂的问题。

（1）顺序结构

顺序结构是一种最简单的程序结构，程序是依据语句书写的先后顺序依次执行的，即程序执行了语句1后才能执行语句2。顺序结构形式的流程图如图1-2a所示。

（2）选择结构

选择结构也称为分支结构，此结构必须包含一个条件判断框，根据条件判断结果决定程序执行的顺序，这种结构形式的流程图如图1-2b所示。当“条件”为“真”（成立）时，执行语句块1；当“条件”为“假”（不成立）时，执行语句块2。

（3）循环结构

循环结构也称为重复结构，通常用来重复执行某些操作语句。用计算机实现反复做某项工作是通过使用循环结构来完成的。循环结构是先判断循环条件，若条件成立，则执行循环体，如图1-2c所示。此结构表示当给定的条件成立时，反复执行循环体，直到条件不成立时，跳出循环。

三种程序基本结构的N-S流程图如图1-3所示，其中图1-3a表示顺序结构，图1-3b表示选择结构，图1-3c表示循环结构。