递归算法与递归程序（一二）(共13页).doc

精选优质文档-倾情为你奉上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)(N3)递推式。马上介绍斐波那契问题的非递归解决方法，如果加以恰当引导，把两个解法对比，会出现效率高的需要较多的经验和技艺才能写出程序，而程序相对容易写出的是在运行时，但效率却不够高。（在调试程序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,如果in则返回    结束 参考程序如下：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 & "月的兔子数目是：" & cEnd Sub图4-5(2)斐波那契兔子程序运行结果图 开动脑筋：我们有没有更简单的方法解决该问题呢？ 4.5.1  从斐波那契的兔子问题看递归算法1斐波那契的兔子问题子 (1)分析问题。我们可以根据题意列出表4-3来解决这个问题：表43兔子问题分析表1月2月3月4月5月6月7月8月9月10月11月12月小兔1 1 1 2 3 5 8 13 21 34 55 大兔1123581321345589 合计1123581321345589144这个表格虽然解决了斐波那契的兔子问题(年底时兔子的总数是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 typeStatementsEnd 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 FunctionPrivate 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 FunctionPrivate 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 FunctionPrivate 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 FunctionPrivate 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次成功。当N2，那么需要利用C柱来过渡。我们假设已经找到一种把N1个金盘从一根柱搬到另外一根柱的方法，那么，我们只要把N1个金盘从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柱；AB  它的意思是把一个(最大的)金盘从A柱搬到B柱； Hanoi(N1，C，B，A)它的意思是把c柱上的N一1个金盘搬到B柱。 空中加油站：过程定义的格式：Private Sub procedurename(arguments)statementsEnd 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 + vbCrLft = 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 IfEnd SubPrivate 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 = tEnd Sub(4)测试程序在“金盘数目”的文本框中输入4。图4-5(9)Hanoi结果示意图(5)检测结果 挑战自我：（以下部分由学生自己完成）如来不用递归，可不可以用其它的解决方案？把A、B、C三柱看作是顺时排列的。C之后又是A，那么搬动过程可以描述为：当搬动次数是奇数时，把最小的金盘移到顺时钟方向的下一根柱子上。当搬动的次数是偶数时则保持最小的金盘不动。而在其他两柱之间把较小的金盘从一根柱子移到另外一根拄子上。不断重复这个过程，即可以完成全部金盘的正确移动。请同学们设计好该程序。本节小结：1、应用递归算法一般都需要调用子过程。2、子过程的参数，不能安排失当。3、在子过程中需要包含自我调用(或者几个子过程的相互调用)。4、对于调用的条件必须清楚，在最初始的简单情形，由人力来获得解答，让递归能够正常结束。递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。专心-专注-专业