4.5 递归算法与递归程序（一、二）
教者：吴艳超时间：
一、课程内容标准：
递归算法与问题解决：
1、了解使用递归法设计算法的基本过程
2、能够根据具体问题的要求，使用递归设计算法、编写递归函数、编写程序、求解问题
例1 写出两个正整数乘积m×n的递归函数。
例2 汉诺塔问题：传说在古代印度的贝拿勒斯圣庙里，安放一块黄铜板，板上插了三根宝石柱，在其中一根宝石柱，自上而下按由小到大的顺序串有64个金盘。这就是汉诺塔游戏。要求将左边柱子上的64个金盘按照下面的规则移到右边的柱子上。规则：（1）一次只能移动一个盘子（2）盘子只能在三个柱子上存放。（3）任何时候大盘不能放在小盘上面。
二、教学目标
1、知识与技能
(1)．认识递归现象。
(2)．使用递归算法解决问题往往能使算法的描述乘法而易于表达
(3)．理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行
2、方法与过程：
本节以斐波那契的兔子问题引入，通过发现先后三个月兔子数量的变化规律入手，导出了F（N）=F(N-1)+F(N+2)(N≥3)递推式。马上介绍斐波那契问题的非递归解决方法，如果加以恰当引导，把两个解法对比，会出现效率高的需要较多的经验和技艺才能写出程序，而程序相对容易写出的是在运行时，但效率却不够高。（在调试程序4-16时可逐步加大月数N，会发出N=40时，明显感觉等待的时间较长，而当N=200时，等待的时间会遥遥无期。）汉诺塔问题是一个经典问题，它著名在使用了递归解法来解决问题。理解这个递归解法是重点，也是难点。
3、情感态度和价值观
结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出提升学生在各个领域的计算机应用水平，提高学生交流和讨论，自己总结获得新的知识能力，培养学生正确寻找解决问题的方法和正确的学习方法。
三、重点难点
1、教学重点
（1）了解递归现象和递归算法的特点。
（2）能够根据问题设计出恰当的递归程序。
2、教学难点
(1)递归过程思路的建立。
(2)判断问题是否适于递归解法。
(3)正确写出递归程序。
四、教学环境
1、教材处理
教材选自《广东省普通高中信息技术选修一：算法与程序设计》第四章第五节，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自定义了一个以递归方式
解决的函数过程。然后利用子过程解决汉诺塔的经典问题。
教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2)和练习(3)，这两道题目的形式相差很远，但方法和答案却都是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。
教学方法采用讲解、探究、任务驱动和学生自主学习相结合
2、预备知识
学生已掌握了用计算机解决问题的过程，掌握了程序设计基础，掌握了解析法、穷举法、查找法、排序法设计程序的技巧。
3、硬件要求
建议本节课在多媒体电脑教室中完成，最好有广播教学系统或投影仪，为拓展学习，学生机应允许上互联网。
五、教学过程
导入：
大家玩汉诺塔游戏：
图4-5(1)汉诺塔游戏的部分界面
这个游戏盘子在A、B、C三根柱子上不停运动，有没有规律，和你在照过镜子时遇到的情况相同吗？
当你往镜子前面一站，镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果甲、乙两面镜子相互面对面放着，你往中间一站，嘿，两面镜子里都有你的千百个“化身”!为什么会有这么奇妙的现象呢?原来，甲镜子里有乙镜子的像，乙镜子里也有甲镜子的像，而且这样反反复复，就会产生一连串的“像中像”。这是一种递归现象。
由同学们总结出递归算法的概念
递归算法：是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
问题
4-16：著名的意大利数学家斐波那契(Fibonacci)在他的著作《算盘书》中提出了一个“兔子问题”：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到年底时将有多少对兔子? (当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖)
我们不难用以前学过的知识设计出如下算法：
②输入计算兔子的月份数：n
②If n < 3 Then c = 1 Else a = 1: b = 1
③i = 3
④ c = a + b：a = b：b = c
⑤i=i+1,如果i≤n则返回④
⑥结束
参考程序如下：
Private Sub Command1_Click()
n = Val(Text1.Text)
If n < 3 Then c = 1 Else a = 1: b = 1
For i = 3 To n
c = a + b
a = b
b = c
Next i
Text2.Text = "第" & n & "月的兔子数目是：" & c
End Sub
图4-5(2)斐波那契兔子程序运行结果图
开动脑筋：我们有没有更简单的方法解决该问题呢？
4.5.1 从斐波那契的兔子问题看递归算法
1．斐波那契的兔子问题子
(1)分析问题。
我们可以根据题意列出表4-3来解决这个问题：
表4—3兔子问题分析表
这个表格虽然解决了斐波那契的兔子问题(年底时兔子的总数是144只)，但仔细观察一下这个表格，你会发现兔子的数目增长得越来越快，如果时间再长，只用列表的方法就会有困难。(例如，你愿意用列表的方法求出5年后兔子的数目吗？)我们需要研究表中的规律，找出一般的方法，去解决这个问题。
交流
仔细研究表4-8，你有些什么发现？每一个月份的大兔数、小兔数与上一个月的数字有什么联系，能肯定这个规律吗？恭喜你，你快成功了？
(2)设计算法。
“兔子问题”很容易列出一条递推式而得到解决。假设第N个月的兔子数目是F(N)，我们有：
F ( N ) =F ( N-1) + F (N-2) ( 当N>=3 )
F ( 1 ) = F ( 2 ) = 1
这是因为每月的大兔子数目一定等于上月的兔子总数，而每个月的小兔子数目一定等于上月的大兔子数目(即前一个月的兔子的数目)。
由上述的递推式我们可以设计出递归程序。递归程序的特点是独立写出一个函数(或子过程)，而这个函数只对极简单的几种情况直接给出解答，而在其余情况下通过反复的调用自身而把问题归结到最简单的情况而得到解答。
空中加油站：
自定义函数的定义格式:
Function procedurename(arguments) [As type]
Statements
End Function
其中的procedurename是函数名，arguments是函数中的参数表，type是函数返回值的数据类型，表示可有可无的部分，statements是过程中的代码
调用函数的格式：
procedurename(arguments)
(3)编写程序。
窗体中开设一个文本框Textl用于填人月数N，设置命令框Commandl，点击它即执行程序求出第N月的兔子数。然后用文本框Text2输出答案。
根据递推式可以写出递归程序如下：
Function Fib(ByVal N As Integer) As Long
If N < 3 Then Fib = 1 Else Fib = Fib(N - 1) + Fib(N - 2)
End Function
Private Sub Command1_Click()
N = Val(Text1.Text)
Text2.Text = "第" & N & "月的兔子数目是：" & Fib(N)
End Sub
(4)调试程序
因为这个算法的效率不高，建议在调试程序时月份数不要大于40。
图4-5(4)斐波那契兔子程序运行结果图
(5)检测结果
挑战自我：（以下部分由学生自己完成）
(1)利用递归方法编写一求N的阶乘。
分析：
根据N!=N*(N-1)*(N-2)*(N-3)*……*3*2*1
可以推出下列式子：
F = n * F(n - 1)
这是一个典型的递归算法，参考程序如下：
Function F(ByVal n As Integer) As Long
If n = 1 Then F = 1 Else F = n * F(n - 1)
End Function
Private Sub Form_Click()
Dim n As Integer
n = Val(InputBox("请输入正整数N：", "求N的阶乘"))
Print "输入的正整数是"; n;
Print "，阶乘是"; F(n)
End Sub
图4-5(5)求阶乘程序的运行结果图
(2)对一正整数N，用数字l和2组成一条加法算式，使其和为N，共可以列出多少条不同的式子？(“l+2”和“2+1”看作是不同的式子)。
算法设计：
假设和为N时可列式子的方法数是F(N)，那么第一个加数可选择1或2。当第一个加数为1时剩下加数的和为N一1，故方法数为F(N一1)；当第一个加数为2时，剩下加数的和为N-2，故方法数为F(N-2)。于是可以得到如下式子：
F = F(n - 1) + F(n - 2)
这是一个典型的递归算法，参考程序如下：参考程序如下：
Function F(ByVal n As Integer) As Long
If n <= 2 Then F = n Else F = F(n - 1) + F(n - 2)
End Function
Private Sub Form_Click()
Dim n As Integer
n = Val(InputBox("请输入正整数N：", "输入式子的总和"))
Print "当总和是"; n; "时"
Print "可以列出不同的由1和2组成的加法式子"; F(n); "条"
End Sub
图4-5(6)书上P136练习2程序运行结果图
(3)罗光明在上楼梯时，有时一步一级楼梯，有时一步两级。如果楼梯有N级，他上完这N级楼梯有多少种不同的方法？
设计算法
假设楼梯级数为N时的方法数是F(N)，那么第一步可选择1或2级楼梯。当第一步为1级时剩下楼梯的级数为N-1，故方法数为F(N-1)；当第一步为2级时，剩下楼梯的级数为N-2，故方法数为F(N-2)。于是可以得到如下式子：
F=F(n-1)+F(n-2)
这是一个典型的递归算法，参考程序如下：程序如下：
Function F(ByVal n As Integer)As Long
If n<=2 Then F=n Else F=F(n-1)+F(n-2)
End Function
Private Sub Form_Click()
Dim n As Integer
n=Val(InputBox("请输入楼梯级数N："，"输人楼梯级数"))
Print "当楼梯级数"；n；"时，"
Print "可以有"；F(n)；"种不同的上楼梯方法。"
End Sub
同学们比较一下你们所做的练习(2)和(3)的程序代码，不知同学们有没有发现一个有趣的现象？为什么会这样？
本节小结：
递归算法的特点
递归过程一般通过函数或子过程来实现。
递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。
递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。
递归算法解决问题的特点：
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
递归算法所体现的“重复”一般有三个要求：
一是每次调用在规模上都有所缩小(通常是减半)；
二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；
三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
第二课时：
导入：
大家玩汉诺塔游戏：
图4-5(7)汉诺塔程序运行界面图
4.5.2 一个应用递归算法解决的问题经典例子
问题
4-17：传说在古代印度的贝拿勒斯神庙，有一块黄铜板上插了3根宝石柱，在其中一根宝石柱自上而下由小到大地叠放着64个大小不等的金盘。一名僧人把这些金盘从一根宝石柱移到另外一根上。僧人在移动金盘时遵守下面3条规则：
第一，一次只能移动一个金盘。
第二，每个金盘只能由一根宝石柱移到另外一根宝石柱。
第三，任何时候都不能把大的金盘放在小的金盘上。
神话说，如果僧人把64个金盘完全地从一根宝石移到了另外一根上，世界的末日就要到了。当然，神话只能当故事来听，世界不可以因为个别人的活动而导致末日。不过，从僧人搬完64个金盘所需时间的角度来说，即使僧人每秒都能移动一个金盘，那也得要几千亿年！
试设计程序，模拟移动金盘的过程。
(1)分析问题。
我们把3根宝石柱分别命名为A、B、C。最初有N个金盘放在A，需要把它们全部按规则移动到B。
当N=1时，直接把金盘从A搬到B就可以了，1次成功。
当N≥2，那么需要利用C柱来过渡。我们假设已经找到一种把N－1个金盘从一根柱搬到另外一根柱的方法，那么，我们只要把N－1个金盘从A搬到C，然后把最大的金盘从A搬到B，最后把C上的N一1个金盘搬到B就可以了。靠递归的思想，我们轻而易举地完成了整个搬动。
(2)设计算法。
我们定义一个过程Hanoi(N，A，B，C)，表示有N个金盘需要从A柱搬到B柱(以C 柱为过渡)。那么完成它只需3步：
①Hanoi(N一1，A，C，B)它的意思是把A柱上的N一1个金盘搬到C柱；
②A→B 它的意思是把一个(最大的)金盘从A柱搬到B柱；
③ Hanoi(N－1，C，B，A)它的意思是把c柱上的N一1个金盘搬到B柱。
空中加油站：
过程定义的格式：
Private Sub procedurename(arguments)
statements
End Sub
其中的procedurename是函数名，arguments是函数中的参数表，statements是过程中的代码
调用过程的格式：
Call procedurename(arguments)
Function函数与Sub过程的几点区别：
① Function函数可以返回一个直到调用程序。
②一般来说，让较大的语句或表达式的右边包含函数过程名和参数（returnvalue=function），这就调用了函数。
③与变量完全一样，函数过程有数据类型，这就决定了返回值的类型。（如果没有AS 子句，缺省的数据类型为Variant。）。
④给procedurename自身赋一个值，就可返回这个值。Function函数返回一个值可成为较大表达式的一部分。
(3)编写程序（引导学生编写程序）。
根据所设计的算法，我们安排窗体如图4-23：
Private Sub Hanoi(n As Integer, ByVal A As String, ByVal B As String, ByVal C As String, t As Long)
If n = 1 Then
Text3.Text = Text3.Text + A + "→" + B + vbCrLf
t = t + 1 '增加变量t用来统计移动次数。
Else
Call Hanoi(n - 1, A, C, B, t)
Text3.Text = Text3.Text + A + "→" + B + vbCrLf
t = t + 1
Call Hanoi(n - 1, C, B, A, t)
End If
End Sub
Private Sub Command1_Click()
Dim t As Long, n As Integer
t = 0
n = Val(Text1.Text)
A = "A"
B = "B"
C = "C"
Call Hanoi(n, A, B, C, t)
Text2.Text = t
End Sub
(4)测试程序
在“金盘数目”的文本框中输入4。
图4-5(9)Hanoi结果示意图
(5)检测结果
挑战自我：（以下部分由学生自己完成）
如来不用递归，可不可以用其它的解决方案？
把A、B、C三柱看作是顺时排列的。C之后又是A，那么搬动过程可以描述为：当搬动次数是奇数时，把最小的金盘移到顺时钟方向的下一根柱子上。当搬动的次数是偶数时则保持最小的金盘不动。而在其他两柱之间把较小的金盘从一根柱子移到另外一根拄子上。不断重复这个过程，即可以完成全部金盘的正确移动。
请同学们设计好该程序。
本节小结：
1、应用递归算法一般都需要调用子过程。
2、子过程的参数，不能安排失当。
3、在子过程中需要包含自我调用(或者几个子过程的相互调用)。
4、对于调用的条件必须清楚，在最初始的简单情形，由人力来获得解答，让递归能够正常结束。
递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。
摘要 软件测试是保证软件质量和可靠性重要手段，在这方面发挥着其它方法不可替代的作用。然而，软件测试是一个复杂的过程，需要耗费巨大的人力、物力和时间，约占整个软件开发成本的40%～50%。因此，提高软件测试工具的自动化程度对于确保软件开发质量、降低软件开发成本非常重要。而提高测试用例生成的自动化程度又是提高测试工具乃至整个测试过程自动化程度的关键所在，本文主要针对这一问题进行了研究和设计。 本文在分析软件测试和算法基本概念的基础上，提出软件测试用例的设计是软件测试的难点之一。论文提出了基于算法的测试用例生成的内含是应用算法来求解一组优化的测试用例，其框架包括了测试环境构造、算法及测试运行环境三部分，论文给出了基于算法的测试用例生成的模型。最后以三角形分类程序为例应用算法进行测试用例生成的模拟，结果显示，应用算法进行测试用例生成可行。 关键词：软件测试测试用例算法
ABSTRACT Software test is the important means that guarantee software quality and reliability，and in this respect，it plays the role that other method cannot replace. However software test is a complex process , it needs to consume huge manpower，material resources and time，which takes the 40%~50% of entire software development cost approximately . Therefore，raising the automation level of software test tool is very important for ensure software development quality and reduction software development cost . And then，the most important is raising the automation level of the test case generation for raising the automation level of test tool and even entire test process，so this paper study and design mainly according to this problem. Based on the analysis of basic concepts of software testing and genetic algorithm, this article proposes that software test case design is one of the difficulties of software testing. Paper presents the inherent in software test case designing based on genetic algorithm is using genetic algorithm to solve a set of optimization test cases, and the framework includes three parts which are test environment construction, genetic algorithm and the environment for test . Paper presents the model of software test case generation based on genetic algorithm. Finally, we take the triangle categorizer as an example, simulate software test case generation based on genetic algorithm. The results display that software test case generation basing on genetic algorithm is possible. KEY WORDS: software test , test case , genetic algorithm
一、教学目标 1、知识与技能 (1)．认识递归现象。 (2)．使用递归算法解决问题往往能使算法的描述乘法而易于表达 (3)．理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4)．认识递归算法往往不是高效的算法。 (5)．了解递归现象的规律。 (6)．能够设计递归程序解决适用于递归解决的问题。 (7)．能够根据算法写出递归程序。 (8)．了解生活中的递归现象，领悟递归现象的既有重复，又有变化的 特点，并 且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 （1）了解递归现象和递归算法的特点。
（2）能够根据问题设计出恰当的递归程序。 2、教学难点 (1)递归过程思路的建立。 (2)判断问题是否适于递归解法。 (3)正确写出递归程序。 三、教学环境 1、教材处理 教材选自《广东省普通高中信息技术选修一：算法与程序设计》第四章第五节，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远，但方法和答案却都是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 教学方法采用讲解、探究、任务驱动和学生自主学习相结合 2、预备知识 学生已掌握了用计算机解决问题的过程，掌握了程序设计基础，掌握了解析法、穷举法、查找法、排序法设计程序的技巧。 3、硬件要求 建议本节课在多媒体电脑教室中完成，最好有广播教学系统或投影仪，为拓展学习，学生机应允许上互联网。 4、所需软件 学生机要安装VB6.0或以上版本。 5、所需课时 2课时（90分钟）
算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i;
递归算法与递归程序 岳西中学：崔世义一、教学目标 1知识与技能 (1) ?认识递归现象。 (2) ?使用递归算法解决冋题往往能使算法的描述乘法而易于表达 (3) ?理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4) ?认识递归算法往往不是咼效的算法。 (5) ? 了解递归现象的规律。 (6) ?能够设计递归程序解决适用于递归解决的问题。 (7) ?能够根据算法写出递归程序。 (8) ? 了解生活中的递归现象，领悟递归现象的既有重复，又有变化的特点，并且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2) 和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 (1) 了解递归现象和递归算法的特点。 (2) 能够根据问题设计出恰当的递归程序。 2、教学难点 (1) 递归过程思路的建立。 (2) 判断冋题是否适于递归解法。 (3) 正确写出递归程序。 三、教学环境 1、教材处理 教材选自《浙江省普通高中信息技术选修：算法与程序设计》第五章，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自 定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习⑵ 和练习
递归调用详解，分析递归调用的详细过程 2009年05月23日星期六 22:52 一、栈 在说函数递归的时候，顺便说一下栈的概念。 栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈在每个程序中都是存在的，它不需要程序员编写代码去维护，而是由运行是系统自动处理。所谓的系统自动维护，实际上就是编译器所产生的程序代码。尽管在源代码中看不到它们，但程序员应该对此有所了解。 再来看看程序中的栈是如何工作的。当一个函数(调用者)调用另一个函数(被调用者)时，运行时系统将把调用者的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用者开始执行时，系统把被调用者的自变量压入到栈中，并把栈指针再向下移，以保证有足够的空间存储被调用者声明的所有自变量。当调用者把实参压入栈后，被调用者就在栈中以自变量的形式建立了形参。被调用者内部的其他自变量也是存放在栈中的。由于这些进栈操作，栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针，以他为参考，用正或负的偏移值来访问栈中的变量。当被调用者准备返回时，系统弹出栈中所有的自变量，这时栈指针移动了被调用者刚开始执行时的位置。接着被调用者返回，系统从栈中弹出返回地址，调用者就可以继续执行了。当调用者继续执行时，系统还将从栈中弹出调用者的实参，于是栈指针回到了调用发生前的位置。 可能刚开始学的人看不太懂上面的讲解，栈涉及到指针问题，具体可以看看一些数据结构的书。要想学好编程语言，数据结构是一定要学的。 二、递归 递归，是函数实现的一个很重要的环节，很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在自己函数调用的下级
科学计算器的科学用法集团文件版本号：（M928-T898-M248-WU2669-I2896-DQ586-M1988）
科学计算器在统计学中的应用一．均差、方差的算法 如图中所圈出的按键是计算均值和方差过程中所需要用的键，下面开始具体的操作讲解。 1.首先进入方差分析的计算模式 打开科学计算器——MODE键——此时会出现三个选项（COMP/SD/REG），直接按数字键2就可以进入方差分析的模式。 PS:观察计算器的顶端位置会出现SD字样，说明已经进入该计算模式 2.录入待计算数据（此处以22，12，54，34，43，23六个数为例） 直接输入第一个数字22——按M+键输入第二个数字12——按M+键输入第三个数字54，依次类推，到最后一个数字结束时按M+键结束 3.进行计算 数据录取完毕之后按shift键（部分计算器是2ndf）——按数字键2此时会出现三个选项x???、x6n和x6n-1，其中第一个就是所求的均值，第三个就是所求的样本方差 点击数字键1然后输入等号就可以得到均值 点击数字键3然后输入等号就可以得到方差 值得注意的是计算完均值需要输出方差的时候需要先按shift键再按数字键3才可以的 此处例子的均值为31.11，方差为15.41 4.强调（恢复初始状态）
在用科学计算器进行均值和方差的计算时，在每次计算完毕之后需要将计算器恢复到默认状态，然后再进行其他的计算。 首先按shift键——然后按MODE键，此时已经进清除状态，界面会显示三个状态，分别是Mcl、Mode和All，选择其中任意一个然后输入=键就完成了相应的清除功能了。 选择2就是清除了方差和均值的计算模式， 选择3则清除了你对计算器所有的设置，回到了默认状态 另外，如果在一次方差和均值计算中不小心输错了数据，则需要首先清除方差均值计算模式，再次进入后重新计算，否则容易出现错误。二．排列组合的运算 排列组合所需要的是nPr、nCr这两个函数,，他们为同一个按键，按 组合：输入过程中先输入数字n的值，然后按nCr键，再输入m值，最后输入等号就可以得到结果咯 排列：输入过程中先输入数字n的值，按shift键，然后再按nCr键，再输入m值，最后输入等号就可以得到结果咯 5——nCr——2=10 5——shift——nCr——2=20 三．对数值的计算
○1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 ○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 边界条件与递归方程是递归函数的二个要素 应用分治法的两个前提是问题的可分性和解的可归并性 以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。 回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。 舍伍德算法设计的基本思想: 设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为 这显然不能排除存在x∈Xn使得的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有 拉斯维加斯( Las Vegas )算法的基本思想: 设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)>0。 设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有： 解此方程可得：
蒙特卡罗(Monte Carlo)算法的基本思想: 设p是一个实数，且1/2 递归算法的实现 【基本信息】 【课标要求】 （三）算法与问题解决例举 1. 内容标准 递归法与问题解决 （1）了解使用递归法设计算法的基本过程。 （2）能够根据具体问题的要求，使用递归法设计算法、编写递归函数、编写程序、求解问题。 【教材分析】 “算法的程序实现”是《算法与程序设计》选修模块第三单元的内容，本节课是“递归算法的程序实现”，前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序以及本节的前一小节知识点“什么是自定义函数”的学习，在学习自定义函数的基础上，学习递归算法的程序实现是自定义函数的具体应用，培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。 『递归算法在算法的学习过程中是一个难点，在PASCAL和C语言等程序语言的学习过程中，往往是将其放在“函数与过程”这一章节中来讲解的。递归算法的实现也是用函数或是过程的自我调用来实现的。从这一点上来讲，作者对教材的分析与把握是准确的，思路是清晰的，目标是明确的。』 【学情分析】 教学对象是高中二年级学生，前面学习了程序设计的各种结构，在学习程序设计各种结构的应用过程中培养了用计算机编程解决现实中问题的能力，特别是在学习循环语句的过程中，应用了大量的“递推”算法。前一节课学习了如何自定义函数，在此基础上学习深入学习和体会自定义函数的应用。以递推算法的逆向思维进行求解问题，在学习过程中体会递归算法的思想过程。多维度的思考问题和解决问题是提高学生的学习兴趣关键。 『递归算法的本质是递推，而递推的实现正是通过循环语句来完成的。作者准确把握了学生前面的学习情况，对递归算法的本质与特征也分析的很透彻，可以说作者对教学任务的分析是很成功的，接来就要看，在成功分析的基础上作者是如何通过设计教学来解决教学难点的了。』 【教学目标】 编译原理课程设计报告 2011 年 12 月 2 日 设计题目 递归下降分析程序的实现 学 号 专业班级 计算机科学与技术 学生姓名 指导教师 一、实验目的: （1）掌握自上而下语法分析的要求与特点。 (2）掌握递归下降语法分析的基本原理和方法。 （3)掌握相应数据结构的设计方法。 二、实验内容: 递归下降分析程序的实现 设计内容及要求： 对文法 G： E→E+T｜Ｔ构造出G的递归下降分析程序。程序显示输出T→T*F|Ｆ匹配过程（即自上而下生成语法分析树的步骤， F→（E）|i 输出各匹配产生式序号即可）。 三、设计思路： (１)语法分析: 语法分析是编译程序的核心部分，任务是分析一个文法的句子结构。递归下降分析程序的实现的功能:按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子（合式程序）。 （2)自上而下分析: 从文法的开始符号出发,向下推导,推出句子。可分为带“回溯”的和不带回溯的递归子程序(递归下降)分析方法。 它的主旨是对任何输入串，试图用一切可能的办法,从文法开始符号(根结点）出发，自上而下地为输入串建立一棵语法树。或者说,为输入串寻找一个最左推导。也即从文法的开始符号出发，反复使用各种产生式，寻找"匹配＂的推导。 (3)递归下降分析法： 对每一语法变量(非终结符)构造一个相应的子程序,每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 (４）分析过程中遇到的问题: a. 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时,不得不“回溯”。 b．文法左递归问题。含有左递归的文法将使自上而下的分析陷入无限循环。 (5)构造不带回溯的自上而下分析算法： ａ.要消除文法的左递归性：一个文法可以消除左递归的条件是①不含以 为右部的产生式②不含回路。 递归算法向非递归算法转换 递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。 将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。 1. 直接转换法 直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。 尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法： long fact(int n) { if (n==0) return 1; else return n*fact(n-1); } 当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法： long fact(int n) { int s=0; for (int i=1; i<=n;i++) s=s*i; //用s保存中间结果 return s; } 单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下： int f(int n) { 科学计算器在统计学中的应用 一．均差、方差的算法 如图中所圈出的按键是计算均值和方差过程中所需要用的键，下面开始具体的操作讲解。1.首先进入方差分析的计算模式 打开科学计算器——MODE键——此时会出现三个选项（COMP/SD/REG），直接按数字键2就可以进入方差分析的模式。 PS:观察计算器的顶端位置会出现SD字样，说明已经进入该计算模式 2.录入待计算数据（此处以22，12，54，34，43，23六个数为例） 直接输入第一个数字22——按M+键输入第二个数字12——按M+键输入第三个数字54，依次类推，到最后一个数字结束时按M+键结束 3.进行计算 数据录取完毕之后按shift键（部分计算器是2ndf）——按数字键2此时会出现三个选项x、x6n和x6n-1，其中第一个就是所求的均值，第三个就是所求的样本方差 点击数字键1然后输入等号就可以得到均值 点击数字键3然后输入等号就可以得到方差 值得注意的是计算完均值需要输出方差的时候需要先按shift键再按数字键3才可以的 此处例子的均值为31.11，方差为15.41 4.强调（恢复初始状态） 在用科学计算器进行均值和方差的计算时，在每次计算完毕之后需要将计算器恢复到默认状态，然后再进行其他的计算。 首先按shift键——然后按MODE键，此时已经进清除状态，界面会显示三个状态，分别是Mcl、Mode和All，选择其中任意一个然后输入=键就完成了相应的清除功能了。 选择2就是清除了方差和均值的计算模式， 选择3则清除了你对计算器所有的设置，回到了默认状态 另外，如果在一次方差和均值计算中不小心输错了数据，则需要首先清除方差均值计算模式，再次进入后重新计算，否则容易出现错误。二．排列组合的运算 排列组合所需要的是nPr、nCr这两个函数,，他们为同一个按键，按shift可以相互转换。其中nPr在计算排列即A n m时用到，而nCr则是在计算组合即C n m时用到，此处分别以( m=5、n=2)进行举例计算 递归算法的优缺点： ○ 1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 ○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 边界条件与递归方程是递归函数的二个要素 应用分治法的两个前提是问题的可分性和解的可归并性 以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。 回溯法以深度优先的方式搜索解空间树T ，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T 。 舍伍德算法设计的基本思想: 设A 是一个确定性算法，当它的输入实例为x 时所需的计算时间记为tA(x)。设Xn 是算法A 的输入规模为n 的实例的全体，则当问题的输入规模为n 时，算法A 所需的平均时间为 这显然不能排除存在x ∈Xn B ，使得对问题的输入规模为n 拉斯维加斯( Las Vegas )算法的基本思想: 设p(x) 是对输入x 调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x 均有p(x)>0。 设t(x)是算法obstinate 找到具体实例x 的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x 蒙特卡罗(Monte Carlo)算法的基本思想: 设p 是一个实数，且1/2 学生课程实验报告书 2014--2015学年第1学期 实验项目：子程序设计（n!） 实验时间： 2014-10-30 实验原理： 在一个程序中如果其中有些内容完全相同或相似，为了简化程序，可以把这些重复的程序段单独列出，并按一定的格式编写成子程序。用递归方式求出n！。 实验仪器： Emu8086编译器 实验步骤（纸张不够写可另外加纸并应装订）： DATA SEGMENT NUM DW 5 FNUM DW ? DATA ENDS STACKS SEGMENT DW 100 DUP(?) STACKS ENDS CODE SEGMENT ASSUME CS:CODE,DS:DATA,SS:STACK BEGIN: MOV AX,DATA MOV DS,AX ;将数据段基值装入DS MOV AX,NUM ;取N PUSH AX ;利用堆栈传递参数 CALL FAC ;调用递归子程序 POP FNUM ;送结果 MOV AX,4C00H ;返回DOS INT 21H FAC PROC PUSH AX ;保存调用参数 PUSH BP ;保存每帧的帧地址(偏移量) MOV BP,SP ;当前帧地址(栈顶地址)送BP寄存器 MOV AX,[BP+6];取参数N CMP AX,0 ;N = 0 ? JNZ FACSUB ;N≠0,继续递归调用 INC AX ;若N=0,则0!=1 JMP EXIT ;由递归调用过程转递次返回过程FACSUB: DEC AX ;N-1送AX PUSH AX ;保护各次调用参数 CALL FAC ;递归调用 POP AX ;从堆栈中弹出每次压入的参数 MUL WORD PTR [BP+6];计算各参数的乘积EXIT: MOV [BP+6],AX ;保存中间结果和最后结果 MOV DX,AX POP BP ;恢复BP内容 POP AX ;恢复AX内容 RET ;返回所调用程序 FAC ENDP CODE ENDS END BEGIN 指导教师评语： 实验成绩_______________ 指导教师_______________ 通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口. 从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的. ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现同步. 下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式). 下面以先序遍历来说明: void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法*/ { if (T) { visit(T); /* 访问当前结点*/ preorder_recursive(T->lchild); /* 访问左子树*/ preorder_recursive(T->rchild); /* 访问右子树*/ } } visit(T)这个操作就是对当前数据进行的处理, preorder_recursive(T->lchild)就是把当前数据变换为它的左子树,访问右子树的操作可以同样理解了. 现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的"叶子结点". 编译方法实验报告实验名称：简单的语法分析程序设计 实验要求 1.功能：对简单的赋值语句进行语法分析 随机输入赋值语句，输出所输入的赋值语句与相应的四元式 2.采用递归下降分析程序完成（自上而下的分析） 3.确定各个子程序的功能并画出流程图 4.文法如下： 5.编码、调试通过 采用标准输入输出方式。输入输出的样例如下： 【样例输入】 x:=a+b*c/d-(e+f) 【样例输出】(说明，语句和四元式之间用5个空格隔开) T1:=b*c (*,b,c,T1) T2:=T1/d (/,T1,d,T2) T3:=a+T2 (+,a,T2,T3) T4:=e+f (+,e,f,T4) T5:=T3-T4 (-,T3,T4,T5) x:=T5 (:=,T5,-,x) 【样例说明】程序除能够正确输出四元式外，当输入的表达式错误时，还应能检测出语法错误，给出相应错误提示。 6.设计3-5个赋值语句测试实例，检验程序能否输出正确的四元式；当输入错误的句子时， 检验程序能够给出语法错误的相应提示信息。 7.报告容包括： 递归程序的调用过程，各子程序的流程图和总控流程图，详细设计，3-5个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等。 目录 1.语法分析递归下降分析算法 (5) 1.1背景知识 (5) 1.2消除左递归 (6) 2.详细设计及流程图 (6) 2.1 函数void V( ) // V -> a|b|c|d|e...|z . (6) 2.2 函数void A( ) // A -> V:=E (7) 2.3 函数void E() //E -> TE' (7) 2.4函数void T( ) // T -> FT' (8) 2.5函数void E1( ) //E'-> +TE'|-TE'|null (8) 2.6函数void T1() // T'-> *FT'|/FT'|null (9) 3.测试用例及截图 (9) 3.1测试用例1及截图 (9) 3.2测试用例2及截图 (10) 3.3测试用例3及截图 (11) 代码清单 (11) 递 归 冯文科 一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引 用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及n a 与前面临近几项之间的关系。 要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它，应该是： ???>==-1 ,1,11n na n a n n 如果需要写一个函数来求n a 的值，那么可以很容易地写成这样： 这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一 些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为 特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。 以上面求阶乘数列的函数)(n f 为例。如在求)3(f 时，由于3不是特殊值，因此需要计 算)2(*3f ，但)2(f 是对它自己的调用，于是再计算)2(f ，2也不是特殊值，需要计算 )1(*2f ，需要知道)1(f 的值，再计算)1(f ，1是特殊值，于是直接得出1)1(=f ，返回上 一步，得2)1(*2)2(==f f ，再返回上一步，得62*3)2(*3)3(===f f ，从而得最终解。 用图解来说明，就是 下面再看一个稍复杂点的例子。 【例1】数列}{n a 的前几项为 一、计算器使用的状态 对于两类计算器来说，使用的是数值计算，所采用的状态是十进制状态： 1、学生计算器（KDT科灵通科学计算器）：按模式键 第一次屏幕显示 第二次屏幕显示 按2次，再按1，则进入十进制计算状态，这时在屏幕上会出现D的标志。 2、普通计算器（价格10元以内）：按键 直接按键，依次在屏幕上会分别显示：DEG、RAD、GRAD，表示十进制、弧度、百分率。要选择DEG，即在屏幕上看到DEG的标志。 二、角度的输入与计算 两种计算器都可以进行角度的运算以及转换： 1、学生计算器（KDT （1 例如输入129°59′26″，操作如下： 输入1295926 这时屏幕的第二行显示：129°59°26°，说明已经将角度输入 （2）角度经过三角函数的计算之后，显示的角度是十进制，即129°59′26″屏幕上显示129.353336，这时需要将十进制的角度转换回六十进制。 按129.353336→129°59°26°。 2 （1）角度的输入：输入角度要以六十进制输入，度和分秒以小数点隔开， 可将六十进制的角度值转换成十进制，用于角度计算或三角函数计算。 具体操作如下：输入129.5926 这时屏幕上显示结果129.9905556，可以进行角度的加减或三角函数计算。 （2）计算结果显示：当角度计算完毕后，需要显示角度的结果，即六十进制的角度结果， 按 具体操作如下：129.9905556→按 这时屏幕上显示计算结果129.592600，可以将成果记录下来。 三、测量误差的精度评定（统计计算） 两种计算器都可以进行标准偏差统计计算： 1、学生计算器（KDT科灵通科学计算器）：在标准偏差统计模式下 （1）进入标准偏差统计计算模式：按 显示 ） 其中n x x2m，即中误差。 编译方法实验报告 令狐采学 实验名称：简单的语法分析程序设计 实验要求 1.功能：对简单的赋值语句进行语法分析 随机输入赋值语句，输出所输入的赋值语句与相应的四元式 2.采用递归下降分析程序完成（自上而下的分析） 3.确定各个子程序的功能并画出流程图 4.文法如下： 5.编码、调试通过 采用标准输入输出方式。输入输出的样例如下： 【样例输入】 x:=a+b*c/d(e+f) 【样例输出】(说明，语句和四元式之间用5个空格隔开) T1:=b*c (*,b,c,T1) T2:=T1/d (/,T1,d,T2) T3:=a+T2 (+,a,T2,T3) T4:=e+f (+,e,f,T4) T5:=T3T4 (,T3,T4,T5) x:=T5 (:=,T5,,x) 【样例说明】程序除能够正确输出四元式外，当输入的表达式错误时，还应能检测出语法错误，给出相应错误提示。 6.设计35个赋值语句测试实例，检验程序能否输出正确的四 元式；当输入错误的句子时，检验程序能够给出语法错误的相应提示信息。 7.报告内容包括： 递归程序的调用过程，各子程序的流程图和总控流程图，详细设计，35个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等。 目录 1.语法分析递归下降分析算法5 1.1背景知识5 1.2消除左递归6 2.详细设计及流程图6 2.1 函数void V( ) // V > a|b|c|d|e...|z6 2.2 函数void A( ) // A > V:=E7 2.3 函数void E() //E > TE'7 2.4函数void T( ) // T > FT'8 2.5函数void E1( ) //E'> +TE'|TE'|null8 2.6函数void T1() // T'> *FT'|/FT'|null9 3.测试用例及截图9 3.1测试用例1及截图9 3.2测试用例2及截图10 3.3测试用例3及截图11 代码清单11 课程设计 题目WHILE循环语句的翻译程序设计 （递归下降法、输出三地址表示）学院计算机科学与技术学院 专业计算机科学与技术 班级0806 姓名张方纪 指导教师郭羽成 2010 年 1 月7 日 课程设计任务书 学生姓名：张方纪专业班级：计算机0806班 指导教师：郭羽成工作单位：计算机科学与技术学院 题目: WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）初始条件： 理论：学完编译课程，掌握一种计算机高级语言的使用。 实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） （1）写出符合给定的语法分析方法的文法及属性文法。 （2）完成题目要求的中间代码三地址表示的描述。 （3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。 （4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。 （5）设计报告格式按附件要求书写。课程设计报告书正文的内容应包括： 1 系统描述（问题域描述）； 2 文法及属性文法的描述； 3 语法分析方法描述及语法分析表设计； 4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计； 5 编译系统的概要设计； 6 详细的算法描述（流程图或伪代码）； 7 软件的测试方法和测试结果； 8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）； 9 参考文献（按公开发表的规范书写）。 时间安排： 设计安排一周：周1、周2：完成系统分析及设计。 周3、周4：完成程序调试及测试。 周5：撰写课程设计报告。 设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。 设计报告书收取时间：设计周的次周星期一上午10点。 指导教师签名： 2010年 11月 23日 系主任（或责任教师）签名： 2010年 11月 23日高中信息技术 算法与程序设计-递归算法的实现教案 教科版
编译原理-递归下降子程序-课程设计报告
递归算法和非递归算法的区别和转换
科学计算器的科学用法
递归算法的优缺点
汇编子程序设计(n!)
递归算法工作栈的变化详解
递归下降语法分析程序的设计说明
递归算法详解
科学计算器的使用方法
递归下降语法分析程序设计
WHILE语句的翻译—递归子程序法—三地址表示——编译原理课程设计报告
相关主题
文本预览