华中科技大学计算机学院 韩建军 jasonhan@mail.hust.edu.cn 计算机算法基础 华中科技大学计算机学院 韩建军 jasonhan@mail.hust.edu.cn 2017/2/25.

Presentation on theme: "华中科技大学计算机学院 韩建军 jasonhan@mail.hust.edu.cn 计算机算法基础 华中科技大学计算机学院 韩建军 jasonhan@mail.hust.edu.cn 2017/2/25."— Presentation transcript:

1 华中科技大学计算机学院 韩建军 jasonhan@mail.hust.edu.cn
计算机算法基础 华中科技大学计算机学院 韩建军 2017/2/25

2 序 专业基础课程： 数据结构、计算机语言 操作系统、编译 如何编写计算机程序： 数据结构+算法 = 程序 算法：计算机软件的“灵魂”
算法是计算机科学和计算机应用的核心 2017/2/25

3 计算机算法基础 余祥宣等编著 华中科技大学出版社 参考书： 算法设计与分析 王晓东编著 清华大学出版社
教材： 计算机算法基础 余祥宣等编著 华中科技大学出版社 参考书： 算法设计与分析 王晓东编著 清华大学出版社 计算机算法导引——设计与分析 卢开澄编著 清华大学出版社 Introduction To Algorithm 高教出版社，MIT Press 学时：36+4学时 2017/2/25

4 章节安排 第一章 导引与基本数据结构 √ 第二章 分治法 √ 第三章 贪心方法 √ 第四章 动态规划 √ 第五章 检索与周游 √
第一章 导引与基本数据结构 √ 第二章 分治法 √ 第三章 贪心方法 √ 第四章 动态规划 √ 第五章 检索与周游 √ 第六章 回溯法 ⊙ 第七章 分枝-限界 ⊙ 第八章 NP-问题 ? 2017/2/25

5 第一章 导引与基本数据结构 1.1 算法的定义及特性 1. 什么是算法？ ★ 算法如数字、计算一样，是一个基本概念。
第一章 导引与基本数据结构 1.1 算法的定义及特性 1. 什么是算法？ ★ 算法如数字、计算一样，是一个基本概念。 ★ 算法是解一确定类问题的任意一种特殊的方法。 ★ 在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词； 算法是一组有穷的规则，它规定了解决某一特定类型 问题的一系列运算。 2017/2/25

6 2. 算法的五个重要特性 1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。 例：不符合确定性的运算 5/0 将6或7与x相加
2. 算法的五个重要特性 确定性、能行性、输入、输出、有穷性 1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。 例：不符合确定性的运算 5/0 将6或7与x相加 未赋值变量参与运算 2017/2/25

7 算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在“有限”的时间内完成。
2）能行性 算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在“有限”的时间内完成。 例：整数的算术运算是“能行”的 实数的算术运算是“不能行”的 2017/2/25

8 3）输入 4）输出 每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域（或值域）
一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。 2017/2/25

9 5）有穷性 一个算法总是在执行了有穷步的运算之后终止。 计算过程：只满足确定性、能行性、输入、输出四个特性的一组规则。
算法和计算过程的区别： 计算过程：操作系统(不终止的运行过程) 算法是“可以终止的计算过程” 算法的时效性：只能把在相当有穷步内终止的算法投 入到计算机上运行 2017/2/25

10 4. 我们的主要任务 算法学习将涉及5个方面的内容： 1）设计算法：创造性的活动 2）表示算法：思想的表示形式，SPARKS语言
3）确认算法：证明算法对所有可能的合法输入都能得出正确的答案。 算法证明：证明算法的正确性，与语言无关 程序证明：证明程序的正确性 4）分析算法：对算法的时、空特性做定量分析，以了解算法的好坏 5）测试程序： 调试：“调试只能指出有错误，而不能指出它们不存在错误” 作时空分布图：验证分析结论，优化算法设计 本课程集中于学习算法的设计与分析。通过学习，掌握计算机算法设计和分析基本策略与方法，为设计更复杂、更有效的算法奠定基础 2017/2/25

11 5. 课程关系 数据结构 程序设计语言：结构化设计 数学基础 非数值计算领域的基本知识 2017/2/25

12 1.2 分析算法 1. 分析算法的目的 在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。 算法分析是计算机领域的古老而前沿的课题。 2017/2/25

13 2. 重要的假设和约定 1）计算机模型的假设 计算机形式理论模型： Turing机模型 通用计算机模型： 顺序计算机 有足够的“内存”
能在固定的时间内存取数据单元 2017/2/25

