1.1 算法概述

1.1.1 什么是算法

算法研究是计算机科学的主要任务之一。利用计算机解决一个实际问题时，首先是选择一个合适的数学模型表示问题，以便抽象出问题的本质特征，其次就是寻找一种算法，作为问题的一种解法。那么什么是算法，算法有什么基本特征，算法的组成有哪些？

1. 算法的定义

算法是解题方案的准确而完整的描述，也就是解题的方法和步骤。下面举两个例子来说明算法。

例1.1　有10道数学应用题的作业，必须一道题、一道题地解答，解答每道题的过程是相同的：看题→思考→解答，然后验算检查有无错误，若没错就做下一道题；若有错，就重做。直到10道题都解答完，这次作业才算完成。解题的方法和步骤如图1-1所示。

一个学生做任何作业都可以按这个“算法”执行，每次执行都产生相应的结果，这个算法的执行者是人而不是机器。

例1.2　求任意两个整数m和n（0<m<n）的最大公约数，称为欧几里德算法，记为gcd(m, n)。

作为例子，这里用了三种方法来解决这一问题，用以阐明算法概念的以下几个要点。

（1）算法的每一个步骤都必须清晰、明确。

（2）算法所处理的输入的值域必须仔细定义。

（3）同样一种算法可以用几种不同的形式来描述。

（4）可能存在几种解决相同问题的算法。

（5）针对同一个问题的算法可能会基于完全不同的解题思路，而且解题速度也会有显著不同。

【程序1-1】欧几里德递归算法。

void swap(int &a, int &b)
    { int c;
      c=a; a=b; b=c;
    }
int rgcd(int m, int n)
    { if(m==0) return n;
      return rgcd(n%m, m);
    }
int gcd(int m, int n)
    { if (m>n) swap(m, n);
      return rgcd(m, n);
    }

【程序1-2】欧几里德迭代算法。

int gcd(int m, int n)
    { if (m==0) return n;
      if (n==0) return m;
      if (m>n) swap(m, n);
      while(m>0)
          { int c=n%m; n=m; m=c; }
      return n;
    }

【程序1-3】gcd的连续整数检测算法。

int gcd(int m, int n)
    { int t ;
      if (m==0) return n;
      if (n==0) return m;
      int t=m>n?n:m;
      while (m%t || n%t) t--;
      return t;
    }

计算机科学中讨论的算法是由计算机来执行的，也可由人模拟它用笔和纸执行。算法中最低层的操作是对用存储器实现的变量进行赋值，这样整个算法就是一个信息变换器，对任意一组给定的输入值，产生一组唯一确定的输出结果值。

对算法（Algorithm）一词给出精确的定义是很难的。算法是用计算机解决某一类特定问题的一组规则的有穷集合，或者说是对特定问题求解步骤的一种描述，它是指令的有限序列。

也可以说，算法是将输入转化为输出的一系列计算步骤，它取某些数值或数值的集合作为输入，并产生某些值或值的集合作为输出。因此，算法是将输入转化为输出的一系列计算步骤。计算机科学中，算法已经逐渐成了用计算机解决问题的精确、有效方法的代名词。

简而言之，算法就是有效求出问题的解，对问题的求解过程进行精确的描述。那么一个算法应该具有哪些基本特征呢？

2. 算法的特征

算法通常具有以下几个特征。

（1）输入（Input）

一个算法可以有零个或多个输入。这些输入是在算法开始之前给出的量，它们取自于特定对象的集合，通常体现为算法中的一组变量。如【程序1-1】中有两个输入m、n。当然，有些算法也可以没有输入，如求10以内素数的算法。

（2）输出（Output）

一个算法必须具有一个或多个输出，以反映算法对输入数据加工后的结果。这些输出是同输入有某种特定关系的量，实际上是输入的某种函数。不同取值的输入，产生不同的输出结果。没有输出的算法是没有意义的。如【程序1-1】中的输出是输入m、n的最大公约数。

（3）确定性（Definiteness）

确定性指算法中的每一个步骤都必须是有明确定义的，必须是足够清楚的、无二义性的，不允许有模棱两可的解释，确定性保证了以同样的输入多次执行一个算法时，必定产生相同的结果，否则一定是执行者出了差错。例如，b=2a，多次输入a=2，b一定为4。如【程序1-1】中的两个输入m、n一定是从正整数集合中抽取的。

（4）可行性（Effectiveness）

算法中所有的操作都必须足够基本，使算法的执行者或阅读者明确其含义以及如何执行。它们可以通过已经实现的基本运算执行有限次数来实现；每种运算至少在原理上均能由人用纸和笔在有限的时间内完成。如“增加变量x的值”或“把x和y的最大公因子赋给z”都不够明确，前者不知增加多少，后者不知如何去操作。

（5）有穷性（Finiteness）

算法的有穷性是指算法必须总能在执行有限步骤之后终止，且每一步的时间也是有限的。如果一个算法需要执行千万年，显然就失去了实用价值。如【程序1-1】对输入的任意正整数m、n，再把m除以n的余数赋值给n，从而使n值变小，如此重复进行，最终使n=0，算法终止。再如1除以3等于0.3333…，如果规定保留小数点第几位后，按照四舍五入的方法计算，就可以确定一个值，而不是无穷计算下去。

