1.1 算法概念与描述

算法（Algorithm）是计算机科学与技术中一个常用的基本概念。本节简要论述算法的定义与算法的描述。

1.1.1 算法概念

在计算机科学与技术中，算法是用于描述一个可用计算机实现的问题求解方法。算法是程序设计的基础，是计算机科学的核心。计算机科学家哈雷尔在《算法学——计算的灵魂》一书中指出：“算法不仅是计算机学科的一个分支，它更是计算机科学的核心，而且可以毫不夸张地说，它和绝大多数科学、商业和技术都是相关的。”

在计算机应用的各个领域，技术人员都在使用计算机求解他们各自专业领域的课题，他们需要设计算法，编写程序，开发应用软件，所以学习算法对于越来越多的人来说变得十分必要。我们学习算法的重点就是把人类找到的求解问题的方法、步骤，以过程化、形式化、机械化的形式表示出来，以便让计算机执行，从而解决更多的实际问题。

1．算法定义

我们首先给出算法的定义。

算法是解决问题的方法或过程，是解决某一问题的运算序列，或者说算法是问题求解过程的运算描述。

在数学和计算机科学之中，算法为一个计算的具体步骤，常用于计算、数据处理和自动推理。

当面临某一问题时，需要找到用计算机解决这个问题的方法与步骤，算法就是解决这个问题的方法与步骤的描述。

2．算法的三要素

算法由操作、控制结构与数据结构三要素组成。

（1）操作

算术运算：加、减、乘、除等。

关系运算：大于、小于、等于、大于等于、小于等于、不等于等。

逻辑运算：与、或、非等。

其他操作：输入、输出、赋值等。

（2）控制结构

顺序结构：各操作按排列顺序依次执行。

选择结构：由条件是否成立来选择相应操作执行。

循环结构：重复执行某些操作，直到满足指定条件为止。

模块调用：一个模块调用另一个模块（包括自身直接或间接调用的递归结构）。

（3）数据结构

算法的处理对象是数据，数据之间的逻辑关系、数据的存储方式与处理方式就是数据结构。

常见的数据结构有：线性结构，如线性表、数组、堆栈和队列；树形结构，如树、堆；图形结构。

3．算法的基本特征

一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。

计算机按算法所描述的顺序执行算法的指令能在有限的步骤内终止：或终止于给出问题的解，或终止于指出问题对此输入数据无解。

算法是满足下列特性的指令序列。

（1）确定性

组成算法的每条指令是清晰的、无歧义的。

在算法中不允许有诸如“x/0”之类的运算，因为其结果不能确定；也不允许有“x与1或2相加”之类的运算，因这两种可能的运算应执行哪一个，并不确定。

（2）可行性

算法中的运算是能够实现的基本运算，每一种运算可在有限的时间内完成。

在算法中两个实数相加是可行的；两个实数相除，例如求2/3的值，在没有指明位数时需由无穷个十进制位表示，并不可行。

（3）有穷性

算法中每一条指令的执行次数有限，执行每条指令的时间有限。

如果算法中的循环步长为零，运算进入无限循环，这是不允许的。

（4）算法有零个或多个输入

算法所能接受的数据输入。有些输入数据需要在算法执行过程中输入，有些算法看起来没有输入，实际上输入已被嵌入算法之中。

（5）算法有一个或多个输出

输出一个或多个与输入数据有确定关系的量，是算法对数据进行运算处理的结果。

通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，其次是算法所需要的存储空间少和执行时间短等。

4．算法的重要意义

有人也许会认为：今天计算机运算速度这么快，算法还重要吗？

诚然，计算机的计算能力每年都在飞速增长，价格在不断下降。可日益先进的记录和存储手段使我们需处理的信息量也在快速增长，互联网的信息流量更在爆炸式地增长。在科学研究方面，随着研究手段的进步，数据量更是达到了前所未有的程度。例如在高能物理研究方面，很多实验每秒都能产生若干个TB的数据量，但因为处理能力和存储能力的不足，科学家不得不把绝大部分未经处理的数据舍弃。无论是三维图形、海量数据处理、机器学习、语音识别等，都需要极大的计算量。

