大学计算机基础：算法工具及设计要求

算法（Algorithm）一词最早出现在波斯数学家al—Khwarizmi所写的《印度数字算术》中。欧几里得算法（求两个整数的最大公约数）被认为是史上第一个算法。

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

1.算法的基本特性：

·输入输出，算法具有零个或多个输入，至少有一个或多个输出；

·有穷性，算法在执行有限步后能够自动结束，不会出现无限循环；

·确定性，算法的每一步都具有确定的含义，不会出现二义性；

·可行性，算法的每一步都能够通过执行有限次操作完成。

2.程序与算法的区别：

程序（program）是软件开发人员根据用户需求开发的、用程序设计语言描述的适合计算机执行的指令（语句）序列。它包括「数据结构」、「算法」、「程序设计方法」和「编程语言」。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有穷性，比如操作系统也是一种程序，它可以一直运行。

3.算法的描述工具：

首先明确一点，任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成（任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成）。

用于描述算法的工具很多，通常有流程图、N—S图、自然语言和伪代码等工具。我们以计算为例，使用不同工具描述其算法。

自然语言：带序号的人类语言描述方法。

1.将变量s清0；

2.将变量n置1；

3.把s+n的值赋给s；

4.把n+1的值赋给n；

5.判断n≤100是否成立，若成立，转3；否则转6；(www.xing528.com)

6.输出s的值。

自然语言的特点：易懂却不直观，对复杂算法描述很困难，易产生歧义。

伪代码法：是一种假的代码—不能被计算机理解，可由计算机语言和自然语言构成，见图9-3。

特点：接近某种语言编写的程序，便于转换成程序。

流程图法：采用不同的几何图形来描述算法的逻辑结构，每个几何图形表示不同性质的操作。见图9-4。符号说明见图9-5。

图9-3　伪代码

图9-4　流程图

图9-5　流程图中的符号说明

优点：直观形象

缺点：算法复杂时，篇幅较多，费时且不方便修改。

N—S图：去掉箭头流程线、算法处理步骤写在大矩形框内，框内还可包含一些小矩形框，适于结构化程序设计，见图9-6。

图9-6　N—S图

4.算法的设计要求：

·正确性，算法至少应该具有输入、输出和加工处理无歧义、能正确反映问题的需求、能够得到问题的正确答案。

·可读性，便于阅读、理解和交流。

·健壮性，输入不合法时，算法能够给出相应的处理，而不是产生错误的结果。

·高效性，算法应该尽量满足高效率和低存储的需求。