14 2）计算的约定 从运算的“时间特性”上将运算的分类： 算法的执行时间=∑fi*ti
其中，fi是算法中用到的某种运算i的次数——称为该运算的“频率计数” ti是该运算执行一次所用的时间 —— 与程序语言和硬件有关 确定：使用何种运算及其执行时间。 从运算的“时间特性”上将运算的分类： 时间囿界于常数的运算： ·基本算术运算，如整数、浮点数的加、减、乘、除 ·字符运算、赋值运算、过程调用等 特点：尽管每种运算的执行时间不同，但一般只花一个 固定量的时间（单位时间）就可完成。 2017/2/25

15 2）计算的约定（续） 其他运算： ·字符串操作：与字符串中字符的数量成正比 ·记录操作：与记录的属性数、属性类型等有关
特点：运算时间无定量。 如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。 如：tstring = Length（String）* tchar 2017/2/25

16 3）工作数据集的选择 编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。
编制测试数据是程序测试与算法分析中的关键技术之一。 ·作为算法分析的数据集：反映算法的典型特征 ·作为程序正确性及性能测试的数据集：测试程序的对错，反映对性能指标产生影响的方面,如边界值 2017/2/25

17 3. 如何进行算法分析？ 对算法进行全面分析，可分两个阶段进行： 事前分析：就算法本身，通过对其执行性能的“理论”分析，
得出关于算法特性——时间和空间的一个特征 函数（Ο、Ω）——与计算机物理软硬件没有 直接关系。 事后测试：将算法编制成程序后实际放到计算机上运行， 收集其执行时间和空间占用等统计资料，进行 分析判断——直接与物理实现有关。 2017/2/25

18 算法的执行时间=∑fi*ti 1）事前分析 目的：试图得出关于算法特性的一种形式描 述，以“理论上”衡量算法的“好坏”。
如何给出反映算法特性的描述？ 统计算法中各种运算的执行情况，包括： 引用了哪些运算 每种运算被执行的次数 该种运算执行一次所花费的时间等。 算法的执行时间=∑fi*ti 2017/2/25

19 频率计数 例： 频率计数：算法中语句或运算的执行次数。 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 (a) (b) (c) 分析： (a)： x←x+y执行了1次 (b)： x←x+y执行了n次 (c)： x←x+y执行了n2次 2017/2/25

20 在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。
一条语句在整个程序运行时实际执行时间= 频率计数 * 每执行一次该语句所需的时间 在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。 2017/2/25

21 —— 用来衡量频率计数的“大小”的一种测度 语句的数量级：语句的执行频率 例：1，n ，n2
算法的数量级：算法所包含的所有语句的执行频率之和。 数量级反映了算法复杂度的最本质的特征。 例：假如求解同一个问题的三个算法分别具有n， n2 ， n3数量级。 若n=10，则可能的执行时间将分别是10，100，1000个单 位时间——与环境因素无关。 2017/2/25

22 空间特性分析（与时间特性的分析类似，略）
频率计数的函数表示 就计算时间而言，事前分析阶段求得算法在频率计数 上的函数表示——与规模n有关的函数形式，记为： g(n) ★ 不同的算法，g(n)的具体形式是不同的，如 logn，nlogn，n2等 ★ g(n)的一般形式：关于n的简单函数式 “实际”能够得到的： 1) 函数式的最高次项 2)最高次项与函数整体的关系。 空间特性分析（与时间特性的分析类似，略） 2017/2/25

23 2）事后测试 目的：运行程序，确定程序实际耗费的准确的时间与空间，与事前分析的结论进行比较，验证先前的分析结论——包括正确性、执行性能等，比较、优化所设计的算法。 分析手段：作时、空性能分布图 2017/2/25

24 4. 计算时间的渐近表示 记：算法的实际计算时间为f(n)，计算时间的限界函数为g(n) 其中， n是输入或输出规模的某种测度。
g(n)是事前分析的结果——一个形式简单的函数，如nm，logn，2n，n!等。是与频率计数有关、而与机器及语言无 关的函数。 以下给出算法执行时间：上界（О）、下界（Ω）、“平均”（ ）的定义。 2017/2/25

25 1）上界函数 定义1 如果存在两个正常数c和n0，对于所有的n≥n0，有 |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))。 2017/2/25

