全屏显示专题章节

计算机能帮助我们解决很多问题，而这些问题的解决方法就是算法。算法是一种思想。其实这个概念我们非常熟悉，那是因为从小学就开始接触算法。例如做四则运算要先乘除后加减，只要按照一定的程序一步一步做，一定不会错。至于乘法口诀、珠算口诀，更是算法的具体体现。

1）算法及其特征

算法是针对特定任务和对象而设计的，在有限步骤内求解某一问题所使用的一组定义明确的规则，是问题求解规则的一种过程化描述。通俗点说，就是计算机解题的方法与过程。

一个算法应该具有以下几个重要的特征：

（1）有穷性：一个算法必须保证执行有限步之后结束。如果一个无穷的算法并不能提交我们所需要的结果，那么这个算法将毫无意义。

（2）确切性：算法的每一步骤必须有确切的定义。这里要求算法的每个步骤都是明确的、没有歧义的，从而保证算法能安全正确地被执行。

（3）可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

（4）输入：一个算法有0个或多个输入。输入为算法指定了初始条件，当然这个初始条件并不是必需的。

（5）输出：一个算法有一个或多个输出。将输出结果提交，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。

算法的处理对象是数据，而程序的核心是算法。因此，我们应该正确的对待算法与数据之间的关系，数据的定义是算法设计的基础，数据的存储结构在某种程度上将影响算法的好坏。算法的表示有很多种，常见的有自然语言表示法、流程图表示法、N－S图表示法、伪代码表示法等。

2）结构化程序设计

结构化程序设计的思想是：自顶向下，逐步求精。将一个大的问题分解成多个可独立进行编程的小问题（模块），如果某个模块还未精细到可以直接编写的程度，则继续对它进行分解，直至能直接编程为止。其程序结构是按功能划分成若干个基本模块，这些模块形成一个层次结构。各模块之间的关系尽可能简单，在功能上相对独立，各个部分除了必要的数据交互外，彼此互不影响，相互隔离。每个模块都是由顺序、分支、循环三种基本结构组成。

程序设计本质是为了实现数据的处理，其中的数据我们可以理解为对客观事物的符号表示，即所有能输入到计算机中并被计算机程序处理的符号的总称。数据作为程序操作的对象，具有名称、类型、作用域等特征，使用前要先对这些特征加以说明。

数据名是用户通过标识符来命名的，原则上要“见名知意”。

数据类型如图3．9所示，数据类型说明了数据的性质和在内存中需占用多少存储单元。下面以C语言为例进行说明，其数据类型可以分为基本类型和构造类型。

基本整型中包括的四种数据类型所定义的变量是程序设计中经常使用到的最简单的数据，它的值是一个数值或字符。数值有精度的要求，划分为整型、实型、字符型和枚举型。例如：

声明了整型变量x、字符型变量c。

数组是一组有序数据的集合。在C语言中，数组用数组名、数组类型、数组维数和数组宽度来说明。例如：

int array［2］［3］；

声明了2行3列的二维整型数组array。

变量被声明后，系统将在内存中为其分配内存单元，指针是变量所在内存单元的首地址。例如：

int x＝1，＊p＝＆x；

声明了初始值为1的整型变量x、指向整型变量的指针变量p，p的初始值为x所在的地址编号，即指针p指向变量x。

（4）结构体类型

结构体类型是由程序员根据自己的要求自行定义的数据类型。具有结构体数据类型的变量的成员可以是基本类型、构造类型、指针类型等标准类型的数据。例如：

声明了具有xs结构的结构体变量a，a中有xh、xm、nl、bj四个成员。

作用域说明数据的使用范围。

在结构化程序设计方法中，有三种基本控制结构：顺序结构、分支结构、循环结构。

顺序结构是指语句的执行顺序和它在程序中出现的次序是一致的。如图3．10所示，我们可以看到，先执行操作（集）A，然后执行操作（集）B。

分支结构实现了把程序根据一定的条件分成不同的分支，程序只执行其中的一个分支。如图3．11所示，分支结构由一个条件判断表达式P和两个供选择的操作A和B组成。首先判断条件表达式P的值，如果P的值为真，则执行操作A，否则执行操作B。

在C语言中，分支结构的表示形式如下：

循环结构是根据一定的条件重复执行某些语句，重复重复执行执行的次数可以预先指定，也可以不指定而由循环体中的变量变化决定。如图3．12所示，循环结构由一个条件判断表达式P和操作A构成。首先判断P是否为真，如果为真则执行操作A，操作A执行结束后再来判断P，依此类推，直到P为假，则跳出循环。循环结构有多种形式，以C语言中的while语句为例，表示形式如下：

3）面向对象的程序设计

传统的结构化程序设计思想是面向任务的，主要以功能为中心，重点强调使用何种算法将问题解决。面向对象的程序设计思想与以往的各种编程语言不同处在于，它设计的出发点就是为了更直接地描述客观世界中存在的事务以及它们之间的关系。它将数据及与数据相关的操作集成一个整体，称为“对象”，而通过同类型对象抽象出其共性，称为“类”（class）。类是静态的、相对稳定的概念，而对象是动态的，是类的具体实现。

下面简单介绍一下面向对象程序设计中的几个基本概念。

面向对象方法中认为，类是具有相同属性和行为的一组事物的集合。它涵盖了属于该类的全部对象的抽象描述。类是面向对象程序设计的核心，通过类可以简化应用程序的设计。

人类在认识客观世界时经常会采用归纳、划分的思维方式，其分类依据就是对客观事物进行抽象，提取那些重要的本质特征，忽略事物的非本质特征，从而找出事物的共性。通过把具有共同性质的事物划分为一类，得出一个抽象的概念。例如：飞机、房屋、火车、空气等。

类具有继承性、多态性、封装性等特点。

