1.9 编程语言及算法

编程语言，或称计算机语言，是一个不断发展演变的概念。从开始的机器语言，到体现指令结构的汇编语言，再到各种结构化的高级语言，直至发展到支持面向对象技术的语言。

1.9.1 第一阶段：机器语言

机器语言是第一代计算机语言，计算机使用0和1组成的二进制数进行工作，二进制是计算机的语言基础，因此机器语言也被称为二进制语言。

由于是用机器语言来书写程序的，机器语言不易识别和读写，使用起来十分不方便。特别是在对程序查错纠错时，更会痛苦不堪。并且，由于每种计算机的指令系统往往不同，因此，使用机器语言编写的程序几乎没有移植性，这对程序的通用性就造成了障碍。

但机器语言的优点在于，计算机能够直接识别并快速执行，因而是所有语言中效率最高的一种语言。

一般而言，将这种用二进制机器码编写的程序叫“目标程序”。

1.9.2 第二阶段：汇编语言

为了减轻使用机器语言的痛苦，人们对它进行了有益的改进。用一些简洁的字母、符号等来代替特定的二进制指令串。比如，使用“ADD”表示加法，用“MOV”表示数据传递等。这样，人们就能轻松理解程序所进行的操作，用户阅读起来也不再是那么艰涩难懂，维护、纠错也方便一些。于是，汇编语言诞生了。

汇编语言又称符号语言，是对机器指令进行的简单符号化，它能利用计算机的所有硬件特性，并直接控制硬件。作为第二代计算机语言，汇编语言十分依赖机器硬件，它像机器指令一样，是对硬件操作的控制信息，因而属于面向机器的语言。针对计算机特定硬件编制的汇编语言程序，能准确发挥计算机硬件的功能和特长，程序精炼，代码质量高。

汇编语言的通用性不强，移植性不好，使用起来仍然烦琐费时，但其执行效率高，所以至今仍是一种常用而有力的软件开发工具。尤其在一些单片机和工业控制领域，汇编语言仍有一席之地。

1.9.3 第三阶段：高级语言

1958年首次出现了描述加工过程更为方便，且能在任何计算机上使用的第三代程序设计语言。程序设计人员可以利用这种语言直接写出各种表达式，以描述简单的计算过程，这种语言称为高级语言。

高级语言接近于数学语言或人的自然语言，同时它又不依赖于计算机硬件，输出的程序能在所有机器上通用。使用较普遍的有FORTRAN、ALGOL、COBOL、BASIC、LISP、SNOBOL、PL/1、PASCAL、C和RPOLOG等。

用高级语言编写的程序称为源程序，它不能在计算机上直接运行，必须翻译成二进制程序后才能执行。翻译的方式有两种：编译方式和解释方式。

对于程序解释，一次只读一行源程序，然后执行该行语言所指定的操作，每次运行用户程序时，必须再次解释程序。在程序的开发过程中，运用解释的方式执行程序，便于程序员对程序进行调试。

编译程序是将源程序全部翻译成目标代码（即二进制程序）后再执行，这个过程将只读取一次源程序，因此节省了大量的时间。

1.9.4 第四阶段：面向对象或面向问题的高级语言

第四代语言由第二代、第三代语言编制而成。面向对象的语言是在面向过程语言的基础上发展而来的，如C++语言就是由C语言发展而来的。

所谓“面向对象”，就是基于对象的概念，以对象为中心，以类、继承和构造机制，认识、了解、刻画客观世界，并最终开发出相应软件系统的思想方法。它把构成问题的事务分解成各个对象，建立对象的目的并不是为了完成一个步骤，而是为了描述某个事物在整个问题解决过程中的行为。面向对象程序设计语言的典型代表有C++、Visual Basic、Delphi等。

1.9.5 什么是算法

广义上的算法即解决问题的方法，就程序设计而言，算法是指计算机在求解某一问题时采用的具体方法和步骤。事实上，在日常生活中解决问题经常要用到算法，只是通常不会想到用算法这个词来形容我们思考的过程罢了。例如，乐谱是乐队指挥和演奏的算法，菜谱是厨师做菜的算法等。

在程序设计中，算法应该能够离散成若干个具体的操作步骤，而且每一个步骤都是能够用程序设计语言的语句或语句串来描述的。

例如，若要求两个整数中较大的数，其算法如下：

第1步：开始。

第2步：输入两个整数a、b。

第3步：比较a、b的大小，如果a大于b，输出a，否则输出b。

第4步：结束。

计算机解题算法分为两大类：数值运算算法和非数值运算算法。数值运算算法解决的是求数值的问题，求解过程要运用一定的求值公式，如二元一次方程的求根公式等。这类算法相对成熟。非数值运算算法涉及的内容较广，而且难以量化，一般都需要设计者参考已有的类似算法，并且针对具体问题重新设计。

1.9.6 算法的特点

通常，算法具有以下5个重要特征。

1．有穷性

一个算法应该包括有限个操作步骤，并且其中每一步都应在合理的时间段内完成。有的算法可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。执行的时间没有严格的限制，受所要处理问题的实际情况结束。