算法并不局限于计算机和网络。在网络时代，越来越多的挑战需要靠卓越的算法来解决。如果你把计算机的发展放到数据飞速增长的大环境下考虑，你一定会发现，算法的重要性不是在日益减小，而是在日益增强。

在实际工程中我们遇到许多的高难度计算问题，有的问题在巨型计算机上采用一个劣质的算法来求解可能要几个月的时间，而且很难找到精确解。但采用一个优秀的算法，即使在普通的个人计算机上，可能只需数秒就可以解答。计算机求解一个工程问题的计算速度不仅仅与计算机的设备水平有关，更取决于求解该问题的算法设计水平的高低。世界上许多国家，从大学到研究机关都高度重视对计算机算法的研究，已将提高算法设计水平看作是一个提升国家技术竞争力的战略问题。

对同一个计算问题，不同的人会有不同的计算方法，而不同算法的计算效率、求解精度和对计算资源的需求有很大的差别。

本书具体介绍枚举、递推、递归、回溯、动态规划、贪心算法、分支限界与模拟等常用算法，介绍这些常用算法在实际案例处理与求解中的应用。最后，介绍几个算法综合应用的案例。

1.1.2 算法描述

要使计算机能完成人们预定的工作，首先必须为如何完成这些工作设计一个算法，然后再根据算法编写程序。

一个问题可以设计不同的算法来求解，同一个算法可以采用不同的形式来描述。

算法是问题的程序化解决方案。描述算法可以有多种方式，如自然语言方式、流程图方式、伪代码方式、计算机语言表示方式与表格方式等。

当一个算法使用计算机程序设计语言描述时，就是程序。

本书采用C语言与自然语言相结合的方式来描述算法。之所以采用C语言来描述算法，是因为C语言功能丰富、表达能力强、使用灵活方便、应用面广，它既能描述算法所处理的数据结构，又能描述计算过程，是目前大学阶段学习计算机程序设计的首选语言。

为方便算法描述与程序设计，下面把C语言的语法要点作简要概括。

1．标识符

标识符可由字母、数字和下划线组成，但是必须以字母或下划线开头。一个字母的大小写分别认为是两个不同的字符。

2．常量

整型常量：十进制常数、八进制常数（以0开头的数字序列）、十六进制常数（以0x开头的数字序列）。

长整型常数（在数字后加字符L或l）。

实型常量（浮点型常量）：小数形式与指数形式。

字符常量：用单引号（撇号）括起来的一个字符，可以使用转义字符。

字符串常量：用双引号括起来的字符序列。

3．表达式

（1）算术表达式

整型表达式：参加运算的运算量是整型量，结果也是整型数。

实型表达式：参加运算的运算量是实型量，运算过程中先转换成double型，结果为double型。

（2）逻辑表达式

用逻辑运算符连接的整型量，结果为一个整数（0或1），逻辑表达式可以认为是整型表达式的一种特殊形式。

（3）字位表达式

用位运算符连接的整型量，结果为整数。字位表达式也可以认为是整型表达式的一种特殊形式。

（4）强制类型转换表达式

用“（类型）”运算符使表达式的类型进行强制转换，如（float）a。

（5）逗号表达式（顺序表达式）

形式为：表达式1，表达式2, …，表达式n

顺序求出表达式1，表达式2, …，表达式n的值，结果为最后有表达式n的值。

（6）赋值表达式

将赋值号“=”右侧表达式的值赋给赋值号左边的变量，赋值表达式的值为执行赋值后被赋值的变量的值。注意，赋值号左边必须是变量，而不能是表达式。

（7）条件表达式

形式为：逻辑表达式？表达式1：表达式2

逻辑表达式的值若为非0（真），则条件表达式的值等于表达式1的值；若逻辑表达式的值为0（假），则条件表达式的值等于表达式2的值。

以上各种表达式可以包含有关的运算符，也可以是不包含任何运算符的初等量。例如，常数是算术表达式的最简单的形式。

