算法-程序的灵魂

Ø一个程序主要包括以下两方面的信息：

(1)对数据的描述。在程序中要指定用到哪些数据以及这些数据的类型和数据的组织形式

u这就是数据结构(datastructure)

(2)对操作的描述。即要求计算机进行操作的步骤

u也就是算法(algorithm)

Ø数据是操作的对象Ø操作的目的是对数据进行加工处理，以得到期望的结果Ø著名计算机科学家沃思(NikiklausWirth)提出一个公式：

算法+数据结构=程序

µ算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。

Ø广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”Ø对同一个问题，可以有不同的解题方法和步骤Ø为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法

Ø计算机算法可分为两大类别：u数值运算算法u非数值运算算法Ø数值运算的目的是求数值解Ø非数值运算包括的面十分广泛，最常见的是用于事务管理领域

下面以一个简单算法为列。

Ø一个有效算法应该具有以下特点：

(1)有穷性。一个算法应包含有限的操作步骤，而不能是无限的。

(2)确定性。算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。

(3)有零个或多个输入。所谓输入是指在执行算法时需要从外界取得必要的信息。

(4)有一个或多个输出。算法的目的是为了求解，“解”就是输出。

u没有输出的算法是没有意义的。

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

怎样表示一个算法

Ø常用的方法有：

u自然语言

u传统流程图

u结构化流程图

u伪代码……

Ø用自然语言表示通俗易懂，但文字冗长，容易出现歧义性Ø用自然语言描述包含分支和循环的算法，不很方便Ø除了很简单的问题外，一般不用自然语言。

Ø通过以上几个例子可以看出流程图是表示算法的较好的工具Ø一个流程图包括以下几部分：

(1)表示相应操作的框

(2)带箭头的流程线

(3)框内外必要的文字说明

Ø流程线不要忘记画箭头，否则难以判定各框的执行次序

三种基本结构和改进的流程图

1.传统流程图的弊端

Ø传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制Ø使用者可以毫不受限制地使流程随意地转来转去，使人难以理解算法的逻辑

三种基本结构

(1)顺序结构

(2)选择结构

(3)循环结构

①当型循环结构

②直到型循环结构

Ø以上三种基本结构，有以下共同特点：

(1)只有一个入口

(2)只有一个出口

l一个判断框有两个出口

l一个选择结构只有一个出口

(3)结构内的每一部分都有机会被执行到。也就是说，对每一个框来说，都应当有一条从入口到出口的路径通过它

(4)结构内不存在“死循环”

Ø一个结构化的算法是由一些基本结构顺序组成的

Ø在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内

Ø一个非结构化的算法可以用一个等价的结构化算法代替，其功能不变

Ø如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法