26 定理1 若A(n) = amnm+…+a1n+a0是一个m次多项式，则有 A(n) = Ο(nm)
多项式定理 定理1 若A(n) = amnm+…+a1n+a0是一个m次多项式，则有 A(n) = Ο(nm) 即：变量n的固定阶数为m的任一多项式，与此多项式的最高阶 nm同阶。 证明：取n0=1,当n≥n0时，有 |A(n)|≤|am|nm+…+|a1|n+|a0| ＝ (|am|+|am-1|/n+…+|a0|/nm) nm ≤ (|am|+|am-1|+…+|a0|) nm 令c= |am|+|am-1|+…+|a0| 则，定理得证。 2017/2/25

27 计算时间的数量级的大小对算法的有效性有决定性的影响
例：假设解决同一个问题的两个算法，它们都有n个输入, 计算时间的数量级分别是n2和nlogn。则， n=1024：分别需要 和10240次运算。 n=2048：分别需要 和22528次运算。 分析： ★ 同等规模下的计算量比较： ★ 规模增大情况下的比较：在n加倍的情况下，一个Ο(n2)的算法计算时间增长4倍，而一个Ο(nlogn)算法则只用两倍多一点的时间即可完成。 2017/2/25

28 多项式时间算法和指数时间算法 多项式时间算法：可用多项式（函数）对其计算时间限界 的算法。 常见的多项式限界函数有：
Ο(1) < Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n2) < Ο(n3) 指数时间算法：计算时间用指数函数限界的算法 常见的指数时间限界函数： Ο(2n) < Ο(n！) < Ο(nn) 说明：当n取值较大时，指数时间算法和多项式时间算法在计算时 间上非常悬殊。 2017/2/25

29 典型的计算时间函数曲线 2017/2/25

30 一般认识 当数据集的规模很大时，要在现有的计算机系统上运行 具有比Ο(nlogn)复杂度还高的算法是比较困难的。
要想在顺序处理机上扩大所处理问题的规模，有效的途径 是降低算法的计算复杂度，而不是（仅仅依靠）提高计算 机的速度。 2017/2/25

31 计算时间函数值比较 3 2017/2/25

32 2）下界函数 定义1.2 如果存在两个正常数c和n0，对于所有的n≥n0， 有 |f(n)| ≥ c|g(n)|
则记作f(n) = Ω(g(n)) 含义： 如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个下界函数。 试图求出“最大”的g(n)，使得f(n) = Ω(g(n))。 2017/2/25

33 3）“平均情况”限界函数 定义1.3 如果存在正常数c1，c2和n0，对于所有的n≥n0，有
c1|g(n)| ≤|f(n)| ≤ c2|g(n)| 则记作 含义： 算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作： 既有 f(n) = Ω(g(n))，又有f(n) = Ο(g(n)) 2017/2/25

34 4）限界函数的性质 1）若 且 ，则 。即О具有传递性。（ 同） 2） 当且仅当 3）若 ，则 。即， 定义了一个等价关系（等价类） 证明：
1）若 且 ，则 。即О具有传递性。（ 同） 2） 当且仅当 3）若 ，则 。即， 定义了一个等价关系（等价类） 证明： 从定义出发。证明过程略。 2017/2/25

35 5. 常用的整数求和公式 在算法分析中，在统计语句的频率时，求和公式的一般形式为： 如： 2017/2/25

36 1.3 关于SPARKS语言 本书为描述算法选用的一种计算机语言 类PASCAL语言 结构化设计 2017/2/25

37 1. 基本语法成分 2）变量声明 类型说明符 变量； integer i,j; 1）数据类型 boolean b; 整型 integer
1. 基本语法成分 2）变量声明 类型说明符 变量； integer i,j; boolean b; char c 3）数组 任意整数下标 integer A(1:5,7:20) integer B(5,7:20) 1）数据类型 整型 integer 实型 float 布尔型 boolean 字符型 char 2017/2/25

38 4）赋值运算 （变量）←（表达式） x ← 2 + x; 5）逻辑运算：and or not 6）关系运算：＜ ≤ ＝ ≠ ≥ ＞
6）关系运算：＜ ≤ ＝ ≠ ≥ ＞ 2017/2/25

39 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 until cond repeat ·for vble←start to finish by increment do 2017/2/25

40 8) 函数的定义与调用 过程定义 procedure NAME((参数表)) （说明部分） S end NAME
过程的调用： CALL 过程名 函数定义 类型名 function NAME((参数表)) return (表达式) 函数的引用：x ← function（参数）； 2017/2/25

