1.2　算法及其描述

在程序设计中，也经常涉及算法。瑞士著名计算机科学家Niklaus Wirth提出了程序定义的著名公式：程序=数据结构+算法。这个公式说明了程序与算法的关系，也足以说明算法在程序设计中的重要性。下面从算法的概念和描述方法两个方面讨论算法问题。

1.2.1　算法的概念

在日常生活中，做任何事情都是按照一定规则一步一步地进行的，例如，新生开学典礼就是按预设步骤一步一步进行，直到结束。这些预设步骤就是新生开学典礼的算法。

通常认为，算法就是对特定问题求解步骤的一种描述。算法应具备以下5个特点：

①有穷性。算法必须保证执行有穷步之后结束，不能无止境地执行下去。

②确定性。算法必须保证每一步必须具有确切的含义，不能有二义性。

③有效性。算法必须保证每一步操作都是可执行的。

④要有数据输入。算法中操作的对象是数据，因此，算法应该提供数据输入。

⑤要有结果输出。算法是用来解决一个给定的问题，因此，算法应该提供结果输出。

1.2.2　算法的描述方法

算法就是对特定问题求解步骤的一种描述。为了描述一个算法，可以用不同的方法。通常的方法包括自然语言、传统流程图、结构化流程图、伪代码等。

1.自然语言

自然语言就是人们日常使用的语言，可以是汉语、英语，或其他语言。

自然语言描述的算法通俗易懂，便于用户间交流。但文字冗长，含义往往不太严格，需要根据上下文才能判断其正确含义，容易出现歧义性。一般用来描述较简单的算法。

例如，求sum=1+2+…+n。算法用自然语言描述如下：

算法设计

第一步：置初值，累加和sum置0，累加项i置1。

第二步：输入待求和数的个数n。

第三步：求累加和，重复执行下面操作，直到i>n。

●　累加项：sum+i=>sum

●　求下一项：i+1=>i

第四步：输出sum的值。

2.流程图

流程图就是借助一组专用的图框和线条来描述算法，用图框表示各种操作，用线条表示操作的执行顺序。它的特点是直观形象，易于理解。美国国家标准学会（ANSI）规定了一组常用的流程图符号（见图1-1），已被世界各国所采用。

①起止框：扁圆形，表示流程图的开始或结束。

②处理框：矩形，表示各种处理功能，其内注明处理名称或简要功能。

③输入/输出框：平行四边形，表示数据的输入或输出。

④连接点：表示两部分流程图的连接处。

⑤判断框：菱形，表示判断，注明判断条件，只有一个入口，可以有多个选择出口。

⑥流程线：箭头，表示操作执行顺序。

⑦注释框：对流程图中的某些框作补充说明，帮助阅读流程图。

例如，求sum=1+2+…+n。算法用流程图描述如图1-2所示。

3.伪代码

流程图描述算法直观形象，易于理解。但画起来比较费事，在设计一个算法时，可能需要反复修改，对流程图的修改比较麻烦。流程图适合描述一个算法，但在设计算法过程中使用不太理想（因为需要反复修改）。为了设计算法时方便，常使用一种称为伪代码（Pesudo Code）的工具。

伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它如同一篇文章，自上而下地写下来，每一行（或几行）表示一个基本操作，不需使用图形符号。因此，书写方便，格式紧凑，容易理解，也便于向程序过渡。

例如，求sum=1+2+…+n。算法用类C语言的伪代码描述如下：

算法设计

上面介绍了几种常用的描述算法的方法，每种方法都有自己的特点，在程序设计中，读者可以根据需要和习惯任意选用。笔者认为，基于“自然语言+伪代码”相结合的思想是一种较好的算法描述方法，这种方法的基本思想是：算法的大框架采用自然语言描述，在重要步骤（核心步骤）中嵌入伪代码。

例如，求sum=1+2+…+n。基于“自然语言+伪代码”相结合的思想，其算法描述如下：

算法设计

第一步：输入待求和数的个数n。

第二步：置初值，将累加器sum置0，累加项i置1。

第三步：求累加和，用C语言的类while结构描述如下。

第四步：输出sum的值。