第 4章 算法
当我们试图用计算机解决一个问题时，大
体都要经历如下几个步骤,
1,把问题抽象为一个带有一般性的数学问题，即数
学化。这一步要引入一些数学概念，给出所求问题
的已知条件、所要求的结果、以及在已知条件和所
要求的结果之间存在着的隐式或显式的联系。
2,建立相应的求解方法。这一步要给出问题的求解模型，
即确定问题的数据模型并在此模型上定义一组运算，
然后借助于对这组运算的调用和控制，根据已知数
据导出所要求的结果。
3,用一种程序设计语言描述算法。即将非形式自然语
言表达的算法转变为一种程序设计语言表达的算法。
也可称做程序设计或程序编制。
4,编辑、调试和测试程序代码，直到输出所要求的
结果。
? 获得了计算方法和算法，并不等于问题可解，
是否可解取决于算法的存在性和计算的复杂性。
即是否存在求解算法，算法所需要的时间和空
间在数量级上能否被接受。
? 1900年，数学家希尔伯特在巴黎举行的世界数
学家大会上发表了至今仍著名的演说。在演说
中，他提出了 23个数学问题，这就是著名的
,希尔伯特 23个问题,,并认为它们是对下一
个世纪的挑战。其中的第 10个问题是, 丢番图
方程的可解性问题, 。其具体涵义是设计一个
算法来测试多项式是否有整数根。将该问题做
相应简化可以设,
D={p|p是有整数根的 x的多项式 },则集合 D是否
可判定？ 答案是否定的 。
我们可以把多项式输入到计算机中进行处理，当
x赋值为 0,-1,1,-2,2,-3,3,…… 时，分
别求出多项式的值，一旦求得 0值，就接受，如
果 p没有整数根，则程序将永远运行下去 。
本章内容
? 4.1 算法的概念
? 4.2 算法的表示
? 4.3 常用算法介绍
? 4.4 并行算法
? 4.5 算法的评价
? 4.6 算法的设计要求
4.1.1 算法的定义
? 算法是程序设计的精髓，程序设计的实质就是
构造解决问题的算法，将其解释为计算机语言。
? 有关算法 (algorithm)的定义不只一种，其中
一种叙述为：算法是对特定问题求解步骤的一
种描述，它是指令的有限序列，其中每一条指
令表示一个或多个操作。
曾获图灵奖的著名科学家克努斯 （ D.Knuth）
对算法这一概念给出了进一步的描述 。
? 一个算法，就是一个有穷规则的集合，其中
之规则确定了一个解决某一特定类型问题的
运算序列。此外，算法的规则序列必须满足
下列五个重要条件,
（ 1） 有穷性 。 算法必须总是在执行有穷步之后结束；
（ 2） 确定性 。 算法的每一步骤必须被确切地定义；
（ 3） 输入 。 算法有零个或多个输入；
（ 4） 输出 。 算法有一个或多个输出；
（ 5）能行性。算法中有待执行的运算和操作必须是相当
基本的，即它们原则上都是能够精确地进行的，而且
用笔和纸做有穷次就可以完成。
除了算法的非形式化定义外，还有算法的形式化定义,
算法是一个四元组，即（ Q,I,O,F）。
其中,
1 Q 是一个包含子集 I 和的集合它表示计算的状态 。
2 I 表示计算的输入集合；
3 O 表示计算的输出集合；
4 F 表示计算的规则，它是一个由 Q 到它自身的函数，且
具有自反性，即对于任何一个元素 q∈ Q,有 F(q)=q 。
4.1.2 性质
在 4.1.1中我们曾介绍了克努斯给出的算
法定义,其中包括算法成立的五个重要条
件,实际上就是算法的规则序列必须满足
的五个特性 。
例 1 给定两个整数 m和 n，试写出它们的最大公因
子的算法。
其算法如下,
1,读入两个正整数 m和 n（设 m>n）。
2,求 m和 n的余数 r。
3,用 n的值取代 m，用 r的值取代 n。
4,判断 r的值是否为零，如果 r=0，则 m为最大公
因子，否则返回 2
5,输出 m的值。
? 我们可以看到，无论给出多大的两个数，这个
算法都会在执行一定次数之后结束。这是算法
的有穷性要求：, 算法必须总是（对任何合法
的输入值）在执行有穷步之后结束，且每一步
都可在有穷时间内完成, 。
? 给出的数值必须是确定的，不能出现诸如
,比 m大一些或比 n小一点儿, 之类的无法确
定数值的表达方式。这是算法的确定性要求：
算法中每一条指令必须被确切地定义，读者
理解时不会产生二义性。
? 算法一定是可操作的，当我们用笔和纸代替
计算机去完成计算过程时,是可以做到的。这
是算法的可行性要求：即算法中描述的操作
都是可以通过有限次的基本运算执行来实现
的。
? 一个算法有零个或多个的输入。在上述的例
子中共有两个已知变量,m和 n,否则算法将无
法执行下去,这是算法的输入要求。
? 算法必须给出结果，在本例中，结果为 m和 n
的最大公因子。这是算法的输出要求：一个
算法有一个或多个的输出，这些输出是与输
入有着某些特定关系的量。
4.2 算法的表示
? 算法不能直接被计算机执行，使用它的
目的就是把你的思想表达出来。可以使
用专门的工具进行描述。常用的描述工
具有：自然语言、流程图、决策表及算
法描述语言等。
? 关于最大公因子的描述方法使用的就是
自然语言，即人们 日常交流所用的语言
进行描述。
1 自然语言的歧义性容易导致算法执行的不
确定性；
2 自然语言的语句一般太长从而导致了所描
述的算法太长；
3 由于自然语言表示的串行性,因此当一个算
法中循环和分支较多时就很难清晰地表示出
来；
4 自然语言表示的算法不能直接被计算机接
受。
由于自然语言具有二义性和不确定性而难以严
格表示算法的逻辑流程，因此一般不用自然语
言描述算法。
? 流程图是用一种图形工具描述算法或程序结
构。 流程图是描述算法的常用工具，它采用
美国国家标准化协会 ANSI （ American
National Standard Institute） 规定的一
组图形符号来表示。 算法流程图可以很方便
地表示顺序选择和循环结构，而任何程序的
逻辑结构都可以用顺序选择和循环结构来表
示，因此流程图可以表示任何程序的逻辑结
构。
例如，用矩形表示处理，用菱形表示判断，用
平行四边形输入 /输出，用带箭头的折线表示
流程等等。
将例 1用流程图表示如下,
begin
end
write m
read m,n
n=r
m=n
r=mod(m,n)
r=0
T
F
从上例中我们看到, 只要掌握了流程图
中各种符号所代表的含义, 即可以知道
要完成的操作 。 下面让我们再看一个例
子,
例 2 求解 1到 100的和的算法流程图
开始
结束
X=X+Y
Y=Y+1
Y=2
X=1
Y>100
write x
T
F
? 决策表又称为判断表，它列出了对于所
有可能的条件应采取的动作。适用于描
述一个复杂的判断过程。
? 算法描述语言是一种把自然语言与程序
设计语言相结合起来的算法描述工具。
保留了程序设计语言严谨的结构、语句
的形式和控制成分，忽略了繁琐的变量
说明。
例１的算法描述语言,
PROCDURE Euclid’s algorithm；
BEGIN
READ（ m,n） ;
REPEAT;
r:=mod(m,n);
m:=n;
n:=r;
UNTIL r=0;
WRITE (m)
END
? 上面的这种描述示方法与计算机程序
非常相似，但又不是正式的程序，需
要进一步加工才能在计算机中实现。
例 1演示
例 3 给出小于 100的斐波那契数的算法描述 。
首先，我们给出斐波那契数列（, 兔子问
题, ）, 0,1,1,2,3,5,8, 13,
21,34,…
假设一对刚出生的兔子一个月后就能长大，
再过一个月就能生下一对兔子，并且此后每
个月都能生一对兔子，且新生的兔子在第二
个月后，也是每个月生一对兔子。问一对兔
子一年内可繁殖成多少对兔子？
其算法可描述如下,
PROCEDURE Fibonacci;
BEGIN
n1:=0;
n2:=1;
n3:=0;
WRITE (n1,n2);
WHILE n3<100 DO
BEGIN
n3:=n1+n2;
WRITE(n3);
n1:=n2;
n2:=n3;
END
END
例 3演示
? 算法是供人来阅读的，必须牢记这一点。算
法中语句的书写格式采用缩进规则，保留字
用大写，其余标识符小写，以提高算法的易
读性。
4.3 常用算法介绍
? 算法包括数值计算算法和非数值计算算
法两类，后者尤为重要。关于算法的概
念及应用，更深入的内容将在算法设计
与分析等课程中学习。在此简单介绍分
治法、递归法、迭代法等。
4.3.1递归
? 所谓递归是指：一个过程用自身的简单情况来
定义自身，再自己调用自己则称它们是递归的，
或者是递归定义的。
递归是一种强有力的数学工具，它可使问
题的描述和求解变得简洁和清晰。递归算法常
常比非递归算法更易设计，尤其是当问题本身
或所涉及的数据结构是递归定义的时候，使用
递归算法特别合适。
例 1 非负整数 n的阶乘可递归定义为,
n!=
1 n=0
n*(n-1) n=0
? 递归算法的设计步骤
第一步骤（递归步骤）：将规模较大的原问
题分解为一个或多个规模更小、但具有类似
于原问题特性的子问题。即较大的问题递归
地用较小的子问题来描述，解原问题的方法
同样可用来解这些子问题。
第二步骤：确定一个或多个无须分解、可直
接 求解的最小子问题（称为递归的终止
条件）。
例 2 函数 f(n)可递归定义为,
f(n)=
n*f(n－ 1) (n>0)
1 (n=0)
（ 1）递归边界条件。也就是所描述问题的最简
单情况，它本身不再使用递归的定义。如上例，
当 n=0时,f(n)=1，不使用 f(n-1)来定义。
（ 2）递归定义：使问题向边界条件转化的规则。
递归定义必须能使问题越来越简单。 如上例：
f(n)由 f(n-1)定义，越来越靠近 f(0),也即边界条
件。最简单的情况是,f(0)=1。
裴波那契数的形式化定义, f(n)=f(n-1)+f(n-
2); f(0)=1; f(1)=2。事实上，这种定义方法
就是递归。它所对应的递归程序为,
Function fib(n, integer), integer;
Begin
If n = 0 then fib,= 1 { 递归边界 }
Else if n = 1 then fib,= 2
Else fib,= fib(n-2) + fib(n-1) { 递归 }
End;
? 递归算法能使一个蕴含递归关系且结构
复杂的程序简捷精炼,增加可读性。特
别是在难于找到从边界到解的全过程的
情况下,如果把问题推进一步，没有结
果仍维持原问题的关系,则采用递归算
法编程比较合适 。
用递归算法解决汉诺塔问题。假设有三
个塔,每个塔都堆放 n 个盘子。开始
时,所有盘子均在塔 A上,并且,盘从上
到下,按直径增大的次序放置。此题目
的目的是设计一个盘子移动的序列，使
得塔 A 上的所有盘子借助于塔 B 移动
到塔 C 上。
其中, 有两个限制条件, 1,一次只能搬动一
个盘子 。 2,任何时候不能把盘子放在比它小
的盘子的上面 。
第 1步, 把 n-1 个盘子从塔 A 搬到塔 B。
第 2步, 将剩下的一只盘 (也就是最大的一只 )
直接从 A 塔搬到那个仍然空着的塔 C 。
第 3步：用第一步描述的方法,再次将 B
塔上的盘搬到 C 塔。操作方法和第一步一
样,但这一步实际上是由 n-1的盘子组成。
这一步是没有问题的,因为塔 C上仅有的一只
盘是最大的。
算法演示
main() /* 读入要搬动的盘的个数 */
{
int disks; /*定义变量 disks，用于存放盘的个数 */
void towers(int,char,char,char); /*函数 tower()声明
*/
printf("Number of disks,");
scanf("%d",&disks); /*输入盘的数目 */
towers(disks,'A','B','C'); /*调用函数
towers() 用于完成递归算法 */
}
void move_disk(char src,char dst)
{
printf("%c ====> %c",src,dst);
}
void towers(int n,char src,char mid,char dst)
{
void move_disk(char,char);
if (n==1)
{
move_disk(src,dst);/*调用函数 move_disk（）打印盘从一个
塔到另一个塔的搬动过程 */
return;
}
towers(n-1,src,dst,mid);
move_disk(src,dst);
towers(n-1,mid,src,dst);
}
4.3.2 迭代
? 迭代法是一种逐次逼近法。迭代一词按
其字面解释,,迭, 代表屡次和反复的
意思,,代, 表示替换的意思，合起来
迭代就是反复替换的意思。在程序设计
中为了处理重复性计算的问题，最常用
的方法就是迭代方法。主要是循环迭代。
? 迭代与递归有着密切的联系，甚至前面提到
的 X0=a,Xn+1=f(n)的递归关系也可以看作是
数列的一个迭代关系，可以证明迭代程序都
可以转换为与它等价的递归程序，反之则不
然，就效率而言，递归程序的实现要比迭代
程序的实现耗费更多的时间和空间，因此在
具体实现时又希望尽可能将递归程序转化为
等价的迭代程序。
有的问题既可以用递归，也可以用迭代
方法完成，但并非全部，像汉诺塔问题
只能用递归方法实现，不能用迭代方法
解决。
用迭代方法求解 斐波那契数 问题的自然语言描
述如下,
1） 如果 n=0,那么将 0 赋值给 Y,并输出 Y，
转步骤 11，否则继续执行；
2） 将 0 赋给 X, 将 1 赋值给 Y；
3） 输出 X,Y；
4） 将 1 赋值给 I；
5） 如果 I 大于 n-1,则转到步骤 11，否则
继续执行；
6)将 X 和 Y 的和赋值给 Z；
7） 将 Y 赋值给 X；
8） 将 Z 赋值给 Y；
9） 将 Y 输出；
10) 将 I 加 1，转步骤 5 继续执行；
11) 算法结束。
4.3.3 分治法
? 分治法的设计思想是将一个难以直接解决的
大问题，分割成一些规模较小的相同问题，
以便各个击破，含, 分而治之, 之意。
? 如果原问题可分割成 k个子问题,1<k≤n,且
这些子问题都可解，并可利用这些子问题的
解求出原问题的解，那么这种分治法就是可
行的。
? 由分治法产生的子问题往往是原问题的较小
模式，这就为使用 递归技术 提供了方便。在
这种情况下，反复应用分治手段，可以使子
问题与原问题类型一致而其规模却不断缩小，
最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。分治与递归像
一对孪生兄弟，经常同时应用在算法设计之
中，并由此产生许多高效算法。
例如，求 n个元素集合 S的最大元素和最小元
素问题。可以把 S分成大小相等的两个子集 S1
和 S2，递归的求出 S1及 S2的最大元素和最小
元素。只要从两个最大元素中选出一个较大
的，从两个最小元素中选出一个较小的，则
它们分别是 S的最大元素和最小元素。
后续将要介绍的二分查找法，也运用了分治法
的思想。例如，给定一排好序的整型序列，查
找元素 x是否在该序列中。这时，需将待查元
素与 中值元素 进行比较，即把一个长度为 n的
有序表分成两个长度小于等于 n/2的有序段，
依次进行查找，如果查找不成功，则需查找剩
下的另一段。
4.4 并行算法
? 并行算法是指一次可执行多个操作的算法。对
并行算法的研究现在已发展为一个独立的研究
领域。很多用串行算法解决的问题也已经有了
相应的并行算法。
这里介绍的并行算法将用一种流行的理论模
型即并行随机存取计算机 (PRAM)来描述。因
为很多关于数据结构的概念，如数组、表、
树和图的并行算法都可以很容易地用 PRAM
模型来描述，所以，这里对 PRAM模型做一
简单介绍。
1,PRAM模型
图 4.3说明了 PRAM的基本结构。其中有 n个普
通的串行处理器 p0,p1,...,pn-1共享一个全局
存储器。所有处理器都可以, 并行地, (同时 )
从全局存储器读出信息或向全局存储器写入
信息。各处理器也可以并行地执行各种算术
和逻辑操作。
P0
Shared
memory
P1
P2
Pn1
..,
..,
? 并行算法的运行时间既依赖于执行算法的处理
器数目，也依赖于输入问题本身的规模。一般
来说，在分析 PRAM算法时我们必须同时讨论
其时间和处理器数目，这与串行算法完全不同，
在串行算法中我们主要集中于对时间的分析。
? 并发存储器存取方式与互斥存储器存取方式
并发读算法是指在算法执行过程中多处理器
可以同时对共享存储器的同一位置进行读操
作的一种 PRAM算法。互斥读算法是指在算
法执行中任何两个处理器都不能同时对共享
存储器的同一位置进行读操作的一种 PRAM
算法。
? EREW：互斥读且互斥写
? CREW：并发读且互斥写
? ERCW：互斥读且并发写
? CRCW：并发读且并发写
? 同步与控制
PRAM算法必须高度同步以保证其正确执
行。如何获得这一同步特征？另外，
PRAM算法中的处理器常常必须测试循环
的终止条件，而这一终止条件又往往取决
于所有处理器的状态。如何实现这种控制
功能？
许多并行计算机采用了一种连接各处理器的
控制网络，以帮助实现同步和对终止条件进
行测试。在特定情况下，控制网络实现这些
功能的速度可以与路径选择网络实现对全局
存储语句的速度一样快。
为方便起见，我们假设各个处理器都有严格
同步的特征。所有处理器同时执行相同的语
句。处理器执行代码的进度也保持一致。
4.5 算法的评价
? 对算法的研究，第一步是设计算法，第二
步是复杂性分析。对同一问题，若有两种
不同的算法，两种算法的优劣要根据复杂
性分析的结果来判断。一般认为需要的时
间较短，存取单元较少的算法是较好的。
4.5.1 算法的时间复杂度
? 算法的时间复杂度（ Time Complexity）
是依据算法编制成程序后在计算机中运
行时所耗费的时间的大小来决定的。一
个程序在计算机上运行时所耗费的时间
取决于程序运行时输入的数据量、对源
程序编译所需要的时间、执行每条指令
所需的时间以及程序中语句执行的次数。
其中一个最重要的指数是程序中语句重
复执行的次数。
? 算法的时间复杂度 T(n)实际上是表示当
问题的规模 n充分大时该程序所占用时间
的一个数量级。例如，若某程序运行时
的时间复杂度为 T(n)=2n3+3n2+2n+1,则表
明程序运行所需要的时间与 n3成正比。
引入符号,O”,则有 T（ n） =O(n3)。
4.5.2 算法的空间复杂度
例 1,在三个整数中求最大值。其中，算法（一）如下,
max(int a,int b,int c) /*给出三个整数 */
{ if (a>b) /*如果 a>b*/
{ if(a>c) return a; /*如果 a>c，返回 a*/
else return c; /*否则返回 c*/
}
else
{ if(b>c) return b; /*如果 b>c，则返回 b*/
else return c; /*否则返回 c*/
}/*运算过程无需额外存储空间，只需两次比较 */
算法（二）如下,
max(int a[3])
{ int c,int i;
c=a[0];
for(i=1;i<3;i++)
if (a[i]>c) c=a[i];
return c;
} /*需要两个额外的存储空间，两次比较，至少一次
赋值，共需 5个整型数空间 */
当用算法（一）实现求 100个整数中的最大值时，算法
几乎是无法描述的，但算法（二）只要稍做改动即可。
max(int a[100])
{ int c,int i;
c=a[0];
for(i=1;i<100;i++)
if (a[i]>c) c=a[i];
return c;
} /*共需 102个整型数空间 */
例 1(二 )
? 算法的空间复杂度 (Space Complexity)是指
依据算法编制成程序后在计算机中运行时所
占用的空间的大小。一个程序在计算机上运
行所占用的空间同样也是 n的一个函数，称为
算法的空间复杂度，记为 S（ n）。如果
S(n)=O(n2)，表示运行时所占用的空间与 n2
成正比。
4.5.3 算法的易理解性
? 一个算法如果难以理解，将给应用和评价带来
一定的困难，易理解性是衡量一个算法优劣的
重要标准。因为给出算法的目的是让别人能读
懂，理解并编写相应的程序进行维护和修改。
因此，具有良好的结构、易理解、易维护的算
法是人们追求的目标。
4.6 算法设计的要求
1 正确
算法应当满足具体问题的需求。正确性
是设计和评价一个算法的首要条件。如果
一个算法不正确，其他方面就无从谈起。
一个正确的算法是指在合法的数据输入情
况下，能在有限的运行时间内得出正确的
结果。选用或设计的算法首先应该保证是
正确的。
2 可读
算法最主要目的是为了阅读与交流，并将它
转换成可实现的程序在计算机中执行。可读
性好不仅有助于人们对算法的理解，而且也
有利于程序的调试与修改。在保证算法正确
的前提下，应十分强调算法的可读性。
3 健壮
健壮是指算法对各种可能的情形都考虑的
非常完善。当输入数据非法时，算法也能
适当地作出反应或进行处理。而不会发生
异常或输出莫名期妙的结果。例如，输入
三角形的三条边长时，若其二边之和小于
另一条边，则算法执行中应输出相应的通
告信息而不是发生异常。
4 高效
它是指算法的执行效率要高。算法的效率包
括时间效率与空间两个方面。时间效率是指
算法的执行所需要的时间，而空间效率是指
执行该算法所需的存储量。对应同一个问题
和同一问题的规模，若采用不同的算法进行
处理，其执行的效率就可能不相同。对于一
种算法来说，如果执行的时间越短，而所需
的存储量越小，则其效率就越高。
在许多情况下各种因素是互相制约的。要
求算法的可读性好，则其效率就不一定理
想；如果要求执行时间短，则所需的存储
量就可能比较大，这种场合是以空间为代
价来换取时间的；如果要求使用的存儲量
较小，则执行时间就可能较大，这种场合
是以时间为代价来换取空间的。
本章关键术语,
算法的
定义
算法的
特性
算法的
表示
流程图 算法描述
语言
递归 迭代 分治 并行算
法
时间复杂
度
空间复
杂度
可读性 健壮性 可行性
思考与练习,
1） 什么是算法？它具有哪些特性？
2） 描述算法的常用工具有哪几种？
3） 如何衡量一个算法的优劣？
4) 比较 斐波那契数列的递归算法和迭代
算法，有哪些区别？
当我们试图用计算机解决一个问题时，大
体都要经历如下几个步骤,
1,把问题抽象为一个带有一般性的数学问题，即数
学化。这一步要引入一些数学概念，给出所求问题
的已知条件、所要求的结果、以及在已知条件和所
要求的结果之间存在着的隐式或显式的联系。
2,建立相应的求解方法。这一步要给出问题的求解模型，
即确定问题的数据模型并在此模型上定义一组运算，
然后借助于对这组运算的调用和控制，根据已知数
据导出所要求的结果。
3,用一种程序设计语言描述算法。即将非形式自然语
言表达的算法转变为一种程序设计语言表达的算法。
也可称做程序设计或程序编制。
4,编辑、调试和测试程序代码，直到输出所要求的
结果。
? 获得了计算方法和算法，并不等于问题可解，
是否可解取决于算法的存在性和计算的复杂性。
即是否存在求解算法，算法所需要的时间和空
间在数量级上能否被接受。
? 1900年，数学家希尔伯特在巴黎举行的世界数
学家大会上发表了至今仍著名的演说。在演说
中，他提出了 23个数学问题，这就是著名的
,希尔伯特 23个问题,,并认为它们是对下一
个世纪的挑战。其中的第 10个问题是, 丢番图
方程的可解性问题, 。其具体涵义是设计一个
算法来测试多项式是否有整数根。将该问题做
相应简化可以设,
D={p|p是有整数根的 x的多项式 },则集合 D是否
可判定？ 答案是否定的 。
我们可以把多项式输入到计算机中进行处理，当
x赋值为 0,-1,1,-2,2,-3,3,…… 时，分
别求出多项式的值，一旦求得 0值，就接受，如
果 p没有整数根，则程序将永远运行下去 。
本章内容
? 4.1 算法的概念
? 4.2 算法的表示
? 4.3 常用算法介绍
? 4.4 并行算法
? 4.5 算法的评价
? 4.6 算法的设计要求
4.1.1 算法的定义
? 算法是程序设计的精髓，程序设计的实质就是
构造解决问题的算法，将其解释为计算机语言。
? 有关算法 (algorithm)的定义不只一种，其中
一种叙述为：算法是对特定问题求解步骤的一
种描述，它是指令的有限序列，其中每一条指
令表示一个或多个操作。
曾获图灵奖的著名科学家克努斯 （ D.Knuth）
对算法这一概念给出了进一步的描述 。
? 一个算法，就是一个有穷规则的集合，其中
之规则确定了一个解决某一特定类型问题的
运算序列。此外，算法的规则序列必须满足
下列五个重要条件,
（ 1） 有穷性 。 算法必须总是在执行有穷步之后结束；
（ 2） 确定性 。 算法的每一步骤必须被确切地定义；
（ 3） 输入 。 算法有零个或多个输入；
（ 4） 输出 。 算法有一个或多个输出；
（ 5）能行性。算法中有待执行的运算和操作必须是相当
基本的，即它们原则上都是能够精确地进行的，而且
用笔和纸做有穷次就可以完成。
除了算法的非形式化定义外，还有算法的形式化定义,
算法是一个四元组，即（ Q,I,O,F）。
其中,
1 Q 是一个包含子集 I 和的集合它表示计算的状态 。
2 I 表示计算的输入集合；
3 O 表示计算的输出集合；
4 F 表示计算的规则，它是一个由 Q 到它自身的函数，且
具有自反性，即对于任何一个元素 q∈ Q,有 F(q)=q 。
4.1.2 性质
在 4.1.1中我们曾介绍了克努斯给出的算
法定义,其中包括算法成立的五个重要条
件,实际上就是算法的规则序列必须满足
的五个特性 。
例 1 给定两个整数 m和 n，试写出它们的最大公因
子的算法。
其算法如下,
1,读入两个正整数 m和 n（设 m>n）。
2,求 m和 n的余数 r。
3,用 n的值取代 m，用 r的值取代 n。
4,判断 r的值是否为零，如果 r=0，则 m为最大公
因子，否则返回 2
5,输出 m的值。
? 我们可以看到，无论给出多大的两个数，这个
算法都会在执行一定次数之后结束。这是算法
的有穷性要求：, 算法必须总是（对任何合法
的输入值）在执行有穷步之后结束，且每一步
都可在有穷时间内完成, 。
? 给出的数值必须是确定的，不能出现诸如
,比 m大一些或比 n小一点儿, 之类的无法确
定数值的表达方式。这是算法的确定性要求：
算法中每一条指令必须被确切地定义，读者
理解时不会产生二义性。
? 算法一定是可操作的，当我们用笔和纸代替
计算机去完成计算过程时,是可以做到的。这
是算法的可行性要求：即算法中描述的操作
都是可以通过有限次的基本运算执行来实现
的。
? 一个算法有零个或多个的输入。在上述的例
子中共有两个已知变量,m和 n,否则算法将无
法执行下去,这是算法的输入要求。
? 算法必须给出结果，在本例中，结果为 m和 n
的最大公因子。这是算法的输出要求：一个
算法有一个或多个的输出，这些输出是与输
入有着某些特定关系的量。
4.2 算法的表示
? 算法不能直接被计算机执行，使用它的
目的就是把你的思想表达出来。可以使
用专门的工具进行描述。常用的描述工
具有：自然语言、流程图、决策表及算
法描述语言等。
? 关于最大公因子的描述方法使用的就是
自然语言，即人们 日常交流所用的语言
进行描述。
1 自然语言的歧义性容易导致算法执行的不
确定性；
2 自然语言的语句一般太长从而导致了所描
述的算法太长；
3 由于自然语言表示的串行性,因此当一个算
法中循环和分支较多时就很难清晰地表示出
来；
4 自然语言表示的算法不能直接被计算机接
受。
由于自然语言具有二义性和不确定性而难以严
格表示算法的逻辑流程，因此一般不用自然语
言描述算法。
? 流程图是用一种图形工具描述算法或程序结
构。 流程图是描述算法的常用工具，它采用
美国国家标准化协会 ANSI （ American
National Standard Institute） 规定的一
组图形符号来表示。 算法流程图可以很方便
地表示顺序选择和循环结构，而任何程序的
逻辑结构都可以用顺序选择和循环结构来表
示，因此流程图可以表示任何程序的逻辑结
构。
例如，用矩形表示处理，用菱形表示判断，用
平行四边形输入 /输出，用带箭头的折线表示
流程等等。
将例 1用流程图表示如下,
begin
end
write m
read m,n
n=r
m=n
r=mod(m,n)
r=0
T
F
从上例中我们看到, 只要掌握了流程图
中各种符号所代表的含义, 即可以知道
要完成的操作 。 下面让我们再看一个例
子,
例 2 求解 1到 100的和的算法流程图
开始
结束
X=X+Y
Y=Y+1
Y=2
X=1
Y>100
write x
T
F
? 决策表又称为判断表，它列出了对于所
有可能的条件应采取的动作。适用于描
述一个复杂的判断过程。
? 算法描述语言是一种把自然语言与程序
设计语言相结合起来的算法描述工具。
保留了程序设计语言严谨的结构、语句
的形式和控制成分，忽略了繁琐的变量
说明。
例１的算法描述语言,
PROCDURE Euclid’s algorithm；
BEGIN
READ（ m,n） ;
REPEAT;
r:=mod(m,n);
m:=n;
n:=r;
UNTIL r=0;
WRITE (m)
END
? 上面的这种描述示方法与计算机程序
非常相似，但又不是正式的程序，需
要进一步加工才能在计算机中实现。
例 1演示
例 3 给出小于 100的斐波那契数的算法描述 。
首先，我们给出斐波那契数列（, 兔子问
题, ）, 0,1,1,2,3,5,8, 13,
21,34,…
假设一对刚出生的兔子一个月后就能长大，
再过一个月就能生下一对兔子，并且此后每
个月都能生一对兔子，且新生的兔子在第二
个月后，也是每个月生一对兔子。问一对兔
子一年内可繁殖成多少对兔子？
其算法可描述如下,
PROCEDURE Fibonacci;
BEGIN
n1:=0;
n2:=1;
n3:=0;
WRITE (n1,n2);
WHILE n3<100 DO
BEGIN
n3:=n1+n2;
WRITE(n3);
n1:=n2;
n2:=n3;
END
END
例 3演示
? 算法是供人来阅读的，必须牢记这一点。算
法中语句的书写格式采用缩进规则，保留字
用大写，其余标识符小写，以提高算法的易
读性。
4.3 常用算法介绍
? 算法包括数值计算算法和非数值计算算
法两类，后者尤为重要。关于算法的概
念及应用，更深入的内容将在算法设计
与分析等课程中学习。在此简单介绍分
治法、递归法、迭代法等。
4.3.1递归
? 所谓递归是指：一个过程用自身的简单情况来
定义自身，再自己调用自己则称它们是递归的，
或者是递归定义的。
递归是一种强有力的数学工具，它可使问
题的描述和求解变得简洁和清晰。递归算法常
常比非递归算法更易设计，尤其是当问题本身
或所涉及的数据结构是递归定义的时候，使用
递归算法特别合适。
例 1 非负整数 n的阶乘可递归定义为,
n!=
1 n=0
n*(n-1) n=0
? 递归算法的设计步骤
第一步骤（递归步骤）：将规模较大的原问
题分解为一个或多个规模更小、但具有类似
于原问题特性的子问题。即较大的问题递归
地用较小的子问题来描述，解原问题的方法
同样可用来解这些子问题。
第二步骤：确定一个或多个无须分解、可直
接 求解的最小子问题（称为递归的终止
条件）。
例 2 函数 f(n)可递归定义为,
f(n)=
n*f(n－ 1) (n>0)
1 (n=0)
（ 1）递归边界条件。也就是所描述问题的最简
单情况，它本身不再使用递归的定义。如上例，
当 n=0时,f(n)=1，不使用 f(n-1)来定义。
（ 2）递归定义：使问题向边界条件转化的规则。
递归定义必须能使问题越来越简单。 如上例：
f(n)由 f(n-1)定义，越来越靠近 f(0),也即边界条
件。最简单的情况是,f(0)=1。
裴波那契数的形式化定义, f(n)=f(n-1)+f(n-
2); f(0)=1; f(1)=2。事实上，这种定义方法
就是递归。它所对应的递归程序为,
Function fib(n, integer), integer;
Begin
If n = 0 then fib,= 1 { 递归边界 }
Else if n = 1 then fib,= 2
Else fib,= fib(n-2) + fib(n-1) { 递归 }
End;
? 递归算法能使一个蕴含递归关系且结构
复杂的程序简捷精炼,增加可读性。特
别是在难于找到从边界到解的全过程的
情况下,如果把问题推进一步，没有结
果仍维持原问题的关系,则采用递归算
法编程比较合适 。
用递归算法解决汉诺塔问题。假设有三
个塔,每个塔都堆放 n 个盘子。开始
时,所有盘子均在塔 A上,并且,盘从上
到下,按直径增大的次序放置。此题目
的目的是设计一个盘子移动的序列，使
得塔 A 上的所有盘子借助于塔 B 移动
到塔 C 上。
其中, 有两个限制条件, 1,一次只能搬动一
个盘子 。 2,任何时候不能把盘子放在比它小
的盘子的上面 。
第 1步, 把 n-1 个盘子从塔 A 搬到塔 B。
第 2步, 将剩下的一只盘 (也就是最大的一只 )
直接从 A 塔搬到那个仍然空着的塔 C 。
第 3步：用第一步描述的方法,再次将 B
塔上的盘搬到 C 塔。操作方法和第一步一
样,但这一步实际上是由 n-1的盘子组成。
这一步是没有问题的,因为塔 C上仅有的一只
盘是最大的。
算法演示
main() /* 读入要搬动的盘的个数 */
{
int disks; /*定义变量 disks，用于存放盘的个数 */
void towers(int,char,char,char); /*函数 tower()声明
*/
printf("Number of disks,");
scanf("%d",&disks); /*输入盘的数目 */
towers(disks,'A','B','C'); /*调用函数
towers() 用于完成递归算法 */
}
void move_disk(char src,char dst)
{
printf("%c ====> %c",src,dst);
}
void towers(int n,char src,char mid,char dst)
{
void move_disk(char,char);
if (n==1)
{
move_disk(src,dst);/*调用函数 move_disk（）打印盘从一个
塔到另一个塔的搬动过程 */
return;
}
towers(n-1,src,dst,mid);
move_disk(src,dst);
towers(n-1,mid,src,dst);
}
4.3.2 迭代
? 迭代法是一种逐次逼近法。迭代一词按
其字面解释,,迭, 代表屡次和反复的
意思,,代, 表示替换的意思，合起来
迭代就是反复替换的意思。在程序设计
中为了处理重复性计算的问题，最常用
的方法就是迭代方法。主要是循环迭代。
? 迭代与递归有着密切的联系，甚至前面提到
的 X0=a,Xn+1=f(n)的递归关系也可以看作是
数列的一个迭代关系，可以证明迭代程序都
可以转换为与它等价的递归程序，反之则不
然，就效率而言，递归程序的实现要比迭代
程序的实现耗费更多的时间和空间，因此在
具体实现时又希望尽可能将递归程序转化为
等价的迭代程序。
有的问题既可以用递归，也可以用迭代
方法完成，但并非全部，像汉诺塔问题
只能用递归方法实现，不能用迭代方法
解决。
用迭代方法求解 斐波那契数 问题的自然语言描
述如下,
1） 如果 n=0,那么将 0 赋值给 Y,并输出 Y，
转步骤 11，否则继续执行；
2） 将 0 赋给 X, 将 1 赋值给 Y；
3） 输出 X,Y；
4） 将 1 赋值给 I；
5） 如果 I 大于 n-1,则转到步骤 11，否则
继续执行；
6)将 X 和 Y 的和赋值给 Z；
7） 将 Y 赋值给 X；
8） 将 Z 赋值给 Y；
9） 将 Y 输出；
10) 将 I 加 1，转步骤 5 继续执行；
11) 算法结束。
4.3.3 分治法
? 分治法的设计思想是将一个难以直接解决的
大问题，分割成一些规模较小的相同问题，
以便各个击破，含, 分而治之, 之意。
? 如果原问题可分割成 k个子问题,1<k≤n,且
这些子问题都可解，并可利用这些子问题的
解求出原问题的解，那么这种分治法就是可
行的。
? 由分治法产生的子问题往往是原问题的较小
模式，这就为使用 递归技术 提供了方便。在
这种情况下，反复应用分治手段，可以使子
问题与原问题类型一致而其规模却不断缩小，
最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。分治与递归像
一对孪生兄弟，经常同时应用在算法设计之
中，并由此产生许多高效算法。
例如，求 n个元素集合 S的最大元素和最小元
素问题。可以把 S分成大小相等的两个子集 S1
和 S2，递归的求出 S1及 S2的最大元素和最小
元素。只要从两个最大元素中选出一个较大
的，从两个最小元素中选出一个较小的，则
它们分别是 S的最大元素和最小元素。
后续将要介绍的二分查找法，也运用了分治法
的思想。例如，给定一排好序的整型序列，查
找元素 x是否在该序列中。这时，需将待查元
素与 中值元素 进行比较，即把一个长度为 n的
有序表分成两个长度小于等于 n/2的有序段，
依次进行查找，如果查找不成功，则需查找剩
下的另一段。
4.4 并行算法
? 并行算法是指一次可执行多个操作的算法。对
并行算法的研究现在已发展为一个独立的研究
领域。很多用串行算法解决的问题也已经有了
相应的并行算法。
这里介绍的并行算法将用一种流行的理论模
型即并行随机存取计算机 (PRAM)来描述。因
为很多关于数据结构的概念，如数组、表、
树和图的并行算法都可以很容易地用 PRAM
模型来描述，所以，这里对 PRAM模型做一
简单介绍。
1,PRAM模型
图 4.3说明了 PRAM的基本结构。其中有 n个普
通的串行处理器 p0,p1,...,pn-1共享一个全局
存储器。所有处理器都可以, 并行地, (同时 )
从全局存储器读出信息或向全局存储器写入
信息。各处理器也可以并行地执行各种算术
和逻辑操作。
P0
Shared
memory
P1
P2
Pn1
..,
..,
? 并行算法的运行时间既依赖于执行算法的处理
器数目，也依赖于输入问题本身的规模。一般
来说，在分析 PRAM算法时我们必须同时讨论
其时间和处理器数目，这与串行算法完全不同，
在串行算法中我们主要集中于对时间的分析。
? 并发存储器存取方式与互斥存储器存取方式
并发读算法是指在算法执行过程中多处理器
可以同时对共享存储器的同一位置进行读操
作的一种 PRAM算法。互斥读算法是指在算
法执行中任何两个处理器都不能同时对共享
存储器的同一位置进行读操作的一种 PRAM
算法。
? EREW：互斥读且互斥写
? CREW：并发读且互斥写
? ERCW：互斥读且并发写
? CRCW：并发读且并发写
? 同步与控制
PRAM算法必须高度同步以保证其正确执
行。如何获得这一同步特征？另外，
PRAM算法中的处理器常常必须测试循环
的终止条件，而这一终止条件又往往取决
于所有处理器的状态。如何实现这种控制
功能？
许多并行计算机采用了一种连接各处理器的
控制网络，以帮助实现同步和对终止条件进
行测试。在特定情况下，控制网络实现这些
功能的速度可以与路径选择网络实现对全局
存储语句的速度一样快。
为方便起见，我们假设各个处理器都有严格
同步的特征。所有处理器同时执行相同的语
句。处理器执行代码的进度也保持一致。
4.5 算法的评价
? 对算法的研究，第一步是设计算法，第二
步是复杂性分析。对同一问题，若有两种
不同的算法，两种算法的优劣要根据复杂
性分析的结果来判断。一般认为需要的时
间较短，存取单元较少的算法是较好的。
4.5.1 算法的时间复杂度
? 算法的时间复杂度（ Time Complexity）
是依据算法编制成程序后在计算机中运
行时所耗费的时间的大小来决定的。一
个程序在计算机上运行时所耗费的时间
取决于程序运行时输入的数据量、对源
程序编译所需要的时间、执行每条指令
所需的时间以及程序中语句执行的次数。
其中一个最重要的指数是程序中语句重
复执行的次数。
? 算法的时间复杂度 T(n)实际上是表示当
问题的规模 n充分大时该程序所占用时间
的一个数量级。例如，若某程序运行时
的时间复杂度为 T(n)=2n3+3n2+2n+1,则表
明程序运行所需要的时间与 n3成正比。
引入符号,O”,则有 T（ n） =O(n3)。
4.5.2 算法的空间复杂度
例 1,在三个整数中求最大值。其中，算法（一）如下,
max(int a,int b,int c) /*给出三个整数 */
{ if (a>b) /*如果 a>b*/
{ if(a>c) return a; /*如果 a>c，返回 a*/
else return c; /*否则返回 c*/
}
else
{ if(b>c) return b; /*如果 b>c，则返回 b*/
else return c; /*否则返回 c*/
}/*运算过程无需额外存储空间，只需两次比较 */
算法（二）如下,
max(int a[3])
{ int c,int i;
c=a[0];
for(i=1;i<3;i++)
if (a[i]>c) c=a[i];
return c;
} /*需要两个额外的存储空间，两次比较，至少一次
赋值，共需 5个整型数空间 */
当用算法（一）实现求 100个整数中的最大值时，算法
几乎是无法描述的，但算法（二）只要稍做改动即可。
max(int a[100])
{ int c,int i;
c=a[0];
for(i=1;i<100;i++)
if (a[i]>c) c=a[i];
return c;
} /*共需 102个整型数空间 */
例 1(二 )
? 算法的空间复杂度 (Space Complexity)是指
依据算法编制成程序后在计算机中运行时所
占用的空间的大小。一个程序在计算机上运
行所占用的空间同样也是 n的一个函数，称为
算法的空间复杂度，记为 S（ n）。如果
S(n)=O(n2)，表示运行时所占用的空间与 n2
成正比。
4.5.3 算法的易理解性
? 一个算法如果难以理解，将给应用和评价带来
一定的困难，易理解性是衡量一个算法优劣的
重要标准。因为给出算法的目的是让别人能读
懂，理解并编写相应的程序进行维护和修改。
因此，具有良好的结构、易理解、易维护的算
法是人们追求的目标。
4.6 算法设计的要求
1 正确
算法应当满足具体问题的需求。正确性
是设计和评价一个算法的首要条件。如果
一个算法不正确，其他方面就无从谈起。
一个正确的算法是指在合法的数据输入情
况下，能在有限的运行时间内得出正确的
结果。选用或设计的算法首先应该保证是
正确的。
2 可读
算法最主要目的是为了阅读与交流，并将它
转换成可实现的程序在计算机中执行。可读
性好不仅有助于人们对算法的理解，而且也
有利于程序的调试与修改。在保证算法正确
的前提下，应十分强调算法的可读性。
3 健壮
健壮是指算法对各种可能的情形都考虑的
非常完善。当输入数据非法时，算法也能
适当地作出反应或进行处理。而不会发生
异常或输出莫名期妙的结果。例如，输入
三角形的三条边长时，若其二边之和小于
另一条边，则算法执行中应输出相应的通
告信息而不是发生异常。
4 高效
它是指算法的执行效率要高。算法的效率包
括时间效率与空间两个方面。时间效率是指
算法的执行所需要的时间，而空间效率是指
执行该算法所需的存储量。对应同一个问题
和同一问题的规模，若采用不同的算法进行
处理，其执行的效率就可能不相同。对于一
种算法来说，如果执行的时间越短，而所需
的存储量越小，则其效率就越高。
在许多情况下各种因素是互相制约的。要
求算法的可读性好，则其效率就不一定理
想；如果要求执行时间短，则所需的存储
量就可能比较大，这种场合是以空间为代
价来换取时间的；如果要求使用的存儲量
较小，则执行时间就可能较大，这种场合
是以时间为代价来换取空间的。
本章关键术语,
算法的
定义
算法的
特性
算法的
表示
流程图 算法描述
语言
递归 迭代 分治 并行算
法
时间复杂
度
空间复
杂度
可读性 健壮性 可行性
思考与练习,
1） 什么是算法？它具有哪些特性？
2） 描述算法的常用工具有哪几种？
3） 如何衡量一个算法的优劣？
4) 比较 斐波那契数列的递归算法和迭代
算法，有哪些区别？