41 c）根据是否带入、带出数据值/结果分类： in型变量 out型变量 inout型变量 边界效应：改变了参变量或全程变量的值
9) 变量的分类 a）根据数据类型分类 整型、实型、字符型等 b）根据作用域分类： 全程变量、局部变量、形式参数 c）根据是否带入、带出数据值/结果分类： in型变量 out型变量 inout型变量 边界效应：改变了参变量或全程变量的值 函数：通过函数值返回输出结果，没有边界效应 纯过程：没有函数值返回，只通过边界效应带出输出结果 2017/2/25

42 10) 特殊语句 a）exit 退出当前一层的循环 b）return 退出过程 return(表达式) : 函数返回结果
c）goto 无条件转向语句 goto label 11) 递归 a）直接递归：过程中包含对自身的调用 b）间接递归：间接调用自身 12) 输入输出 read、print 13）注释 //注释// 2017/2/25

43 1.4 基本数据结构 1. 栈和队列 线性表： n个元素的有序表 栈和队列：特殊的线性表 利用动态数据结构——链表实现栈或队列
1.4 基本数据结构 1. 栈和队列 线性表： n个元素的有序表 栈和队列：特殊的线性表 利用动态数据结构——链表实现栈或队列 利用静态数据结构——数组实现栈或队列 基于以上两种表示形式的栈和队列上的基本运算 2017/2/25

44 2. 树 定义1.4 树（tree）是一个或多个结点的有限集合，它使得： 有一个指定为根（root）的结点
2. 树 定义1.4 树（tree）是一个或多个结点的有限集合，它使得： 有一个指定为根（root）的结点 剩余结点被划分成m≥0个不相交的集合： T1，…，Tm 这些集合的每一个又都是一棵树，并称T1，…，Tm为根的子树。 2017/2/25

45 关于树的重要概念 结点的度（degree）：一个结点的子树数 树的度：树中结点度的最大值
结点的级（level）（又叫层）：设根是1级，若某结点在p级，则它的儿子在p+1级 树的高度（或深度）：树中结点的最大级数 叶子（终端结点）：度为0的结点 内结点（非终端结点）：度不为0的结点 森林：m≥0个不相交树的集合。 2017/2/25

46 定义1.5 二元树（binary tree）是结点的有限集合，它或者为空，或者由一个根和两棵称为左子树和右子树的不相交二元树所组成。
3 二元树 定义1.5 二元树（binary tree）是结点的有限集合，它或者为空，或者由一个根和两棵称为左子树和右子树的不相交二元树所组成。 二元树与度为2的树的区别 二元树性质： 引理1.1 一棵二元树第 i级的最大结点数是2i-1。深度为k的二元树的最大结点数为2k-1,k>0。 2017/2/25

47 2017/2/25

48 特殊形态的二元树 ① 满二元树：深度为k且有2k-1个结点的二元树 2017/2/25

49 ② 完全二元树：一棵有n个结点深度为k的二元树，当它的 结点相当于深度为k的满二元树中编号为1到 n的结点时，称该二元树是完全的。
完全二元树的叶子结点至多出现在相邻的两级上。 完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理1.2）。 2017/2/25

50 ③ 堆：堆是一棵完全二元树，它的每个结点的值至少和 该结点的儿子们（如果存在的话）的值一样大 （ max-堆）（或小， min-堆）。
　③ 堆：堆是一棵完全二元树，它的每个结点的值至少和 该结点的儿子们（如果存在的话）的值一样大 （ max-堆）（或小， min-堆）。 　④　二分检索树：二分检索树Ｔ是一棵二元树，它或者为空， 或者每个结点含有一个可以比较大小的数据元素，且 有： 　　　·Ｔ的左子树的所有元素比根结点中的元素小； 　　　·Ｔ的右子树的所有元素比根结点中的元素大； 　　　·Ｔ的左子树和右子树也是二分检索树。 　注：二分检索树要求树中所有结点的元素值互异 2017/2/25

51 3. 图 图Ｇ由称之为结点Ｖ和边Ｅ的两个集合组成，记为 G=（V，E）
其中，Ｖ是一个有限非空的结点集合；Ｅ是结点对偶的集合，Ｅ的每一对偶表示Ｇ的一条边。 2017/2/25

52 有关图的的重要概念 无向图：边表示为（ｉ，ｊ） 有向图：边表示为〈ｉ，ｊ〉 成本：带有成本的图称为网络（带权图） 邻接
结点的度（出度／入度） 路径：由结点vp到vq的一条路（path）是结点 vp ， vi1 ， vi2 ， … ， vim ， vq的一个序列，它使得 ( vp ， vi1 ) ，( vi1 ，vi2 ) ， … ，( vim ， vq ) 是E（G）的边。 路的长度：组成路的边数。 2017/2/25

