计算机算法基础 周中成 苏州科技学院应用数学系 2019/4/18.

Presentation on theme: "计算机算法基础 周中成 苏州科技学院应用数学系 2019/4/18."— Presentation transcript:

1 计算机算法基础 周中成 苏州科技学院应用数学系 2019/4/18

2 序 先修课： 高等数学 高等代数 程序设计——使用高级程序语言描述一个 具体算法的基础 数据结构——为表达非数值算法提供了抽 象的运算机制
先修课： 高等数学 高等代数 程序设计——使用高级程序语言描述一个 具体算法的基础 数据结构——为表达非数值算法提供了抽 象的运算机制 数学类 计算机类 2019/4/18

3 结论： 算法是计算机科学和计算机应用的核心，图灵奖得主Donald E. Knuth说：”计算机科学就是算法的研究“
如何编写计算机程序： 数据结构+算法 = 程序 算法：计算机软件的“灵魂” 结论： 算法是计算机科学和计算机应用的核心，图灵奖得主Donald E. Knuth说：”计算机科学就是算法的研究“ 2019/4/18

4 算法分析与设计 刘任任主编 武汉理工大学出版社
教材： 算法分析与设计 刘任任主编 武汉理工大学出版社 参考书： 算法设计技巧与分析 [沙特]M.H.Alsuwaiyel 电子工业出版社 Introduction to The Design & Analysis of Algorithms(算法设计与分析基础)（影印版） [美] Anany Levitin 算法设计与分析 王晓东编著 清华大学出版社 计算机算法导引——设计与分析 卢开澄编著 清华大学出版社 Introduction To Algorithm 高教出版社，MIT Press 学时：51学时 2019/4/18

5 章节安排 第一章 导论 √ 第二章 分治与递归 √ 第三章 贪心算法 √ 第四章 动态规划 √ 第五章 回溯法 ⊙ 第六章 分枝-限界法 ⊙
第一章 导论 √ 第二章 分治与递归 √ 第三章 贪心算法 √ 第四章 动态规划 √ 第五章 回溯法 ⊙ 第六章 分枝-限界法 ⊙ 第八章 NP完全问题 ? 2019/4/18

6 第一章 引论 §1.1 算法的定义及特性 1. 什么是算法（algorithm） 算法如数学、计算一样，是一个基本概念。
第一章 引论 §1.1 算法的定义及特性 1. 什么是算法（algorithm） 算法如数学、计算一样，是一个基本概念。 ★ Webster辞典：“algorithm（算法）在有限步骤内解一个数学问题的过程，步骤中常常包括某一操作的重复。更广义地说，一个算法就是为解一个问题或实现某一目标的逐步过程“ ★D.E.Knuth说：一个算法就是一个有穷规则的集合，其中的规则规定了一个解决某一特定类型的问题的运算序列。此外，它还具有下面第二部分所述的5个重要特征 2019/4/18

7 2. 算法的五个重要特性 1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。
2. 算法的五个重要特性 有穷性、确定性、可行性、输入、输出 1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。 例：菜谱就不是一个算法，因为菜谱中经常有这样的步骤：“加入食盐少许”，这种“少许”是不确定的。 2019/4/18

8 算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在“有限”的时间内完成。
2）可行性 算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在“有限”的时间内完成。 2019/4/18

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

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

11 4。程序与算法 二者关系：程序可以用来描述算法，同一个算法可以用不同语言（c, basic, 汇编）编写的程序来描述。
程序不一定是算法，因为它不一定符合算法的5条性质，如操作系统作为整体是程序，但不是一个算法，因为操作系统是无限循环的过程 2019/4/18

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

13 6. 课程关系 数据结构 程序设计语言：结构化设计 数学基础 非数值计算领域的基本知识 2019/4/18

14 §1.2 分析算法 分析算法的目的及历史背景 目的：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法（主要在时空效率方面）的好坏，从而选择好的算法，改进差的算法。 历史背景：算法分析是计算机领域的“古老”而“前沿”的课题。称为计算复杂性问题，属于计算理论的一个重要领域，它是由于对有效算法的需求而发展起来的，产生于二十世纪六十年代，繁荣于七、八十年代。 2019/4/18

15 算法分析的标准 1。正确性(Correctness)
2。简洁、清晰(Simplicity) 一般而言（并不必然如此），最简单、思路最直接的解决方法效率往往不是最佳的。然而，简洁性也是一个算法值得追求的目标。它可以使验证算法的正确性相对容易，它也使我们编写、调试、修改程序更为容易。当然，若程序使用频率很高，算法的效率还是选择算法的决定性因素。 3。优化性(Optimality) 符合优化性的算法不是已知中最好的（the best known），而是解决问题的一切可能算法中最好的(the best possible)。 4。空间复杂度(Space Complexity) 5。时间复杂性 2019/4/18

