2009-7-26
计算机算法基础
(课件 V0.1)
王多强华中科技大学计算机学院
2009-7-26
序专业基础课程：
数据结构、计算机语言操作系统、编译如何编写计算机程序：
数据结构 +算法 = 程序
算法：计算机软件的,灵魂,
算法是计算机科学和计算机应用的核心
2009-7-26
教材：
计算机算法基础 余祥宣等编著 华中科技大学出版社参考书：
算法设计与分析 王晓东编著 清华大学出版社计算机算法导引 —— 设计与分析 卢开澄编著 清华大学出版社
Introduction To Algorithm 高教出版社,MIT Press
学时,32+8学时
2009-7-26
章节安排
第一章 导引与基本数据结构 √
第二章 分治法 √
第三章 贪心方法 √
第四章 动态规划 √
第五章 检索与周游 √
第六章 回溯法 ⊙
第七章 分枝 -限界 ⊙
第八章 NP-问题?
2009-7-26
第一章 导引与基本数据结构
1.1 算法的定义及特性
1,什么是算法？
★ 算法如数字、计算一样，是一个 基本概念 。
★ 算法是解一 确定类 问题的任意一种 特殊 的方法。
★ 在计算机科学中，算法是使用计算机解 一类问题的精确、有效方法的代名词；
算法 是一组 有穷的规则,它规定了解决某一 特定类型问题 的一系列 运算 。
2009-7-26
2,算法的五个重要特性确定性,能行性,输入,输出,有穷性
1） 确定性,算法的每种运算必须要有确切的定义，不能有二义性。
例：不符合确定性的运算
5/0
将 6或 7与 x相加
未赋值变量参与运算
2009-7-26
2） 能行性算法中有待实现的运算都是基本的运算，
原理上每种运算都能由人用纸和笔在“有限”的时间内完成。
例：整数的算术运算是“能行”的实数的算术运算是,不能行” 的
2009-7-26
3） 输入每个算法有 0个或 多 个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合 —— 定义域 （或值域）
4） 输出一个算法产生 一个 或 多个 输出，这些输出是同输入有某种特定关系的量。
2009-7-26
5） 有穷性一个算法总是在执行了 有穷步 的运算之后 终止 。
计算过程,只满足确定性、能行性、输入、输出四个特性的一组规则。
算法和计算过程的区别：
计算过程：操作系统 (不终止的运行过程 )
算法是“可以终止的计算过程”
算法的时效性：只能把在 相当 有穷步内终止的算法投入到计算机上运行
2009-7-26
4,我们的主要任务算法学习将涉及 5个方面的内容：
1） 设计算法,创造性的活动
2） 表示算法,思想的表示形式,SPARKS语言
3） 确认算法,证明算法对所有可能的合法输入都能得出正确的答案。
算法证明,证明算法的正确性，与语言无关程序证明,证明程序的正确性
4） 分析算法,对算法的时、空特性做 定量 分析，以了解算法的好坏
5） 测试程序,
调试,“调试只能指出有错误，而不能指出它们不存在错误”
作时空分布图,验证分析结论，优化算法设计本课程集中于学习算法的 设计 与 分析 。通过学习，掌握计算机算法设计和分析 基本策略与方法,为设计更复杂、更有效的算法奠定基础
2009-7-26
5,课程关系数据结构程序设计语言：结构化设计数学基础非数值计算领域的基本知识
2009-7-26
1.2 分析算法
1,分析算法的目的在于：通过对算法的分析，在把算法变成程序实际运行前，
就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。
算法分析是计算机领域的“古老”而“前沿”的课题。
2009-7-26
2,重要的假设和约定
1）计算机模型的假设
计算机形式理论模型,Turing机模型
通用计算机模型：
顺序计算机
有足够的“内存”
能在固定的时间内存取数据单元
2009-7-26
2）计算的约定算法的执行时间 =∑fi*ti
其中,fi是算法中用到的某种运算 i的次数 —— 称为该运算的,频率计数,
ti是该运算执行一次所用的时间 —— 与程序语言和硬件有关确定：使用何种运算及其执行时间。
从运算的“时间特性”上将运算的分类：
时间囿界于常数的运算,
· 基本算术运算，如整数、浮点数的加、减、乘、除
· 字符运算,赋值 运算,过程调用等特点：尽管每种运算的执行时间不同，但一般只花一个固定量 的时间（单位时间）就可完成。
2009-7-26
2）计算的约定（续）
其他运算,
· 字符串操作：与字符串中字符的数量成正比
· 记录操作：与记录的属性数、属性类型等有关特点：运算时间 无定量 。
如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。
如,tstring = Length（ String） * tchar
2009-7-26
3）工作数据集的选择
编制能够反映算法在最好、平均、最坏情况下工作的 数据配置 。然后使用这些数据配置运行算法，以了解算法的性能。
编制测试数据 是程序测试与算法分析中的关键技术之一。
· 作为算法分析的数据集：反映算法的典型特征
· 作为程序正确性及性能测试的数据集：测试程序的对错，反映对性能指标产生影响的方面,如边界值
2009-7-26
3,如何进行算法分析？
对算法进行全面分析，可分两个阶段进行：
事前分析,求算法的一个 时间 /空间限界函数,即通过对算法的“理论”分析，得出关于算法 时间和空间特性的特征函数（ Ο,Ω） —— 与计算机物理软硬件没有直接关系。
事后测试,将算法编制成程序后实际放到计算机上运行，
收集其执行时间和空间占用等统计资料，进行分析判断 —— 直接与物理实现有关。
2009-7-26
1）事前分析
目的：试图得出关于算法特性的一种形式描述，以“理论上”衡量算法的“好坏”。
如何给出反映算法特性的描述？
统计算法中各种运算的执行情况，包括：
引用了哪些运算
每种运算被执行的次数
该种运算执行一次所花费的时间等。
算法的执行时间 =∑fi*ti
2009-7-26
频率计数频率计数,算法中 语句 或 运算 的执行次数。
例：
x←x+y for i ←1 to n do for i ←1 to n do
x ← x + y for j ←1 to n do
repeat x ← x +y
repeat
repeat
(a) (b) (c)
分析：
(a),x←x+y 执行了 1次
(b),x←x+y 执行了 n次
(c),x←x+y 执行了 n2次
2009-7-26
一条语句在整个程序运行时实际执行时间 =
频率计数 * 每执行一次该语句所需的时间
在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。
2009-7-26
数量级
—— 衡量 频率计数 的,大小,的一种测度
语句的数量级,语句的执行频率例,1,n,n2
算法的数量级,算法所包含的所有语句的执行频率之和。
数量级反映了算法复杂度的最本质的特征。
例：假如求解同一个问题的三个算法分别具有 n,n2,n3数量级。
若 n=10，则可能的执行时间将分别是 10,100,1000个单位时间 —— 与环境因素无关。
2009-7-26
频率计数的函数表示就 计算时间 而言，事前分析阶段求得算法在频率计数上的 函数 表示 —— 与规模 n有关的函数形式，记为,g(n)
★ 不同的算法,g(n)的具体形式是不同的，如
logn,nlogn,n2等
★ g(n)的一般形式：关于 n的简单函数式
“实际”能够得到的：
1) 函数式的 最高次项
2)最高次项 与函数整体的关系。
空间特性分析（与时间特性的分析类似，略）
2009-7-26
2）事后测试
目的：运行程序，统计执行实际耗费的准确的时间与空间，与事前分析的结论进行比较，验证先前的分析结论 —— 包括正确性、执行性能等，比较、优化所设计的算法。
分析手段：作时、空性能分布图
2009-7-26
4,计算时间的渐近表示记：算法的实际计算时间为 f(n)，计算时间的限界函数为 g(n)
其中，
n是输入或输出规模的某种测度。
f(n)表示算法的“实际”执行时间 — 与机器及语言有关 。
g(n)是事前分析的结果 —— 一个 形式简单 的函数，如 nm,logn，
2n,n!等。是与频率计数有关、而 与机器及语言无关 的函数。
以下给出算法执行时间,上界 （ О ）,下界 （ Ω ）,“平均”
（ ）的定义。
2009-7-26
1）上界函数定义 1 如果存在两个正常数 c和 n0，对于所有的 n≥n 0，有
|f(n)| ≤ c|g(n)|
则记作 f(n) = Ο(g(n))
含义：
如果算法用 n值不变的同一类数据在某台机器上运行时，所用的时间总是小于 |g(n)|的一个常数倍。所以 g(n)是计算时间 f(n)的一个 上界函数 。 f(n)的数量级就是 g(n)。
试图求出 最小 的 g(n)，使得 f(n) = Ο(g(n))。
2009-7-26
多项式定理定理 1 若 A(n) = amnm+?+a 1n+a0是一个 m次多项式，则有
A(n) = Ο(nm)
即：变量 n的固定阶数为 m的任一多项式，与此多项式的最高阶
nm同阶。
证明：取 n0=1,当 n≥n 0时，有
|A(n)|≤|am|nm+…+|a 1|n+|a0|
≤(|am|+|am-1|/n+…+|a 0|/nm) nm
≤ (|am|+|am-1|+…+|a 0|) nm
令 c= |am|+|am-1|+…+|a 0|
则，定理得证。
2009-7-26
计算时间的 数量级的大小对算法的有效性有 决定性 的影响例：假设解决同一个问题的两个算法，它们都有 n个输入,
计算时间的数量级分别是 n2和 nlogn。则，
n=1024：分别需要 1048576和 10240次运算。
n=2048：分别需要 4194304和 22528次运算。
分析：
★ 同等规模下的计算量比较：
★ 规模增大情况下的比较：在 n加倍的情况下，一个 Ο(n2)的算法计算时间增长 4倍，而一个 Ο(nlogn)算法则只用 两 倍多一点的时间即可完成。
2009-7-26
多项式时间算法 和 指数时间算法
多项式时间算法,可用多项式（函数）对其计算时间限界的算法。
常见的多项式限界函数有：
Ο(1) < Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n2) < Ο(n3)
指数时间算法,计算时间用指数函数限界的算法常见的指数时间限界函数：
Ο(2n) < Ο(n！ ) < Ο(nn)
说明：当 n取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。
2009-7-26
典型的计算时间函数曲线
2009-7-26
一般认识
当数据集的规模很大时，要在现有的计算机系统上运行具有比 Ο(nlogn)复杂度还高的算法是比较困难的。
指数时间算法只有在 n取值 非常小时 才实用。
要想在顺序处理机上扩大所处理问题的规模，有效的途径是 降低算法的计算复杂度,而不是（仅仅依靠）提高计算机的速度。
2009-7-26
计算时间函数值比较
3
2009-7-26
定义 1.2 如果存在两个正常数 c和 n0，对于所有的 n≥n 0，
有
|f(n)| ≥ c|g(n)|
则记作 f(n) = Ω (g(n))
含义：
如果算法用 n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于 |g(n)|的一个常数倍。所以 g(n)是计算时间 f(n)
的一个 下界函数 。
试图求出,最大,的 g(n)，使得 f(n) = Ω (g(n))。
2）下界函数
2009-7-26
定义 1.3 如果存在正常数 c1,c2和 n0，对于所有的 n≥n 0，有
c1|g(n)| ≤|f(n)| ≤ c 2|g(n)|
则记作含义：
算法在最好和最坏情况下的计算时间就一个 常数因子 范围内而言是相同的。可看作：
既有 f(n) = Ω (g(n))，又有 f(n) = Ο(g(n))
))(()( ngnf
3）“平均情况”限界函数
2009-7-26
4）限界函数的性质
1）若 且,则 。即 О具有传递性。（ 同）
2） 当且仅当
3）若,则 。即,定义了一个等价关系（等价类）
证明：
从定义出发。证明过程略。
)(gf )(hg )(hf
、
)( fg
)(gf )( fg
)(gf
2009-7-26
5,常用的整数求和公式在算法分析中，在统计语句的频率时，求和公式的一般形式为：
如：
h ( n )i)(
)(
ng
if
)( 1
1
k
ni
k ni
2009-7-26
1.3 关于 SPARKS语言
本书为描述算法选用的一种计算机语言
类 PASCAL语言
结构化设计
2009-7-26
1,基本语法成分
1）数据类型整型 integer
实型 float
布尔型 boolean
字符型 char
2）变量声明类型说明符 变量；
integer i,j;
boolean b;
char c
3）数组任意整数下标
integer A(1:5,7:20)
integer B(5,7:20)
2009-7-26
4）赋值运算
（变量） ← （表达式）
x ← 2 + x;
5）逻辑运算,and or not
6）关系运算：＜ ≤ ＝ ≠ ≥ ＞
2009-7-26
7）控制结构：
顺序,（略）
分支,
· if condition then S1
else S2
endif
· case
:cond1:S1;
:cond2:S2;
…
:condn:Sn
:else:Sn+1
endcase
循环,
· while cond do
S
repeat
· loop
S
until cond repeat
· for vble←start to finish by
increment do
S
repeat
2009-7-26
8) 过程的定义与调用过程定义
procedure NAME(参数表 )
（说明部分）
S
end NAME
过程的调用,CALL 过程名函数定义类型名 procedure NAME(参数表 )
（说明部分）
S
return (表达式 )
end NAME
函数的引用,x ← function （参数）；
2009-7-26
9) 变量的分类
a）根据数据类型分类整型、实型、字符型等
b）根据作用域分类：
全程变量、局部变量、形式参数
c）根据是否带入、带出数据值 /结果分类：
in型变量
out型变量
inout型变量边界效应：改变了参变量或全程变量的值函数：通过函数值返回输出结果，没有边界效应纯过程：没有函数值返回，只通过边界效应带出输出结果
2009-7-26
10) 特殊语句
a） exit
退出当前一层的循环
b） return
退出过程
return(表达式 ),函数返回结果
c） goto 无条件转向语句
goto label
11) 递归
a）直接递归：过程中包含对自身的调用
b）间接递归：间接调用自身
12) 输入输出
read,print
13）注释
//注释 //
2009-7-26
1.4 基本数据结构
1,栈和队列
线性表,n个元素的有序表
栈和队列：特殊的线性表
利用动态数据结构 —— 链表 实现栈或队列
利用静态数据结构 —— 数组 实现栈或队列
基于以上两种表示形式的栈和队列上的基本运算
2009-7-26
2,树定义 1.4 树（ tree） 是一个或多个结点的 有限 集合，它使得：
有一个指定为 根 （ root）的结点
剩余结点被划分成 m≥0 个不相交的集合：
T1,?,Tm
这些集合的每一个又都是一棵树，并称 T1,?,Tm为根的子树。
2009-7-26
关于树的重要概念
结点的度 （ degree）：一个结点的子树数
树的度,树中结点度的最大值
结点的级 （ level）（又叫层）：设根是 1级，若某结点在 p级，
则它的儿子在 p+1级
树的高度（或深度）,树中结点的最大级数
叶子（终端结点）,度为 0的结点
内结点（非终端结点）,度不为 0的结点
森林,m≥0 个不相交树的集合。
2009-7-26
3 二元树定义 1.5 二元树 （ binary tree）是结点的有限集合，它或者为空,或者由一个根和两棵称为左子树和右子树的不相交二元树所组成。
二元树与度为 2的树的区别
二元树性质：
引理 1.1 一棵二元树第 i级的最大结点数是 2i-1。深度为 k的二元树的最大结点数为 2k-1,k>0。
2009-7-26
2009-7-26
特殊形态的二元树
① 满二元树,深度为 k且有 2k-1个结点的二元树
2009-7-26
② 完全二元树,一棵有 n个结点深度为 k的二元树，当它的结点相当于深度为 k的满二元树中 编号 为 1到
n的结点时，称该二元树是完全的。
完全二元树的叶子结点至多出现在相邻的两级上。
完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理 1.2）。
2009-7-26
③ 堆,堆是一棵完全二元树，它的每个结点的值至少和该结点的儿子们（如果存在的话）的值一样大
（ max-堆）（或小,min-堆）。
④ 二分检索树,二分检索树Ｔ是一棵二元树，它或者为空，
或者每个结点含有一个可以比较大小的数据元素，且有：
· Ｔ的左子树的所有元素比根结点中的元素小；
· Ｔ的右子树的所有元素比根结点中的元素大；
· Ｔ的左子树和右子树也是二分检索树。
注：二分检索树要求树中所有结点的元素值 互异
2009-7-26
3,图图Ｇ 结点集Ｖ和边集Ｅ组成，记为
G=（ V,E）
其中，Ｖ是一个 有限非空 的结点集合；Ｅ是结点 对偶 的集合，Ｅ的每一对偶表示Ｇ的一条边。
2009-7-26
有关图的的重要概念
无向图,边表示为（ｉ，ｊ）
有向图,边表示为 〈 ｉ，ｊ 〉
成本,带有成本的图称为网络（带权图）
邻接
结点的度（出度／入度 ）
路径,由结点 vp到 vq的一条路（ path）是结点
vp,vi1,vi2,?,vim,vq的一个序列，它使得
( vp,vi1 ),( vi1,vi2 ),?,( vim,vq )
是 E（ G）的边。
路的长度,组成路的边数。
2009-7-26
简单路径,除了第一和最后一个结点可以相同以外，其它所有结点都不同。
环,第一个和最后一个结点相同的简单路。
连通图,在无向图中，如果每对结点之间都存在一条路径，则称该图是连通的。
子图,是由 G的结点集 V的子集（记为 VB）和边集 E中连接 VB
中结点的边的子集所组成的图。
连通分图,一个图的最大连通子图。
有向图的强连通性,在有向图中，如果对于每一对结点 i和 j，
既存在一条从 i到 j的路，又存在一条从 j
到 i的路，则称该有向图是强连通的。
2009-7-26
图的表示方法
邻接矩阵 邻接表
2009-7-26
1.5 递归和消去递归
1,递归
递归是一种强有力的设计方法
递归的效率问题
2009-7-26
例 1.3 斐波那契 (Fibonacci)序列：
F0 = F1 = 1
Fi = Fi-1 + Fi-2 （ i>1)
算法 1.7 求斐波那契数
procedure F(n)
//返回第 n个斐波那契数 //
integer n
if n<= 1 then return(1)
else return(F(n-1) + F(n-2))
endif
end F
算法效率：对 F(n-2),F(n-3),… 存在大量的重复计算
改 进：保存中间结果
2009-7-26
例 1.4 欧几里得算法已知两个非负整数 a和 b，且 a＞ b≥0,求这两个数的最大公因数。
辗转相除法,若 b=0，则 a和 b的最大公因数等于 a；若 b＞ 0，
则 a和 b的最大公因数等于 b和用 b除 a的余数的最大公因数。
算法 1.8 求最大公因数
procedure GCD(a,b) // 约定 a>b //
if b=0 then return(a)
else return (GCD(b,a mod b))
endif
end GDC
例,GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;
2009-7-26
例 1.5 用递归策略设计的检索算法已知元素 x和元素表 A（ 1,n），判断 x是否等于 A中某元素的值。
算法 1.9 在 A（ 1,n）中检索 x
procedure SEARCH(i)
//如果在 A（ 1,n） //中有一元素 A（ k） =x，则将其第一次出现的下标 k返回，
否则返回 0//
global n,x,A(1:n)
case
:i>n,return(0)
:A(i) = x; return(i)
:else,return(SEARCH(i+1))
endcase
end SEARCH
0 u<v
T(A,v,u,x)= av u≥v,av = x
T(A,v+1,u,x) u≥v,av≠ x
2009-7-26
2,消去递归直接递归的消去规则,
基本思路,将递归调用的地方用等价的 非递归代码 来代替，并对 return语句 做适当处理。
13条规则,处理直接递归调用和 return语句，将之转换成等价的迭代代码。
初始化
⑴ 在过程的开始部分，插入说明为 栈 的代码并将其初始化为空,StackType Stack[1..SIZE]
Top ← 0
在一般情况下，这个栈用来存放参数、局部变量和函数的值、
每次递归调用的返回地址。
2009-7-26
⑵ 将标号 L1附于第一条可执行语句。
．．．
L1：第一条可执行语句
．．．
然后对于每一处递归调用都用一组执行下列规则的指令来代替。
2009-7-26
处理 递归调用 语句
⑶ 将所有参数和局部变量的值存入栈。
Top ← Top +1
Stack[Top] ←?
栈顶指针 可作为一个全程变量来看待。
⑷ 建立第 i个新标号 Li，并将标号的下标 i存入栈。这个标号的
i值将用来计算返回地址。
Top ← Top +1
Stack[Top] ← i
此标号放在规则⑺所描述的程序段中。
保存现场
2009-7-26
⑸ 计算这次调用的各实在参数（可能是表达式）的值，
并把这些值赋给相应的形式参数。
⑹ 插入一条无条件转向语句转向过程的开始部分：
goto L1
(以上完成一次递归调用 )
2009-7-26
对 退出点 的处理
⑺ 如果这过程是 函数,则对递归过程中含有此次函数调用的那条语句做如下处理：将该语句的此次 函数调用 部分用从栈顶取回该函数值的代码来代替，其余部分的代码按原描述方式照抄，
并将⑷中建立的标号附于这条语句上。
goto L1
Li,x←Stack(Top)
Top← Top -1
A(．．,)
．．．
x← A(,．,)
．．．
end A
2009-7-26
如果此过程不是函数，则将⑷中建立的标号附于⑹所产生的转移语句后面的那条语句。
goto L1
Li,S
B(．．,)
．．．
B(．．,)
S
．．．
end B
2009-7-26
以上步骤消去过程中的 递归调用 。
下面对过程中出现 return语句 进行处理。
注,纯过程结束处的 end可看成是一条没有值与之联系的
return语句
2009-7-26
对每个有 return语句的地方，执行下述规则：
⑻ 如果栈为 空,则执行 正常返回 。
if top ＝ 0 then return(?)
⑼ 否则，将所有输出参数（带有返回值的出口参数，
out/ inout型）的当前值赋给栈顶上的那些对应的变量。
Stack[n] ←?
2009-7-26
⑽ 如果栈中有返回 地址标号 的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未使用的变量。
addr ← Stack[Top]
Top ← Top -1
⑾ 从栈中退出所有局部变量和参数的值并把它们赋给对应的变量。
2009-7-26
⑿ 如果这个过程是函数，则插入以下指令，这些指令用来计算紧接在 return后面的表达式并将结果值存入栈顶。
Top ← Top +1
Stack[Top] ← 表达式的值
⒀ 用返回地址标号的下标实现对该标号的转向。
if addr ＝ i then goto Li
2009-7-26
例 1.6 递归调用示例求数组元素中的最大值算法 1.10 求取数组元素的最大值（递归算法）
procedure MAX1(i)
// 查找数组 A中最大值元素，并返回该元素的 最大下标 。 //
global integer n,A(1:n),j,k
integer i
if i<n then j←MAX1(i+1) //递归调用 //
if A(i) > A(j) then k←i
else k←j
endif
else k←n
endif
return(k) //递归调用的返回 //
end MAX1
max(a1,…,a n)
= max(a1,max(a2,…,a n))
2009-7-26
消去上例中的递归算法 1.11 使用上述的规则消去例 1.10中的递归代码
procedure MAX2(i)
local integer j,k; global integer n,A(1:n)
integer i
integer STACK(1:2*n)
top←0 //规则 1，声明栈的代码，并初始化为空 //
L1,if i<n //规则 2，将标号 L1赋于第一条可执行语句前 //
then top ←top + 1; STACK(top)← i; // 规则 3，参数或局部变量的值入栈 //
top ←top +1; STACK(top)← 2; // 规则 4，建立新标号 2，并入栈 //
2009-7-26
i ← i+1 // 规则 5,计算参数值 //
goto L1 //规则 6,无条件转向算法的开始部分 //
L2,j ←STACK(top); top ←top -1; // 规则 7,处理函数调用，
并将标号 2赋于该语句上 //
if A(i) > A(j) then k ←I
else k ←j
endif
else k ←n
endif
2009-7-26
if top = 0 then return(k) // 规则 8,如果栈空，则正常返回 //
else addr ←STACK(top);top ←top -1; // 规则 10,从栈中退出返回标号 //
i ←STACK(top);top ←top -1; // 规则 11,从栈中退出局部变量和参数的值 //
top ←top+1;STACK(top) ← k; // 规则 12,计算返回值，并将之入栈 //
if addr = 2 then goto L2 endif // 规则 13,用返回地址标号的下标实现对该标号的转向 //
endif
end MAX2
2009-7-26
进一步优化和简化经过消去递归产生的迭代程序。
2009-7-26
算法 1.12 算法 1.11的改进模型
procedure MAX3(A,n)
integer i,k,n;
i←k←n
while i>1 do
i←i -1
if A(i)>A(k) then k←i endif
repeat
return(k)
end MAX3
计算机算法基础
(课件 V0.1)
王多强华中科技大学计算机学院
2009-7-26
序专业基础课程：
数据结构、计算机语言操作系统、编译如何编写计算机程序：
数据结构 +算法 = 程序
算法：计算机软件的,灵魂,
算法是计算机科学和计算机应用的核心
2009-7-26
教材：
计算机算法基础 余祥宣等编著 华中科技大学出版社参考书：
算法设计与分析 王晓东编著 清华大学出版社计算机算法导引 —— 设计与分析 卢开澄编著 清华大学出版社
Introduction To Algorithm 高教出版社,MIT Press
学时,32+8学时
2009-7-26
章节安排
第一章 导引与基本数据结构 √
第二章 分治法 √
第三章 贪心方法 √
第四章 动态规划 √
第五章 检索与周游 √
第六章 回溯法 ⊙
第七章 分枝 -限界 ⊙
第八章 NP-问题?
2009-7-26
第一章 导引与基本数据结构
1.1 算法的定义及特性
1,什么是算法？
★ 算法如数字、计算一样，是一个 基本概念 。
★ 算法是解一 确定类 问题的任意一种 特殊 的方法。
★ 在计算机科学中，算法是使用计算机解 一类问题的精确、有效方法的代名词；
算法 是一组 有穷的规则,它规定了解决某一 特定类型问题 的一系列 运算 。
2009-7-26
2,算法的五个重要特性确定性,能行性,输入,输出,有穷性
1） 确定性,算法的每种运算必须要有确切的定义，不能有二义性。
例：不符合确定性的运算
5/0
将 6或 7与 x相加
未赋值变量参与运算
2009-7-26
2） 能行性算法中有待实现的运算都是基本的运算，
原理上每种运算都能由人用纸和笔在“有限”的时间内完成。
例：整数的算术运算是“能行”的实数的算术运算是,不能行” 的
2009-7-26
3） 输入每个算法有 0个或 多 个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合 —— 定义域 （或值域）
4） 输出一个算法产生 一个 或 多个 输出，这些输出是同输入有某种特定关系的量。
2009-7-26
5） 有穷性一个算法总是在执行了 有穷步 的运算之后 终止 。
计算过程,只满足确定性、能行性、输入、输出四个特性的一组规则。
算法和计算过程的区别：
计算过程：操作系统 (不终止的运行过程 )
算法是“可以终止的计算过程”
算法的时效性：只能把在 相当 有穷步内终止的算法投入到计算机上运行
2009-7-26
4,我们的主要任务算法学习将涉及 5个方面的内容：
1） 设计算法,创造性的活动
2） 表示算法,思想的表示形式,SPARKS语言
3） 确认算法,证明算法对所有可能的合法输入都能得出正确的答案。
算法证明,证明算法的正确性，与语言无关程序证明,证明程序的正确性
4） 分析算法,对算法的时、空特性做 定量 分析，以了解算法的好坏
5） 测试程序,
调试,“调试只能指出有错误，而不能指出它们不存在错误”
作时空分布图,验证分析结论，优化算法设计本课程集中于学习算法的 设计 与 分析 。通过学习，掌握计算机算法设计和分析 基本策略与方法,为设计更复杂、更有效的算法奠定基础
2009-7-26
5,课程关系数据结构程序设计语言：结构化设计数学基础非数值计算领域的基本知识
2009-7-26
1.2 分析算法
1,分析算法的目的在于：通过对算法的分析，在把算法变成程序实际运行前，
就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。
算法分析是计算机领域的“古老”而“前沿”的课题。
2009-7-26
2,重要的假设和约定
1）计算机模型的假设
计算机形式理论模型,Turing机模型
通用计算机模型：
顺序计算机
有足够的“内存”
能在固定的时间内存取数据单元
2009-7-26
2）计算的约定算法的执行时间 =∑fi*ti
其中,fi是算法中用到的某种运算 i的次数 —— 称为该运算的,频率计数,
ti是该运算执行一次所用的时间 —— 与程序语言和硬件有关确定：使用何种运算及其执行时间。
从运算的“时间特性”上将运算的分类：
时间囿界于常数的运算,
· 基本算术运算，如整数、浮点数的加、减、乘、除
· 字符运算,赋值 运算,过程调用等特点：尽管每种运算的执行时间不同，但一般只花一个固定量 的时间（单位时间）就可完成。
2009-7-26
2）计算的约定（续）
其他运算,
· 字符串操作：与字符串中字符的数量成正比
· 记录操作：与记录的属性数、属性类型等有关特点：运算时间 无定量 。
如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。
如,tstring = Length（ String） * tchar
2009-7-26
3）工作数据集的选择
编制能够反映算法在最好、平均、最坏情况下工作的 数据配置 。然后使用这些数据配置运行算法，以了解算法的性能。
编制测试数据 是程序测试与算法分析中的关键技术之一。
· 作为算法分析的数据集：反映算法的典型特征
· 作为程序正确性及性能测试的数据集：测试程序的对错，反映对性能指标产生影响的方面,如边界值
2009-7-26
3,如何进行算法分析？
对算法进行全面分析，可分两个阶段进行：
事前分析,求算法的一个 时间 /空间限界函数,即通过对算法的“理论”分析，得出关于算法 时间和空间特性的特征函数（ Ο,Ω） —— 与计算机物理软硬件没有直接关系。
事后测试,将算法编制成程序后实际放到计算机上运行，
收集其执行时间和空间占用等统计资料，进行分析判断 —— 直接与物理实现有关。
2009-7-26
1）事前分析
目的：试图得出关于算法特性的一种形式描述，以“理论上”衡量算法的“好坏”。
如何给出反映算法特性的描述？
统计算法中各种运算的执行情况，包括：
引用了哪些运算
每种运算被执行的次数
该种运算执行一次所花费的时间等。
算法的执行时间 =∑fi*ti
2009-7-26
频率计数频率计数,算法中 语句 或 运算 的执行次数。
例：
x←x+y for i ←1 to n do for i ←1 to n do
x ← x + y for j ←1 to n do
repeat x ← x +y
repeat
repeat
(a) (b) (c)
分析：
(a),x←x+y 执行了 1次
(b),x←x+y 执行了 n次
(c),x←x+y 执行了 n2次
2009-7-26
一条语句在整个程序运行时实际执行时间 =
频率计数 * 每执行一次该语句所需的时间
在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。
2009-7-26
数量级
—— 衡量 频率计数 的,大小,的一种测度
语句的数量级,语句的执行频率例,1,n,n2
算法的数量级,算法所包含的所有语句的执行频率之和。
数量级反映了算法复杂度的最本质的特征。
例：假如求解同一个问题的三个算法分别具有 n,n2,n3数量级。
若 n=10，则可能的执行时间将分别是 10,100,1000个单位时间 —— 与环境因素无关。
2009-7-26
频率计数的函数表示就 计算时间 而言，事前分析阶段求得算法在频率计数上的 函数 表示 —— 与规模 n有关的函数形式，记为,g(n)
★ 不同的算法,g(n)的具体形式是不同的，如
logn,nlogn,n2等
★ g(n)的一般形式：关于 n的简单函数式
“实际”能够得到的：
1) 函数式的 最高次项
2)最高次项 与函数整体的关系。
空间特性分析（与时间特性的分析类似，略）
2009-7-26
2）事后测试
目的：运行程序，统计执行实际耗费的准确的时间与空间，与事前分析的结论进行比较，验证先前的分析结论 —— 包括正确性、执行性能等，比较、优化所设计的算法。
分析手段：作时、空性能分布图
2009-7-26
4,计算时间的渐近表示记：算法的实际计算时间为 f(n)，计算时间的限界函数为 g(n)
其中，
n是输入或输出规模的某种测度。
f(n)表示算法的“实际”执行时间 — 与机器及语言有关 。
g(n)是事前分析的结果 —— 一个 形式简单 的函数，如 nm,logn，
2n,n!等。是与频率计数有关、而 与机器及语言无关 的函数。
以下给出算法执行时间,上界 （ О ）,下界 （ Ω ）,“平均”
（ ）的定义。
2009-7-26
1）上界函数定义 1 如果存在两个正常数 c和 n0，对于所有的 n≥n 0，有
|f(n)| ≤ c|g(n)|
则记作 f(n) = Ο(g(n))
含义：
如果算法用 n值不变的同一类数据在某台机器上运行时，所用的时间总是小于 |g(n)|的一个常数倍。所以 g(n)是计算时间 f(n)的一个 上界函数 。 f(n)的数量级就是 g(n)。
试图求出 最小 的 g(n)，使得 f(n) = Ο(g(n))。
2009-7-26
多项式定理定理 1 若 A(n) = amnm+?+a 1n+a0是一个 m次多项式，则有
A(n) = Ο(nm)
即：变量 n的固定阶数为 m的任一多项式，与此多项式的最高阶
nm同阶。
证明：取 n0=1,当 n≥n 0时，有
|A(n)|≤|am|nm+…+|a 1|n+|a0|
≤(|am|+|am-1|/n+…+|a 0|/nm) nm
≤ (|am|+|am-1|+…+|a 0|) nm
令 c= |am|+|am-1|+…+|a 0|
则，定理得证。
2009-7-26
计算时间的 数量级的大小对算法的有效性有 决定性 的影响例：假设解决同一个问题的两个算法，它们都有 n个输入,
计算时间的数量级分别是 n2和 nlogn。则，
n=1024：分别需要 1048576和 10240次运算。
n=2048：分别需要 4194304和 22528次运算。
分析：
★ 同等规模下的计算量比较：
★ 规模增大情况下的比较：在 n加倍的情况下，一个 Ο(n2)的算法计算时间增长 4倍，而一个 Ο(nlogn)算法则只用 两 倍多一点的时间即可完成。
2009-7-26
多项式时间算法 和 指数时间算法
多项式时间算法,可用多项式（函数）对其计算时间限界的算法。
常见的多项式限界函数有：
Ο(1) < Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n2) < Ο(n3)
指数时间算法,计算时间用指数函数限界的算法常见的指数时间限界函数：
Ο(2n) < Ο(n！ ) < Ο(nn)
说明：当 n取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。
2009-7-26
典型的计算时间函数曲线
2009-7-26
一般认识
当数据集的规模很大时，要在现有的计算机系统上运行具有比 Ο(nlogn)复杂度还高的算法是比较困难的。
指数时间算法只有在 n取值 非常小时 才实用。
要想在顺序处理机上扩大所处理问题的规模，有效的途径是 降低算法的计算复杂度,而不是（仅仅依靠）提高计算机的速度。
2009-7-26
计算时间函数值比较
3
2009-7-26
定义 1.2 如果存在两个正常数 c和 n0，对于所有的 n≥n 0，
有
|f(n)| ≥ c|g(n)|
则记作 f(n) = Ω (g(n))
含义：
如果算法用 n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于 |g(n)|的一个常数倍。所以 g(n)是计算时间 f(n)
的一个 下界函数 。
试图求出,最大,的 g(n)，使得 f(n) = Ω (g(n))。
2）下界函数
2009-7-26
定义 1.3 如果存在正常数 c1,c2和 n0，对于所有的 n≥n 0，有
c1|g(n)| ≤|f(n)| ≤ c 2|g(n)|
则记作含义：
算法在最好和最坏情况下的计算时间就一个 常数因子 范围内而言是相同的。可看作：
既有 f(n) = Ω (g(n))，又有 f(n) = Ο(g(n))
))(()( ngnf
3）“平均情况”限界函数
2009-7-26
4）限界函数的性质
1）若 且,则 。即 О具有传递性。（ 同）
2） 当且仅当
3）若,则 。即,定义了一个等价关系（等价类）
证明：
从定义出发。证明过程略。
)(gf )(hg )(hf
、
)( fg
)(gf )( fg
)(gf
2009-7-26
5,常用的整数求和公式在算法分析中，在统计语句的频率时，求和公式的一般形式为：
如：
h ( n )i)(
)(
ng
if
)( 1
1
k
ni
k ni
2009-7-26
1.3 关于 SPARKS语言
本书为描述算法选用的一种计算机语言
类 PASCAL语言
结构化设计
2009-7-26
1,基本语法成分
1）数据类型整型 integer
实型 float
布尔型 boolean
字符型 char
2）变量声明类型说明符 变量；
integer i,j;
boolean b;
char c
3）数组任意整数下标
integer A(1:5,7:20)
integer B(5,7:20)
2009-7-26
4）赋值运算
（变量） ← （表达式）
x ← 2 + x;
5）逻辑运算,and or not
6）关系运算：＜ ≤ ＝ ≠ ≥ ＞
2009-7-26
7）控制结构：
顺序,（略）
分支,
· if condition then S1
else S2
endif
· case
:cond1:S1;
:cond2:S2;
…
:condn:Sn
:else:Sn+1
endcase
循环,
· while cond do
S
repeat
· loop
S
until cond repeat
· for vble←start to finish by
increment do
S
repeat
2009-7-26
8) 过程的定义与调用过程定义
procedure NAME(参数表 )
（说明部分）
S
end NAME
过程的调用,CALL 过程名函数定义类型名 procedure NAME(参数表 )
（说明部分）
S
return (表达式 )
end NAME
函数的引用,x ← function （参数）；
2009-7-26
9) 变量的分类
a）根据数据类型分类整型、实型、字符型等
b）根据作用域分类：
全程变量、局部变量、形式参数
c）根据是否带入、带出数据值 /结果分类：
in型变量
out型变量
inout型变量边界效应：改变了参变量或全程变量的值函数：通过函数值返回输出结果，没有边界效应纯过程：没有函数值返回，只通过边界效应带出输出结果
2009-7-26
10) 特殊语句
a） exit
退出当前一层的循环
b） return
退出过程
return(表达式 ),函数返回结果
c） goto 无条件转向语句
goto label
11) 递归
a）直接递归：过程中包含对自身的调用
b）间接递归：间接调用自身
12) 输入输出
read,print
13）注释
//注释 //
2009-7-26
1.4 基本数据结构
1,栈和队列
线性表,n个元素的有序表
栈和队列：特殊的线性表
利用动态数据结构 —— 链表 实现栈或队列
利用静态数据结构 —— 数组 实现栈或队列
基于以上两种表示形式的栈和队列上的基本运算
2009-7-26
2,树定义 1.4 树（ tree） 是一个或多个结点的 有限 集合，它使得：
有一个指定为 根 （ root）的结点
剩余结点被划分成 m≥0 个不相交的集合：
T1,?,Tm
这些集合的每一个又都是一棵树，并称 T1,?,Tm为根的子树。
2009-7-26
关于树的重要概念
结点的度 （ degree）：一个结点的子树数
树的度,树中结点度的最大值
结点的级 （ level）（又叫层）：设根是 1级，若某结点在 p级，
则它的儿子在 p+1级
树的高度（或深度）,树中结点的最大级数
叶子（终端结点）,度为 0的结点
内结点（非终端结点）,度不为 0的结点
森林,m≥0 个不相交树的集合。
2009-7-26
3 二元树定义 1.5 二元树 （ binary tree）是结点的有限集合，它或者为空,或者由一个根和两棵称为左子树和右子树的不相交二元树所组成。
二元树与度为 2的树的区别
二元树性质：
引理 1.1 一棵二元树第 i级的最大结点数是 2i-1。深度为 k的二元树的最大结点数为 2k-1,k>0。
2009-7-26
2009-7-26
特殊形态的二元树
① 满二元树,深度为 k且有 2k-1个结点的二元树
2009-7-26
② 完全二元树,一棵有 n个结点深度为 k的二元树，当它的结点相当于深度为 k的满二元树中 编号 为 1到
n的结点时，称该二元树是完全的。
完全二元树的叶子结点至多出现在相邻的两级上。
完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理 1.2）。
2009-7-26
③ 堆,堆是一棵完全二元树，它的每个结点的值至少和该结点的儿子们（如果存在的话）的值一样大
（ max-堆）（或小,min-堆）。
④ 二分检索树,二分检索树Ｔ是一棵二元树，它或者为空，
或者每个结点含有一个可以比较大小的数据元素，且有：
· Ｔ的左子树的所有元素比根结点中的元素小；
· Ｔ的右子树的所有元素比根结点中的元素大；
· Ｔ的左子树和右子树也是二分检索树。
注：二分检索树要求树中所有结点的元素值 互异
2009-7-26
3,图图Ｇ 结点集Ｖ和边集Ｅ组成，记为
G=（ V,E）
其中，Ｖ是一个 有限非空 的结点集合；Ｅ是结点 对偶 的集合，Ｅ的每一对偶表示Ｇ的一条边。
2009-7-26
有关图的的重要概念
无向图,边表示为（ｉ，ｊ）
有向图,边表示为 〈 ｉ，ｊ 〉
成本,带有成本的图称为网络（带权图）
邻接
结点的度（出度／入度 ）
路径,由结点 vp到 vq的一条路（ path）是结点
vp,vi1,vi2,?,vim,vq的一个序列，它使得
( vp,vi1 ),( vi1,vi2 ),?,( vim,vq )
是 E（ G）的边。
路的长度,组成路的边数。
2009-7-26
简单路径,除了第一和最后一个结点可以相同以外，其它所有结点都不同。
环,第一个和最后一个结点相同的简单路。
连通图,在无向图中，如果每对结点之间都存在一条路径，则称该图是连通的。
子图,是由 G的结点集 V的子集（记为 VB）和边集 E中连接 VB
中结点的边的子集所组成的图。
连通分图,一个图的最大连通子图。
有向图的强连通性,在有向图中，如果对于每一对结点 i和 j，
既存在一条从 i到 j的路，又存在一条从 j
到 i的路，则称该有向图是强连通的。
2009-7-26
图的表示方法
邻接矩阵 邻接表
2009-7-26
1.5 递归和消去递归
1,递归
递归是一种强有力的设计方法
递归的效率问题
2009-7-26
例 1.3 斐波那契 (Fibonacci)序列：
F0 = F1 = 1
Fi = Fi-1 + Fi-2 （ i>1)
算法 1.7 求斐波那契数
procedure F(n)
//返回第 n个斐波那契数 //
integer n
if n<= 1 then return(1)
else return(F(n-1) + F(n-2))
endif
end F
算法效率：对 F(n-2),F(n-3),… 存在大量的重复计算
改 进：保存中间结果
2009-7-26
例 1.4 欧几里得算法已知两个非负整数 a和 b，且 a＞ b≥0,求这两个数的最大公因数。
辗转相除法,若 b=0，则 a和 b的最大公因数等于 a；若 b＞ 0，
则 a和 b的最大公因数等于 b和用 b除 a的余数的最大公因数。
算法 1.8 求最大公因数
procedure GCD(a,b) // 约定 a>b //
if b=0 then return(a)
else return (GCD(b,a mod b))
endif
end GDC
例,GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;
2009-7-26
例 1.5 用递归策略设计的检索算法已知元素 x和元素表 A（ 1,n），判断 x是否等于 A中某元素的值。
算法 1.9 在 A（ 1,n）中检索 x
procedure SEARCH(i)
//如果在 A（ 1,n） //中有一元素 A（ k） =x，则将其第一次出现的下标 k返回，
否则返回 0//
global n,x,A(1:n)
case
:i>n,return(0)
:A(i) = x; return(i)
:else,return(SEARCH(i+1))
endcase
end SEARCH
0 u<v
T(A,v,u,x)= av u≥v,av = x
T(A,v+1,u,x) u≥v,av≠ x
2009-7-26
2,消去递归直接递归的消去规则,
基本思路,将递归调用的地方用等价的 非递归代码 来代替，并对 return语句 做适当处理。
13条规则,处理直接递归调用和 return语句，将之转换成等价的迭代代码。
初始化
⑴ 在过程的开始部分，插入说明为 栈 的代码并将其初始化为空,StackType Stack[1..SIZE]
Top ← 0
在一般情况下，这个栈用来存放参数、局部变量和函数的值、
每次递归调用的返回地址。
2009-7-26
⑵ 将标号 L1附于第一条可执行语句。
．．．
L1：第一条可执行语句
．．．
然后对于每一处递归调用都用一组执行下列规则的指令来代替。
2009-7-26
处理 递归调用 语句
⑶ 将所有参数和局部变量的值存入栈。
Top ← Top +1
Stack[Top] ←?
栈顶指针 可作为一个全程变量来看待。
⑷ 建立第 i个新标号 Li，并将标号的下标 i存入栈。这个标号的
i值将用来计算返回地址。
Top ← Top +1
Stack[Top] ← i
此标号放在规则⑺所描述的程序段中。
保存现场
2009-7-26
⑸ 计算这次调用的各实在参数（可能是表达式）的值，
并把这些值赋给相应的形式参数。
⑹ 插入一条无条件转向语句转向过程的开始部分：
goto L1
(以上完成一次递归调用 )
2009-7-26
对 退出点 的处理
⑺ 如果这过程是 函数,则对递归过程中含有此次函数调用的那条语句做如下处理：将该语句的此次 函数调用 部分用从栈顶取回该函数值的代码来代替，其余部分的代码按原描述方式照抄，
并将⑷中建立的标号附于这条语句上。
goto L1
Li,x←Stack(Top)
Top← Top -1
A(．．,)
．．．
x← A(,．,)
．．．
end A
2009-7-26
如果此过程不是函数，则将⑷中建立的标号附于⑹所产生的转移语句后面的那条语句。
goto L1
Li,S
B(．．,)
．．．
B(．．,)
S
．．．
end B
2009-7-26
以上步骤消去过程中的 递归调用 。
下面对过程中出现 return语句 进行处理。
注,纯过程结束处的 end可看成是一条没有值与之联系的
return语句
2009-7-26
对每个有 return语句的地方，执行下述规则：
⑻ 如果栈为 空,则执行 正常返回 。
if top ＝ 0 then return(?)
⑼ 否则，将所有输出参数（带有返回值的出口参数，
out/ inout型）的当前值赋给栈顶上的那些对应的变量。
Stack[n] ←?
2009-7-26
⑽ 如果栈中有返回 地址标号 的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未使用的变量。
addr ← Stack[Top]
Top ← Top -1
⑾ 从栈中退出所有局部变量和参数的值并把它们赋给对应的变量。
2009-7-26
⑿ 如果这个过程是函数，则插入以下指令，这些指令用来计算紧接在 return后面的表达式并将结果值存入栈顶。
Top ← Top +1
Stack[Top] ← 表达式的值
⒀ 用返回地址标号的下标实现对该标号的转向。
if addr ＝ i then goto Li
2009-7-26
例 1.6 递归调用示例求数组元素中的最大值算法 1.10 求取数组元素的最大值（递归算法）
procedure MAX1(i)
// 查找数组 A中最大值元素，并返回该元素的 最大下标 。 //
global integer n,A(1:n),j,k
integer i
if i<n then j←MAX1(i+1) //递归调用 //
if A(i) > A(j) then k←i
else k←j
endif
else k←n
endif
return(k) //递归调用的返回 //
end MAX1
max(a1,…,a n)
= max(a1,max(a2,…,a n))
2009-7-26
消去上例中的递归算法 1.11 使用上述的规则消去例 1.10中的递归代码
procedure MAX2(i)
local integer j,k; global integer n,A(1:n)
integer i
integer STACK(1:2*n)
top←0 //规则 1，声明栈的代码，并初始化为空 //
L1,if i<n //规则 2，将标号 L1赋于第一条可执行语句前 //
then top ←top + 1; STACK(top)← i; // 规则 3，参数或局部变量的值入栈 //
top ←top +1; STACK(top)← 2; // 规则 4，建立新标号 2，并入栈 //
2009-7-26
i ← i+1 // 规则 5,计算参数值 //
goto L1 //规则 6,无条件转向算法的开始部分 //
L2,j ←STACK(top); top ←top -1; // 规则 7,处理函数调用，
并将标号 2赋于该语句上 //
if A(i) > A(j) then k ←I
else k ←j
endif
else k ←n
endif
2009-7-26
if top = 0 then return(k) // 规则 8,如果栈空，则正常返回 //
else addr ←STACK(top);top ←top -1; // 规则 10,从栈中退出返回标号 //
i ←STACK(top);top ←top -1; // 规则 11,从栈中退出局部变量和参数的值 //
top ←top+1;STACK(top) ← k; // 规则 12,计算返回值，并将之入栈 //
if addr = 2 then goto L2 endif // 规则 13,用返回地址标号的下标实现对该标号的转向 //
endif
end MAX2
2009-7-26
进一步优化和简化经过消去递归产生的迭代程序。
2009-7-26
算法 1.12 算法 1.11的改进模型
procedure MAX3(A,n)
integer i,k,n;
i←k←n
while i>1 do
i←i -1
if A(i)>A(k) then k←i endif
repeat
return(k)
end MAX3