3. 算法的基本要素

一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。

（1）对数据对象的运算和操作

在一般的计算机系统中，基本的运算和操作有如下四类。

① 算术运算：主要包括加、减、乘、除等运算。

② 逻辑运算：主要包括与、或、非等运算。

③ 关系运算：主要包括大于、小于、等于、不等于等运算。

④ 数据传输：主要包括赋值、输入、输出等操作。

（2）算法的控制结构

一个算法的功能不仅取决于选用的操作，而且还与各操作之间的执行顺序有关，算法中各操作之间的执行顺序称为算法的控制结构。

一个算法一般都可以用顺序、选择、循环（当型循环或直到型循环）三种控制结构组成。如例1.1中，“看题→思考→解答”是顺序执行，“验算检查”对错是选择控制结构，对就继续执行，错则重做是循环控制结构。

4. 算法的描述工具

描述算法可以有多种方式。

（1）自然语言

自然语言就是人们日常使用的语言，可以是汉语、英语或其他语言。自然语言描述方法就是直接将设计者完成任务的思维过程用其母语描述下来。用自然语言描述算法非常接近人类的思维习惯，是一种非形式描述方法。初学者可以首先使用这种方法描述完成任务的步骤，然后再转换成其他描述。

（2）流程图

流程图是用规定的图形、流程线、文字说明表示算法的方法，是一种图形方式的描述手段。流程图可以清晰地描述出完成解题任务的方法及步骤，它是使用最早的算法描述工具。它的优点是非常直观。

（3）N-S流程图

N-S流程图是1973年提出的一种新的流程图形式，其名称来源于提出它的两位英国学者I. Nassi和B. Shneiderman。N-S流程图也是图形方式的描述手段，N-S流程图简称N-S图。

在N-S图中去掉了容易引起麻烦的流程线，不允许随意使用转移控制，全部算法都写在一个框内，框内还可以包含其他框。这种流程图适用于结构化程序设计，能清楚地显示出程序的结构，是一种结构化的流程图。

N-S图的优点是简洁，但当嵌套层数太多时，内层的方框将越画越小，从而会影响图形的清晰度。

（4）伪代码

伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法，是一种描述语言。它不用图形符号，因此比较紧凑、简洁，也比较好懂，与程序语言的形式非常接近，也容易转化为高级语言程序，是常用的算法描述方法。

伪代码只是一种描述程序执行过程的工具，是一种在程序设计过程中表达想法的非正式的符号系统，是面向读者的，不能直接用于计算机，实际使用时还需转换成某种计算机语言来表示。

无论采用何种算法描述方式，若最终要在计算机中执行，都需要转换为相应的计算机语言程序。

5. 算法与程序和数据结构的关系

（1）算法与程序

算法的概念与程序（Program）十分相似，但也有很大的不同。

算法代表了对特定问题的求解，算法是行为的说明，是一组逻辑步骤。而计算机程序则是算法用某种程序设计语言的表述，是算法在计算机上的具体实现。执行一个程序就是执行一个用计算机语言表述的算法。因此算法也常常被称为一个可行的过程。

算法在描述上一般使用半形式化的语言，而程序是用形式化的计算机语言描述的，是使用一些特殊编程语言表达的算法。算法对问题求解过程的描述可以比用程序描述粗略些，算法经过细化以后可以得到计算机程序。

一个算法可以用不同的编程语言编写出不同的程序，但它们遵循的逻辑步骤是相同的，它们都表达同样的算法，它们不是同样的程序。例如，对于同一个菜肴的制作步骤，可以分别使用英语、法语和日语写成。这是不同的三个菜谱，但是它们都表达同一个操作步骤。

程序并不都满足算法所要求的特征，例如，“操作系统”是一个在无限循环中执行的程序，不具备“有穷性”的特征，因而“操作系统”是一种程序而不是一个算法。

（2）算法与数据结构

不了解施加于数据上的算法就无法决定如何构造数据，可以说算法是数据结构的灵魂；相反地，算法的结构和选择又常常在很大程度上依赖于数据结构，数据结构则是算法的基础。算法与数据结构是密不可分的，二者缺一不可。因此有人说：“算法＋数据结构＝程序”。

1.1.2 学习算法的重要性

算法是计算机科学的基础，更是程序的基石，只有具有良好的算法基础才能成为训练有素的软件人才。对计算机类专业的学生来说，学习算法是十分必要的。因为你必须知道来自不同计算领域的重要算法，你也必须学会设计新的算法、确认其正确性并分析其效率。

随着计算机应用的日益普及，各个应用领域的研究人员和技术人员都在使用计算机求解他们各自专业领域的问题，他们需要设计算法、编写程序、开发应用软件，所以学习算法对于越来越多的人来说变得十分必要。

计算机的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用软件，都要用具体的算法来实现。因此算法设计与分析是计算机科学与技术的一个核心问题，也是一门重要的专业基础课程。

通过对算法设计与分析这门课程的学习，读者就能掌握算法设计与分析的方法，再利用这些方法去解决软件开发中所遇到的各种问题，去设计相应的算法，并对所设计的算法做出科学的评价。无论是计算机专业技术人员，还是使用计算机的其他专业技术人员，算法设计与分析都是非常重要的。