16 如何衡量时间复杂性 算法（程序）实际执行时间 程序中的指令或语句的执行次数（频率计数） 课堂问题 ——缺陷： 受运行机器性能的影响
高度依赖于编程语言及程序员的编程风格，并要首先编写调试程序（也要花费精力）。 2019/4/18

17 频率计数 例： 一条语句在整个程序运行时实际执行时间=频率计数 * 每执行一次该语句所需的时间 频率计数：算法中语句或运算的执行次数。
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 x=x2 repeat (a) (b) (c) 分析： (a)： x←x+y执行了1次 (b)： x←x+y执行了n次，x=x2 ，执行一次 (c)： x←x+y执行了n2次，x=x2 ，执行一次 一条语句在整个程序运行时实际执行时间=频率计数 * 每执行一次该语句所需的时间 2019/4/18

18 如何克服上述办法的缺陷？ 我们需要的是衡量一个算法所使用方法、策略的效率的度量，我们要求： a、这个度量要独立于机器；
b、编程语言、程序员， c、我们主要不是关心小规模输入量的情况，而是关心大输入量时的算法运行情况。 2019/4/18

19 正确的解决办法 因此，我们实际上只计算算法中的特定基本操作而省略初始化操作、循环控制及其他操作。这种基本操作一般同实际运行时间是成比例的。
2019/4/18

20 一些基本操作的合理选择 问题1 在数组中查找元素x 基本操作选择： X与数组中元素的比较 问题2 矩阵相乘 基本操作选择： 两个实数相乘
问题2 矩阵相乘 基本操作选择： 两个实数相乘 课堂问题 问题3 排序 基本操作选择： 两个元素的比较 2019/4/18

21 问题：需要精确计算运算次数吗？ 我们分析算法的时间复杂性时，我们的主要目的是将此算法同解决同一问题的其他算法或不同的问题的算法相比较，时间复杂度是相对的而不是绝对的。要精确计算所有运算的次数，如果不是不可能的话，也是非常麻烦的，实际上对于我们的算法分析的实际目的而言也是不必要的。 解决方法：由于我们只对大输入量时的运行情况感兴趣且没必要非常精确地计算运算次数或运算时间，可以只讨论运行时间的增长率或增长的阶。常见的阶有：logn<n<nlogn<n2<n3<2n 2019/4/18

22 示例 有解决同一问题的两个算法A和B，其时间复杂度分别为10n2和n3，当n比较大时，系数10根本不起作用。
10:1 2 40 8 5:1 103 1:1 100 105 106 1:10 1000 107 109 1:100 10000 1012 1:1000 108 1017 1024 1:107 1020 1041 1060 1:1019 2019/4/18

23 算法C时间复杂度为100n2 n 100n2 n3 100n2:n3 1 100 100:1 2 400 8 50:1 10 104 103 10:1 106 1:1 1000 108 109 1:10 10000 1010 1012 1:100 1018 1024 1:106 1020 1042 1060 1:1018 2019/4/18

24 这一点可以从如下数学分析结果看出： 同样的道理可以用于函数f(n)=n3+2n2+5n中（假定是算法D的时间复杂度）的低阶项上。容易看出，随着n的增大，低阶项的影响越来越小。因此，可以说，算法A、B、C、D的时间复杂度分别为n2、n3、n2、n3阶的。 2019/4/18

25 典型的计算时间函数曲线 2019/4/18

26 计算时间函数值比较 3 2019/4/18

27 典型的函数阶 对数函数 logn 线性函数 cn 次平方函数 nlogn 平方函数 n2 立方函数 n3 指数函数 2n 2019/4/18

28 三个形式化表达时间复杂性的 数学符号 2019/4/18

29 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))。 即从n0及以后项，不等式成立。 2019/4/18

30 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))。 即从n0及以后项，不等式成立。 2019/4/18

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

32 例 设f(n)=10n2+20n 显然， f(n)=10n2+20n>n2,n>1,所以有f(n)= Ω(n2)。
因为f(n)=10n2+20n<20n2,n>2,所以有f(n)=O(n2)。 由以上两点可以推出 2019/4/18

33 例 一般地，对一般多项式f(n)=c1nk+c2n(k-1)+…+ckn+ck+1(c1≠0)
f(n)=Ω (nk)。 f(n)=O(nk)。 由以上两点可以推出 2019/4/18