表达式后加“; ”，即为表达式语句。

4．数据定义

对程序中用到的所有变量都需要进行定义，对数据要定义其数据类型，需要时要指定其存储类别。

（1）数据类型标识符有：

int（整型）, short（短整型）, long（长整型）, unsigned（无符号型）, char（字符型）, float （单精度实型）, double（双精度实型）, struct（结构体名）, union（共用体名）。

（2）存储类别有：

auto（自动的）, static（静态的）, register（寄存器的）, extern（外部的）。

变量定义形式：存储类别 数据类型 变量表列

如：static float x, y

5．函数定义

存储类别 数据类型 <函数名> (形参表列)

{ 函数体}

6．分支结构

（1）单分支：

if(表达式) <语句1> [ else <语句2> ]

功能：如果表达式的值为非0（真），则执行语句1；否则（为0，即假），执行语句2。所列语句可以是单个语句，也可以是用{}界定的若干个语句。

应用if嵌套可实现多分支结构。

（2）多分支：

switch(表达式)

  {case 常量表达式1:<语句1>

    case 常量表达式2:<语句2>

    …

    case 常量表达式n:<语句n>

    default:<语句n+1>

  }

功能：取表达式1时，执行语句1；取表达式2时，执行语句2; …；其他所有情形，执行语句n+1。

其中，case常量表达式的值必须互不相同。

7．循环结构

（1）while循环：

while(表达式) <语句>

功能：表达式的值为非0（条件为真），执行指定语句（可以是复合语句）。直至表达式的值为0（假）时，脱离循环。

特点：先判断，后执行。

（2）Do-while循环：

do <语句>

while（表达式）；

功能：执行指定语句，判断表达式的值非0（真），再执行语句；直到表达式的值为0（假）时，脱离循环。

特点：先执行，后判断。

（3）for循环：

for（表达式1；表达式2；表达式3）<语句>

功能：解表达式1；求表达2的值：若非0（真），则执行语句；求表达式3；再求表达式2的值；…；直至表达式2的值为0（假）时，脱离循环。

以上三种循环，若执行到break语句，提前终止循环。若执行到continue，结束本次循环，跳转下一次循环判定。

顺便指出，在不致引起误解的前提下，有时对描述的C语句进行适当简写或配合汉字标注，用以简化算法框架描述。

例如，从键盘输入整数n，按C语言的键盘输入函数应写为：

scanf("%d", &n);

框架描述时可简写为：input(n);

或简写为：输入整数n;

要输出整数量a(1), a(2), …, a(n)，按C语言的输出循环应写为：

for(k=1; k<=n; k++)

    printf("%d, ", a[k]);

框架描述时可简写为：

print(a(1)～a(n))；

或简写为：输出a(1:n)；

例1-1对两个整数m, n(m>n)最大公约数的欧几里德算法描述。

求两个整数最大公约数的欧几里德算法有着2000余年的历史。欧几里德算法依据的算法理论为如下定理：gcd(m, n)=gcd(n, mmod n)。

（1）m除以n得余数r；若r=0，则n为所求的最大公约数。

（2）若r≠0，以n为m, r为n，继续（1）。

注意到任意两个整数总存在最大公约数，上述辗转相除过程中余数逐步变小，相除过程总会结束。

欧几里德算法又称为“辗转相除”法，应用C语言具体描述如下：

// 求最大公约数欧几里德算法描述

main()

{long  m, n, c, r;

  printf("  请输入整数m, n(m>n):");

  scanf("%ld, %ld", &m, &n);              //  输入两整数

  printf(" (%ld, %ld)=", m, n);

  r=m%n;

  while(r! =0)

    {m=n; n=r;                         //  通过循环实施辗转相除操作

      r=m%n;

    }

  printf("%ld", n);                       //  输出最大公约数

}

该算法中有输入，即输入整数m, n；有操作处理，即通过条件循环实施“辗转相除”；最后有输出，即输出最大公约数n。

以上案例的算法应用C语言（有时适当予以简化）描述，缩减了从算法写成完整C程序的距离，比应用其他方法描述更加方便。