53 简单路径：除了第一和最后一个结点可以相同以外，其它 所有结点都不同。 环：第一个和最后一个结点相同的简单路。
连通图：在无向图中，如果每对结点之间都存在一条路径，则 称该图是连通的。 子图：是由G的结点集V的子集（记为VB）和边集E中连接VB 中结点的边的子集所组成的图。 连通分图：一个图的最大连通子图。 有向图的强连通性：在有向图中，如果对于每一对结点i和j， 既存在一条从i到j的路，又存在一条从j 到i的路，则称该有向图是强连通的。 2017/2/25

54 图的表示方法 邻接矩阵 邻接表 2017/2/25

55 1.5 递归和消去递归 1. 递归 递归是一种强有力的设计方法 递归的效率问题 2017/2/25

56 if n<= 1 then return(1) else return(F(n-1) + F(n-2)) endif end F
例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-1) 、F(n-2)存在大量的重复计算 改 进：保存中间结果 2017/2/25

57 已知两个非负整数a和b，且a＞b≥0，求这两个数的 最大公因数。
例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; 2017/2/25

58 已知元素x和元素表A（1：n），判断x是否等于A中 某元素的值。
例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 2017/2/25

59 2. 消去递归 直接递归的消去规则： 基本思路：将递归调用的地方用等价的非递归代码来代替，并对return语句做适当处理。
2. 消去递归 直接递归的消去规则： 基本思路：将递归调用的地方用等价的非递归代码来代替，并对return语句做适当处理。 13条规则：处理直接递归调用和return语句，将之转换成等价的迭代代码。 初始化 ⑴ 在过程的开始部分，插入说明为栈的代码并将其初始化为空。在一般情况下，这个栈用来存放参数、局部变量和函数的值、每次递归调用的返回地址。 ⑵ 将标号L1附于第一条可执行语句。然后对于每一处递归调用都用一组执行下列规则的指令来代替。 2017/2/25

60 ⑷ 建立第i个新标号Li，并将i存入栈。这个标号的i值将用来计算返回地址。
处理递归调用语句 ⑶ 将所有参数和局部变量的值存入栈。 栈顶指针可作为一个全程变量来看待。 ⑷ 建立第i个新标号Li，并将i存入栈。这个标号的i值将用来计算返回地址。 此标号放在规则⑺所描述的程序段中。 ⑸ 计算这次调用的各实在参数（可能是表达式）的值，并把这些值赋给相应的形式参数。 ⑹ 插入一条无条件转向语句转向过程的开始部分： goto L1 2017/2/25

61 ⑺ 如果这过程是函数，则对递归过程中含有此次函数调用 的那条语句做如下处理：将该语句的此次函数调用部分用从栈顶
对退出一层递归调用后的处理 ⑺ 如果这过程是函数，则对递归过程中含有此次函数调用 的那条语句做如下处理：将该语句的此次函数调用部分用从栈顶 取回该函数值的代码来代替，其余部分的代码按原描述方式照抄，并将⑷中建立的标号附于这条语句上。 如果此过程不是函数，则将⑷中建立的标号附于⑹所产生的转移语句后面的那条语句。 以上步骤消去过程中的递归调用。下面对过程中出现return语句进行处理。 （纯过程结束处的end可看成是一条没有值与之联系的return语句） 2017/2/25

62 对每个有return语句的地方，执行下述规则： ⑻ 如果栈为空，则执行正常返回。
⑼ 否则，将所有输出参数（带有返回值的出口参数，out/ inout型）的当前值赋给栈顶上的那些对应的变量。 ⑽ 如果栈中有返回地址标号的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未使用的变量。 ⑾ 从栈中退出所有局部变量和参数的值并吧它们赋给对应的变量。 ⑿ 如果这个过程是函数，则插入以下指令，这些指令用来计算紧接在return后面的表达式并将结果值存入栈顶。 ⒀ 用返回地址标号的下标实现对该标号的转向。 2017/2/25

63 // 查找数组A中最大值元素，并返回该元素的最大下标。// global integer n,A(1:n),j,k integer i
例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 return(k) //递归调用的返回// end MAX1 2017/2/25

64 消去上例中的递归 算法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，并入栈// 2017/2/25

65 goto L1 //规则6， 无条件转向算法的开始部分//
i ←i // 规则5， 计算参数值// goto L //规则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 2017/2/25

66 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 2017/2/25

67 进一步优化和简化经过消去递归产生的迭代程序。
2017/2/25