34 最坏情形复杂度 与 平均情形复杂度 即使输入量大小相同，不同的输入数据会导致基本运算执行次数也不同，有时候还差别很大。考虑一个简单的问题，即在无序数组a[1:n]中查找元素x，我们采用从前向后顺序查找法。（假定x必在数组中）若x在数组开头a[1]，则只需一次比较运算；若x在数组末尾a[n]，则要n次比较运算；很明显，同样的输入规模（都有n个输入量），但不同情况下要用的运算次数明显差异很大，上述问题中最坏情形下要用n次比较运算。当然（这是最坏情形复杂度），我们可能对平均情况下的比较次数更感兴趣（这是平均情形复杂度）。 2019/4/18

35 最坏情形复杂度与平均情形复杂度的形式化定义
符号的约定 Dn是对于所考虑问题来说输入大小为n的输入集合； I是Dn的一个元素， p(I)为I出现的概率， t(I)是算法在输入I时所执行的基本运算次数。 例如：在无序数组中查找查找元素问题中，Dn即表示有n个元素的所有可能情形。 2019/4/18

36 算法的平均情形复杂度 算法的最坏情形复杂度
描述算法的一般情况下的表现，但必须要首先知道输入数据的出现概率，可能要经过大规模的统计，不一定容易得到，另外，平均情形复杂度的计算也可能是个数学难题 A（n）=∑ p(I) t(I) (I属于Dn) 算法的最坏情形复杂度 W（n）=max{ t(I)} (I属于Dn) 描述算法在最坏情况下的表现，相对容易计算，在无法计算平均情形复杂度时，只能计算最坏情形复杂度，并以之作为度量算法效率的表准 2019/4/18

37 例 顺序搜索无序表 输入 E(含n个元素的序列) n（序列E中元素个数） K（搜索元素，设为整数，E[i]也设为整数） 输出
2019/4/18

38 算法 基本操作：K同E中元素的比较 int seqSearch(int[] E,int n,int K) { int ans,index;
for(index=0;index<n;index++) if(K==E(index)) { ans=index; break; } return ans; 基本操作：K同E中元素的比较 2019/4/18

39 最坏情形复杂度 显然，当K在序列末尾或不在序列中，需要比较n次， 所以W（n）=n 2019/4/18

40 平均情形复杂度 假定序列中元素互不相同；若K在此序列中，假定K在序列中的位置是等可能的。 Ii：代表K在位置i的所有输入
A1(n)= = = 在查找成功的情形下，平均比较次数约为序列长度的一半，这同我们的直觉是相符的。 2019/4/18

41 综合上述两种情形（K在序列与不在序列中）
元素不在序列中的情形 显然，此时平均情形复杂度为A2(n)=n 综合上述两种情形（K在序列与不在序列中） A(n)=Pr(查找成功时)A1(n)+Pr(查找不成功时)A2(n) 设查找成功的概率为q，而查找不成功的概率显然为1-q， 2019/4/18

42 a.q=1(K必在序列中) b.q=0(K必不在序列中) A(n)= n c.q=1/2(K在序列中概率为一半) A(n)=（n+1）/2
2019/4/18

43 § 1.3 关于类c语言与类Pascal语言——SPARKS语言
结构化设计 经常作为教学用语言 2019/4/18

44 1. 基本语法成分 2）变量声明 类型说明符 变量； integer i,j; boolean b; 1）数据类型 char c
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 2019/4/18

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

46 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 2019/4/18

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

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

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

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

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

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

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

54 2019/4/18

55 特殊形态的二元树 ① 满二元树：深度为k且有2k-1个结点的二元树 2019/4/18

56 ② 完全二元树：一棵有n个结点深度为k的二元树，当它的
完全二元树的叶子结点至多出现在相邻的两级上。 完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理1.2）。 2019/4/18

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

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

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

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

61 图的表示方法 邻接矩阵 邻接表 2019/4/18

62 1.5 递归和消去递归 1. 递归 递归是一种强有力的设计方法 递归的效率问题 2019/4/18

63 if n<= 1 then return(1) else return(F(n-1) + F(n-2)) end if 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)) end if end F 算法效率：对F(n-1) 、F(n-2)存在大量的重复计算 改 进：保存中间结果 2019/4/18

64 已知两个非负整数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; 2019/4/18

65 已知元素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 2019/4/18

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

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

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

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

70 // 查找数组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 2019/4/18

71 消去上例中的递归 算法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，并入栈// 2019/4/18

72 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 2019/4/18

73 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 2019/4/18

74 进一步优化和简化经过消去递归产生的迭代程序。
2019/4/18