2．确定性

算法在指导计算执行每步程序时，所涉及的指令都是明确而没有任何歧义的。例如：

输出：A/正整数（A除以正整数）

该指令是无法执行的，因为正整数为一类数，既然没有指定A除以哪个正整数，那么这个步骤便是不确定的。

3．有效性

算法中的每个步骤都应该是有意义的，能够有效执行的，并且应该能够得到确定的结果。比如，开方运算的数不是能负数，分母不能为0等。

4．输入

一个算法有零个或多个输入。在某些算法中，所需要的数据可以由用户通过输入设备来输入，但有时候，也可以在编程过程中直接写明确定的运算参数，这时就不需要用户的输入了，即零输入。

5．输出

一个算法有一个或多个输出。算法的输出反映了对输入数据进行加工后的结果，没有输出的算法是毫无意义的。例如，对于求两个数的最大公约数的算法，执行程序后，若这两个数有最大公约数那么就输出这个计算结果，如果没有最大公约数则应该输出提示信息以反馈给用户。

1.9.7 算法的表示方法

一个算法可以用多种不同的方法来描述，如自然语言、流程图、伪代码、N-S图等。每种表示方法都有其优缺点，可以根据不同的需要适当地选择。

1．自然语言

用自然语言描述算法是指用文字加上一些必要的数学符号来描述解决问题的步骤。

例如，用自然语言来描述求100以内正整数的和的过程：

① 设s代表总和，n代表正整数。

② s=0,n=1.

③ s=s+n，原来的和加上一个正整数。

④ n=n+1，把下一个正整数赋给n。

⑤ 判断n是否小于100，如果是就跳转到步骤③，否则跳转到步骤⑥。

⑥ 输出s的值。

除了很简单的问题外，一般不使用自然语言表示算法。从上面的例子中我们不难发现，自然语言容易理解，也比较好掌握，但需要大量的文字来解释说明，因此并不直观。当算法中含有多分支或循环操作时，自然语言就很难将算法表述清楚。

2．流程图

流程图很好地弥补了自然语言描述算法的缺陷，它用标准的图形元素来描述算法步骤，程序结构一目了然。流程图中的基本构件如图1-22所示。

图1-23就是用流程图求闰年的算法示意图。

3．伪代码

伪代码是一种用于在算法开发过程中表达思想的非形式化的符号系统。相对于编程语言来说，其语法规则、语义结构的规定较为宽松，是一种更加直观易用的表示系统。

伪代码通常采用自然语言、数学公式和符号来描述算法的操作步骤，同时依靠计算机高级语言的控制结构来体现各步骤的执行顺序。使用伪代码的前提是必须熟悉某种程序设计语言，一般来说，软件专业人员更习惯使用伪代码。

比如求1-1/2+1/3-1/4+…+1/99-1/100的和的伪代码表示如下：

4．N-S图

N-S图又称为盒图，在使用流程图的过程中人们发现，流程线不一定是必需的，于是设计出了一种新的流程图，它把整个程序写在一个大框图内，大框图又由若干个小的基本框图构成，这种流程图简称N-S图。

在结构化程序设计中，用N-S图表示顺序结构、选择结构和循环结构的方法有所不同，具体表示如下。图1-24（a）为顺序结构N-S图；图1-24（b）为选择结构N-S图；图1-24（c）为当型循环结构N-S图；图1-24（d）为直到型循环N-S图。

求闰年的算法利用N-S图表示出来，如图1-25所示。

1.9.8 算法分析

算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。求解一个给定的可解问题，不同的人可以编写出不同的程序，分析算法可以观测出每种算法或程序更适合在什么样的环境中运行，从而对解决同一问题的不同算法进行有效性比较。

好的算法，通常可以从以下几个方面来衡量优劣。

1．正确性

正确性也称为有效性，是指算法能够满足具体问题的要求，即对任何合法的输入，算法都会得出正确的结果。确认正确的根本方法是进行形式化的证明，但对一些较复杂的问题，这是一件相当困难的事。目前形式化证明的方法尚处于初级阶段，许多计算机科学工作者正致力于这方面的研究。在实际的编程过程中，常常用测试的方法验证算法的正确性。

2．可读性

可读性指算法被理解的难易程度，人们常把算法的可读性放在比较重要的位置，主要是因为晦涩难懂的算法不易交流和推广，也难于修改、扩展和调试，而且可能隐藏较多的错误。

3．健壮性

健壮性即对非法输入的抵抗能力，它强调的是，如果输入非法数据，算法应能加以识别并做出处理，而不会产生错误动作或陷入瘫痪。

4．时间复杂度与空间复杂度

算法的时间复杂度指算法需要消耗的时间资源，即算法的运行时间。一般来说，计算机算法是问题规模n的函数f(n)，算法的时间也因此可记作：

T(n)=O(f(n))

因此，算法执行时间的增长率与函数f(n)的增长率正相关，称作渐进时间复杂度。

算法的空间复杂度是指算法需要消耗的空间资源，其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示，记作：

s(n)=O(f(n))