1.2 算法

1.2.1 算法及算法的特性

算法是对具体问题求解步骤的一种描述。做任何事情都必须事先想好执行的步骤，然后按步骤进行操作，才能避免产生错乱。对同一个问题，可以有不同的解题方法和步骤。有的方法需要的步骤很少，而有些方法需要的步骤则较多。一般来说，希望采用过程简单明了和思路清晰正确的方法。因此，为了有效地解题，一个算法应具有下列5个特性。

① 有穷性。一个算法必须在执行有限个操作步骤之后结束，且每一步都可以在有穷时间内完成。

② 确定性。算法中的每一条指令必须有确切的含义，不会产生二义性。

③ 可行性。算法中描述的操作在计算机上都是可以实现的。

④ 输入。一个算法应有零个或多个输入。

⑤ 输出。一个算法应有一个或多个输出。

1.2.2 算法的描述工具

为了使算法表达得更清晰，更容易实现算法的编写，在程序设计时通常使用专门的算法表达工具对算法进行描述。对于复杂的问题，可以先用算法表达工具对算法进行描述，再进行编程，算法的最终实现应该是计算机程序。算法的评价标准涉及很多方面，但正确性和清晰易懂性永远是一个好算法的基本条件。

计算机算法的表达工具通常有以下4种。

1．用自然语言表示算法

用自然语言表示算法就是把算法的各个步骤用人们所熟悉的自然语言依次表示出来。但要注意，用自然语言所表示的每一个操作步骤必须是计算机能够实现的。

【例1.1】 求两个整数m与n的和，用自然语言求解该问题的步骤如下。

步骤1：输入整数n和m。

步骤2：求和sum=m+n。

步骤3：输出两数之和sum。

以上3个步骤都是在计算机上可以实现的，所以是一个正确的算法描述。用自然语言表示算法，人们比较容易理解，但书写较烦琐，而且在某些场合，由于自然语言含义的不确切性，容易引起歧义，造成误解；另外对比较复杂的问题，用自然语言又难以表达准确。因此，较少采用自然语言表示复杂算法。

2．用流程图表示算法

用流程图表示算法就是用一些大家共识的专用图形符号和带有箭头的流程线来表示算法。用图形符号表示算法必须要有一组统一规定、含义确定的专用符号。表1.1所示为传统流程图所用的基本符号。图1.2所示为例1.1中求两个整数m与n之和的传统流程图算法。

可见，用流程图来表示算法，直观形象，绘制简单方便，流程清晰，各种操作一目了然，而且不会产生“二义性”。缺点是，占用面积大，由于使用流程线指出各框的执行顺序，且对流程线的方向没有任何限制，可以随意转向，往往使人弄不清楚流程的思路。

针对上述问题，1973年由美国计算机科学家 I.Nassi 和B.Shneiderman提出了结构化程序设计流程图，又称N-S流程图。N-S流程图保留了传统流程图可以形象直观地表示算法的优点，去掉了流程线，即不允许流程任意转移，只能从上到下顺序进行，算法的每一步都用一个矩形框来描述，把这些矩形框按执行的次序连接起来就是一个完整的算法。这种流程图规定了几种基本结构作为构造算法的基本单元，将在下一节中结合3种基本结构来介绍。

3．用伪代码表示算法

所谓伪代码是指用介于自然语言和程序设计语言之间的一种代码来描述算法。它的表示形式比较自由灵活，而且由于与程序设计语言比较接近，因此可以比较容易地转换成计算机程序。伪代码无统一的语法，只要自己或别人能看懂就行。

4．用程序设计语言表示算法

用自然语言和用图形符号所表示的算法有一个共同的缺点就是计算机都不能识别和执行。只有用计算机能理解和执行的程序设计语言把算法表示出来，然后把程序输入到计算机并执行，计算机才能按照预定的算法去解决问题。