第2章 算法——程序的灵魂

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

（1）     对数据的描述。在程序中要指定用到哪些数据以及这些数据的类型和数据的组织形式。这就是数据结构（data structure）。

（2）     对操作的描述。即要求计算机进行操作的步骤，也就是算法（algorithm）。

由著名计算机科学家沃思提出的一个公式：

算法（algorithm）+数据结构数据结构（data structure）=程序（program）

算法、数据结构、程序设计方法和语言工具是一个程序设计人员所应具备的知识。

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

程序中的操作语句，实际上是算法的体现。算法是解决“做什么”和“怎么做”的问题。

2.1 什么是算法

为解决一个问题而采取的方法和步骤，称之为“算法”。

计算机算法分为两大类：数值运算算法和非数值运算算法。

数值运算的目的是求数值解；非数值运算包括面十分广泛，常见于事务管理领域。

2.2 简单的算法举例

例：求1+2+3……+n

 1 //method 1：使用循环累加的方法求值
 2 #include <stdio.h>
 3 int main()
 4 {    
 5     int i = 0;            //循环初始量
 6     int n = 1000000;    //循环累加的次数
 7     int sum = 1;        //存放结果的变量
 8     for(i = 1; i <=n; i++)
 9     {
10         sum = sum+i;
11     }
12     printf("%d",sum);//输出打印的结果
13         return 0;
14 }

 1 //method2:使用高斯公式求和公式
 2 #include <stdio.h>
 3 int main()
 4 {    
 5     int i = 0;            //循环初始量
 6     int n = 1000000;    //循环累加的次数
 7     int sum = 1;        //存放结果的变量
 8     sum = (i+n)*n/2;    //用高斯公式求和公式的方法
 9     printf("%d",sum);//输出打印的结果
10         return 0;
11 }

通过以上两个运行时间的比较，我们就可以得知method2比method1执行的时间更短；可以推出method2的算法优于method1的算法。当然，在性能较为好的计算机上，可能差异并非那么明显。但是如果n增加到一定的大数后，差异会显示出来的，且n越大越容易看出差异。当然这是保证在数据在类型的范围内。比如int为-2^31——2^31-1,即-2147483648——2147483647之间。通过这method1和method2的比较，我们可得知method2算法优于method1算符。

2.3 算法的特性

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

（2）确定性。算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。换句话说，算法的含义应当是唯一的，而不应当产生“歧义性”。所谓“歧义性”，是指可以被理解为两种（或多种）的可能含义。

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

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

（5）有效性。算法中的每一个步骤都应当能有效地执行，并得到确定的结果。如b=0，则执行a/b是不能有效执行的。

2.4 怎样表示一个算法

2.4.1 用自然语言表示算法

自然语言就是人们日常使用的语言，可以使汉语、英语或其他语言。除了简单的问题以外，一般不用自然语言表示算法。

2.4.2 用流程图表示算法

流程图是用一些图框表示各种操作。用图形表示算法，直观形象，易于理解。流程图的符号（见图）

 

菱形框的作用是对一个给定的条件进行判断，根据给定的条件是否成立决定如何执行其后的操作。

连接点（小圆圈）适用于将在不同地方的流程线连接起来。

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

1. 传统流程图的弊端

   传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。故，使用者可以不受限制地使流程随意地转来转去，使流程图变得毫无规律，阅读室要花很大精力去追踪流程，诗人难以理解算法的逻辑。

   传统的流程图算法又称为bs型算法，意为一碗面条（a bowl of spaghetti），毫无头绪。

2. 三种基本结构

（1）顺序结构。

（2）选择结构。选择结构又称选取结构或分支结构。

（3）循环结构。又称重复结构，即反复执行某一部分的操作。

①当型（while型）循环结构。作用是：先判断条件，再根据条件是否成立，去决定是否执行操作。

②直到型（until型）循环结构。作用是：先执行操作，然后再判断条件是否成立。

以上3中基本结构，有以下的共同特点：

（1）    只有一个入口

（2）    只有一个出口

（3）    结构内的每一部分都有机会被执行到

（4）    结构内不存在“死循环”（无终止的循环）

由以上3中基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”算法。

2.4.4 用n-s流程图表示算法

在这种流程图中，完全去掉了带箭头的流程线。这种流程图又称为n-s结构化流程图，又称盒图（box diagram），通过以下n-s流程图和传统流程图结构的比较：

   

 

2.4.5 用伪代码表示算法

为了设计算法时方便，常用一种称为伪代码（pseudo code）的工具。

伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。

例：输入3个数，打印输出其中最大的数。可用如下的伪代码表示：

 1 //伪代码
 2 begin（算法开始）
 3 
 4 输入 a，b，c
 5 
 6 if a>b 则 a→max
 7 
 8 否则 b→max
 9 
10 if c>max 则 c→max
11 
12 print max
13 
14 end （算法结束）

2.4.6 用计算机语言表示算法

设计算法的目的是为了实现算法。故，不仅仅要考虑如何设计一个算法，也要考虑如何实现一个算法。若，只是设计出算法，但是该算法不易实现，则该算法无意义。

2.5 结构化程序设计方法

用3中基本结构组成的程序必然是结构化的程序。

具体说，采用以下方法保证得到结构化的程序：

（1）     自顶向下；

（2）     逐步细化；

（3）     模块化设计；

（4）     结构化编码；

重要的思想是，要使用“自顶向下，逐步细化”的思想。

划分子模块时应该注意模块的独立性，即使用一个模块完成一个功能，耦合性愈少愈好。

在设计好一个结构化的算法之后，要善于进行结构化编码（coding）。所谓编码就是讲已设计好的算法用计算机语言表示。