1.2 计算机问题求解的灵魂
——算法

1.2.1 算法及其特性

计算思维是运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为。它包括了涵盖计算机科学之广度的一系列思维活动。用计算思维实现问题求解，需要经过以下几个步骤。

（1）对问题进行抽象与映射，将客观世界的实际问题映射成计算空间的计算求解问题，建立解决问题的数学模型。当有多个数学模型可用时，需要对模型进行分析、归纳、假设等优化，选择最优模型。

（2）将建立的数学模型转换成计算机所理解的算法和语言，也就是将数学模型映射或分解成计算机所理解和执行的计算步骤。

（3）编写程序就是将所设计的算法翻译成计算机能理解的指令，即用某一种计算机语言描述算法（这就是计算程序）。然后通过上机实践，完成问题求解。

在这个过程中，我们始终以问题的抽象、问题的映射、问题求解算法设计等为主线展开讨论，编写程序只不过是用一种计算机语言去实施问题求解，而对数学模型进行转换所得到的算法才是计算机问题求解的灵魂。所谓算法（Algorithm），就是一组明确的、有序的、可以执行的步骤集合。算法的概念要求步骤集是有序的，这样就要求算法中的各个步骤必须拥有定义完好的、顺序执行的结构。

算法应具有4个特性：有穷性、确定性、有零个或多个输入、有一个或多个输出。有穷性是指一个算法必须保证执行有限步骤之后结束；确定性是指算法的每一步骤必须有确切的定义，算法步骤必须没有二义性，不会产生理解偏差；有零个或多个输入是指描述运算对象的初始情况，其中零个输入是指算法本身给出了初始条件；有一个或多个输出是指算法必须要有结果。

算法主要分为两类：数值运算算法和非数值运算算法。数值运算算法主要用于解决数值求解问题，例如求方程的根、求函数的定积分、求最大公约数等。非数值运算算法主要用于解决需要用逻辑推理才能解决的问题，常见的是用于事务管理领域，例如图书检索、人事管理、行车调度管理、人机围棋大战、定制服务等。

算法分析，一般应遵循以下4个原则。

（1）一个算法必须是正确的，符合计算机所要求解的题目，能得到预期的结果。

（2）求解一个问题，先分析执行算法所需要耗费的时间。

（3）求解一个问题，先分析执行算法所需要占用的存储空间。

（4）编制的算法要求条理清晰、易于理解、易于编码、易于调试。

1.2.2 算法表示方法

算法在描述上一般使用半形式化的语言，而程序是用形式化的计算机语言描述的；算法对问题求解过程的描述可以比对程序的描述略粗，算法经过细化以后可以得到计算机程序。一个计算机程序是一个算法的计算机语言表述，而执行一个程序就是执行一个用计算机语言表述的算法。在算法的表示上，常采用以下几种方式。

1. 用自然语言表示

这种方法易懂但不直观，因此除了很简单的问题外，一般不用这种方法描述。

2. 用流程图表示

如图1.1所示，这种方法采用不同的图元形状来表示“程序开始/结束”“输入/输出”“程序处理”“选择判断”“程序连接”“流程线”“注释”等程序描述要素。这种方法灵活、自由、形象、直观，可表示任何算法，但由于使用有向线来表示流程走向，因此流程图有较大的随意性。对流程图，读者要熟练掌握，会看会画。

常用的流程图制作软件有以下几款。

① Visio属于Office系列应用软件，功能全面，推荐使用。

② Raptor是一种基于流程图的可视化程序设计环境，推荐有一定编程基础的读者使用。

③ Word可以做基本的流程图，最容易上手。

例1.1 用流程图表示求解5！的算法。

问题分析与程序思路：

如图1.2所示，求解5！本质上是两个数的乘法问题。因此，需要设计一个变量 t 保存初值1，另一个变量 i 既可作为操作数递增变量，同时也可作为循环控制变量使用。变量 i 与 t 每做一次乘法运算后，变量 i 便以步长为1进行递增，继续循环计算 i 与 t 的乘法，直至 i 增长超过5后运算结束。算法所体现的思维方式就是通过将从1～5这5个数的连乘运算分解为两个数的循环乘法运算，实现了将复杂问题分解为多个具有相同运算结构的简单问题。

3. 用N-S流程图（盒图）表示

如图1.3所示，这种方法完全去掉了带箭头的流程线，算法的所有处理步骤都写在一个大的矩形框内，表示方法简单，符合结构化思想。因此，N-S流程图比传统流程图更为简洁。对N-S流程图，读者要熟练掌握。

使用图1.3所示的顺序结构、选择结构和循环结构这3种基本框，可以组成复杂的N-S流程图。图1.3中的A框或B框可以是一个简单的操作，也可以是3个基本结构之一。

优点：

① N-S图强制设计人员按结构化程序（Structured Programming，SP）设计方法进行思考并描述其设计方案。因为除了表示几种标准结构的符号外，它不再提供其他描述手段，这样就有效地保证了设计的质量，从而也保证了程序的质量。

② N-S图形象、直观，具有良好的可见度。例如循环的范围、条件语句的范围都是一目了然的，所以容易理解设计意图，为编程、复查、选择测试用例、维护都带来了方便。

③ N-S图简单、易学易用，可用于软件教育和其他方面。

缺点：

主要是手工修改比较麻烦，这是有些人不用它的主要原因。

对于例1.1，若使用N-S流程图来表示算法，如图1.4所示。

4. 用伪代码表示

伪代码用介于自然语言和计算机语言之间的文字及符号来描述算法。它如同一篇文章一样，自上而下地写下来，每一行（或几行）表示一个基本操作。它不用图形符号，因此书写方便、格式紧凑，也比较好懂和便于向计算机语言算法（即程序）过渡。这种方法适用于设计过程中需要反复修改时的流程描述。软件专业人员一般习惯使用伪代码，读者要掌握该方法。

例1.2 用伪代码表示“打印x的绝对值”的算法。

第一种表示方法：使用英文书写伪代码。

if x is positive then
    print x
else
    print -x

第二种表示方法：使用汉字书写伪代码。

若x 为正
     输出 x
否则
     输出 -x

第三种表示方法：可以混合使用中英文书写伪代码。

if x 为正
    print x
else
    print -x

若使用伪代码表示例1.1中求解5！算法，则采用以下两种方式都可以。 KDo2RrdOEB5gGtBRcllB7VFF5DMp716G965RKd1LaW2LsImSbK5mxb8d4CkbKT8T