继承性（inheritance）说明了子类延用父类的能力。如果父类特征发生改变，则子类将继承这些特征。在面向对象程序设计中，继承性对提高软件开发效率、实现软件复用具有重要意义。

多态性（polymorphism）主要指一些相关的类包含同名的方法程序，但方法程序的代码不完全相同。

封装性（encapsulation）是面向对象的一个重要原则，它把对象的属性和服务结合成一个独立的系统单位，并尽可能对外部隐藏对象内部细节，例如内部数据结构和代码等。

面向对象方法中的对象是系统中用来描述客观事物的具体实体，是构成系统的基本单位。对象由一组属性和行为构成。

通俗来讲，对象是基于某种类所创建的实例，它继承了类的属性、事件、方法。类是一个概念，而在这个概念的基础上明确的实例就是对象。对象可以是有形的（如飞机、房屋），也可以是无形的（如一项工程）。对象具有静态的特征，即可以用某种数据来描述；也具有动态特征，即对象所表现的行为或可以完成的功能。

属性（property）定义对象的特征或某一方面的行为。属性是用来描述对象静态特征的一系列数据，规定了对象的外观特征，如汽车的颜色、型号等特征。对象的属性一般由对象所基于的类决定，也可以由用户为对象定义新的属性。

事件（event）是由对象识别的一个动作，可以通过编写相应的代码对此动作进行响应。通常事件是由一个用户动作产生，也可以由程序代码或系统产生。

方法（mothod）是对象能够执行的一个操作，表现为完成该操作的处理代码。

在面向对象程序设计中，大多数程序代码是为对象或对象的某个事件而编写的事件处理程序代码，程序代码的执行总是由某个事件的发生而引起，即采用面向对象程序设计方法设计的应用程序，其功能的实现是由事件驱动的。

4）算法举例与算法的表示

人们经过长期的研究和开发，已经总结了一些经典的算法设计方法，比如枚举法、迭代法、递归法、回溯法等，但有些复杂问题的算法设计往往非常困难。

算法的设计一般采用由粗到细，由抽象到具体的逐步求精的方式。

算法的表示有很多种，常见的有自然语言表示法、流程图表示法、N－S图表示法、伪代码表示法等。这里我们通过流程图来表示算法，它相对比较直观。

首先介绍一下流程图中的几个基本符号。

（1）圆角矩形，表示开始或结束，如图3．13所示。

（2）矩形，表示顺序执行的代码段，如图3．14所示。

（3）带方向的箭头，称为“流程线”，标明了程序的执行方向，如图3．15所示。

（4）菱形，表示分支结构中的判断，如图3．16所示。

现在，我们通过几个例子来说明算法的设计过程。

10！＝1＊2＊3＊4＊5＊6＊7＊8＊9＊10

其本质是一个连乘操作，从1乘到10。我们可以从1＊2开始计算，那么下一个要乘上来的数字是3＝2＋1，依此类推。我们假设未知数X、S分别代表每次乘上来的数字和乘积，每次乘上来的数字为X＝X＋1，最终的S为10！。这样我们可以把10！的求解过程表示为图3．17：

具体描述如下：

②以选择法对10个数字从高到底排序

这个算法和我们平常解决数字排序的思想非常相似。首先，从10个数字中选择最大的，让它和第一个数字交换，再从剩下的9个数字中选择最大的，让它和第二个数字交换，依此类推，直到剩下的两个数字中最大的和第九个数字交换为止。具体过程如表3．1所示：

从上表我们可以看出，第一趟选择，我们比较了9次，第二趟选择比较了8次……第八趟选择比较了2次，如果有第九趟的话，将比较1次，总共的比较次数为9＋8＋7＋6＋5＋4＋3＋2＋1＝45次。

要解决这个排序问题，我们可以把这10个数字放在一个数组a［10］里，数组名为a，大小为10，每个数字的引用可以用a［i］来表示，i表示这个数字在数组中的位置号，这个号码从0开始计算。

流程如图3．18所示，我们可以通过流程图看出程序的执行过程。

用C语言描述如下：

我们先来看一个例子。

假定一个班上有50名学生，现在要按照姓名的拼音顺序排成一张表。一个最笨的算法是将50个学生所有可能的排列表都打出来，然后从中挑选出一张符合拼音顺序的表。那么，50个人的不同排列有50！种，即这样的表有50！张，大约是3×10⁶⁴张。这个数目很大，用每秒100万次的计算机不停地运算需要9．6×1048个世纪，显然是不能实施的。

也可以采用以下大家常用的算法来排。随便用一位同学的名字排在第一位。任取第二位同学的名字放在第二位，然后依拼音顺序和第一位的名字进行比较，比较后放在适当位置。第三位则需要和前两位的名字最多比较两次。依此类推，第k位最多要比较k－1次，第50位最多需要比较49次。这样，只要比较1＋2＋…＋49＝49×50／2＝1225次，就能完成排序。如果班上有n个学生，第一种算法需要运算n！（当n＞25，n！＞10n）次，第二种算法最多需要（n—1）n／2次。前者的次数随n的增加，按照10n的指数方式增加，后者则只按n的二次多项式方式增加。一般地，假如在一个问题中有n个数据需要处理，而处理的算法的计算次数依指数n方式增加，称之为“指数算法”；若按n的多项式方式增加，则称为“多项式算法”。

可以看出，不同问题可以使用不同的解决算法，我们不仅仅要考虑其正确性，还需要对这些算法进行一定的评价。算法的评价有很多方面，其中一方面是执行算法所要占用的计算机资源，我们用时间复杂度和空间复杂度来表示。

时间复杂度是执行算法过程中需要耗费的时间资源。为了便于比较同一问题的不同算法，我们可以从算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行次数作为算法的实践量度。