《2022年-递归算法与递归程序[归》由会员分享,可在线阅读,更多相关《2022年-递归算法与递归程序[归(18页珍藏版)》请在金锄头文库上搜索。
1、一、教学目标1、知识与技能(1) 认识递归现象。(2) 使用递归算法解决问题往往能使算法的描述乘法而易于表达(3) 理解递归三要素: 每次递归调用都要缩小规模; 前次递归调用为后次作准备:递归调用必须有条件进行。(4) 认识递归算法往往不是高效的算法。(5) 了解递归现象的规律。(6) 能够设计递归程序解决适用于递归解决的问题。(7) 能够根据算法写出递归程序。(8) 了解生活中的递归现象,领悟递归现象的既有重复,又有变化的特点,并且从中学习解决问题的一种方法。2、方法与过程本节让同学们玩汉诺塔的游戏,导入递归问题,从用普通程序解决斐波那契的兔子问题 入手,引导学生用 自定义了一个以递归方式解
2、决的函数过程解决问题,同时让同学们做三个递归练习, 巩固提高。然后让学生做练习 (2)和练习 (3) 这两道题目的形式相差很远,但方法和答案却是完全相同的练习,体会其中的奥妙,加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。3、情感态度和价值观结合高中生想象具有较强的随意性、更富于现实性的身心发展特点,综合反映出递归算法的特点,以及递归算法解答某些实践问题通常得很简洁,从而激发学生对程序设计的追求和向往。二、重点难点1、教学重点(1)了解递归现象和递归算法的特点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整
3、理 - - - - - - - 第 1 页,共 18 页 - - - - - - - - - (2)能够根据问题设计出恰当的递归程序。2、教学难点(1) 递归过程思路的建立。(2) 判断问题是否适于递归解法。(3) 正确写出递归程序。三、教学环境1、教材处理教材选自广东省普通高中信息技术选修一:算法与程序设计第四章第五节,原教材的编排是以本节以斐波那契的兔子问题引人,导出递归算法,从而自定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。教材经处理后,让同学们玩汉诺塔的游戏,导入递归问题,从用普通程序解决 斐波那契的兔子问题 入手,引导学生用 自定义了一个以递归方式解决的函
4、数过程 解决问题,同时让同学们做三个递归练习,巩固提高。然后让学生做练习 (2) 和练习 (3) 这两道题目的形式相差很远,但方法和答案却都是完全相同的练习,体会其中的奥妙,加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。教学方法采用讲解、探究、任务驱动和学生自主学习相结合2、预备知识学生已掌握了用计算机解决问题的过程,掌握了程序设计基础,掌握了解析法、穷举法、查找法、排序法设计程序的技巧。3、硬件要求建议本节课在多媒体电脑教室中完成,最好有广播教学系统或投影仪,为拓展学习,学生机应允许上互联网。4、所需软件学生机要安装 VB6.0 或以上版本。5、所需课时2 课时( 90 分钟)名师
5、资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 18 页 - - - - - - - - - 四、教学过程导入:大家玩汉诺塔游戏:图 4-5(1)汉诺塔游戏的部分界面这个游戏盘子在A、B、C 三根柱子上不停运动,有没有规律,和你在照过镜子时遇到的情况相同吗?当你往镜子前面一站,镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果甲、乙两面镜子相互面对面放着,你往中间一站,嘿,两面镜子里都有你的千百个“ 化身 ”!为什么会有这么奇妙的现象呢?原来,甲镜子里有乙镜子的像,乙镜子
6、里也有甲镜子的像,而且这样反反复复,就会产生一连串的“ 像中像 ” 。这是一种递归现象。由同学们总结出递归算法的概念递归算法: 是一种直接或者间接地调用自身的算法。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 18 页 - - - - - - - - - 问题4-16:著名的意大利数学家斐波那契(Fibonacci)在他的著作算盘书中提出了一个“ 兔子问题 ” :假定小兔子一个
7、月就可以长成大兔子,而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子,问到年底时将有多少对兔子? (当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖) 我们不难用以前学过的知识设计出如下算法:输入计算兔子的月份数: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
8、To n c = a + b a = b b = c Next i Text2.Text = 第 & n & 月的兔子数目是: & c End Sub 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 18 页 - - - - - - - - - 图 4-5(2)斐波那契兔子程序运行结果图开动脑筋: 我们有没有更简单的方法解决该问题呢?4.5.1 从斐波那契的兔子问题看递归算法1斐波那契的兔子问题子(1)分析问题。我们可以根据题意列出表4-3 来解决这个问题:表 43 兔子
9、问题分析表1 月2 月3 月4 月5 月6 月7 月8 月9 月10 月11 月12月小兔111235813213455大兔1123581321345589合计1123581321345589144这个表格虽然解决了斐波那契的兔子问题(年底时兔子的总数是144 只),但仔细观察一下这个表格,你会发现兔子的数目增长得越来越快,如果时间再长,只用列表的方法就会有困难。(例如,你愿意用列表的方法求出 5 年后兔子的数目吗?)我们需要研究表中的规律,找出一般的方法,去解决这个问题。交流名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师
10、精心整理 - - - - - - - 第 5 页,共 18 页 - - - - - - - - - 仔细研究表 4-8,你有些什么发现?每一个月份的大兔数、小兔数与上一个月的数字有什么联系,能肯定这个规律吗?恭喜你,你快成功了?(2)设计算法。“ 兔子问题 ” 很容易列出一条递推式而得到解决。假设第N 个月的兔子数目是F(N),我们有:这是因为每月的大兔子数目一定等于上月的兔子总数,而每个月的小兔子数目一定等于上月的大兔子数目(即前一个月的兔子的数目)。由上述的递推式我们可以设计出递归程序。递归程序的特点是独立写出一个函数(或子过程 ),而这个函数只对极简单的几种情况直接给出解答,而在其余情况
11、下通过反复的调用自身而把问题归结到最简单的情况而得到解答。空中加油站:自定义函数的定义格式: Function procedurename(arguments) As type Statements End Function 其中的 procedurename 是函数名, arguments是函数中的参数表,type 是函数返回值的数据类型, 表示可有可无的部分, statements是过程中的代码调用函数的格式:procedurename(arguments) (3)编写程序。窗体中开设一个文本框Textl 用于填人月数N,设置命令框Commandl,点击它即执行程序求出第N 月的兔子数。然
12、后用文本框Text2 输出答案。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 18 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 18 页 - - - - - - - - - 根据递推式可以写出递归程序如下:Function Fib(ByVal N As Integer) As Long If N 3 Th
13、en 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)斐波那契兔子程序运行结果图文本框 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8
14、 页,共 18 页 - - - - - - - - - (5)检测结果挑战自我:(以下部分由学生自己完成)(1)利用递归方法编写一求N 的阶乘。分析:根据 N!=N*(N-1)*(N-2)*(N-3)* *3*2*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:,
15、求 N 的阶乘 ) Print 输入的正整数是 ; n; Print ,阶乘是 ; F(n) End Sub 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 18 页 - - - - - - - - - 图 4-5(5)求阶乘程序的运行结果图(2)对一正整数N,用数字 l 和 2 组成一条加法算式,使其和为N,共可以列出多少条不同的式子?( “l+2 ”和“2+1” 看作是不同的式子)。算法设计:假设和为 N 时可列式子的方法数是F(N),那么第一个加数可选择1 或 2。
16、当第一个加数为1 时剩下加数的和为 N 一 1,故方法数为F(N 一 1);当第一个加数为2 时,剩下加数的和为N-2,故方法数为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() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理
17、- - - - - - - 第 10 页,共 18 页 - - - - - - - - - Dim n As Integer n = Val(InputBox( 请输入正整数N:, 输入式子的总和) Print 当总和是 ; n; 时 Print 可以列出不同的由1 和 2 组成的加法式子; F(n); 条 End Sub 图 4-5(6)书上 P137 练习 2 程序运行结果图(3)罗光明在上楼梯时,有时一步一级楼梯,有时一步两级。如果楼梯有N 级,他上完这 N 级楼梯有多少种不同的方法?设计算法假设楼梯级数为N 时的方法数是F(N),那么第一步可选择1 或 2 级楼梯。 当第一步为1 级时
18、剩下楼梯的级数为 N-1,故方法数为F(N-1) ;当第一步为2 级时,剩下楼梯的级数为N-2,故方法数为F(N-2)。于是可以得到如下式子:名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页,共 18 页 - - - - - - - - - 这是一个典型的递归算法,参考程序如下:程序如下:Function F(ByVal n As Integer)As Long If n=2 Then F=n Else F=F(n-1)+F(n-2) End Functi 0n Privat
19、e Sub Form_Click() Dim n As Integer n=Val(InputBox( 请输入楼梯级数N:,输人楼梯级数 ) Print 当楼梯级数 ;n;时, Print 可以有 ;F(n);种不同的上楼梯方法。 End Sub 同学们比较一下你们所做的练习(2)和(3)的程序代码, 不知同学们有没有发现一个有趣的现象?为什么会这样?本节小结:递归算法的特点递归过程一般通过函数或子过程来实现。递归算法:在函数或子过程的内部,直接或者间接地调用自己的算法。递归算法的 实质: 是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程 )来表示问题的解。递归算法解决问题
20、的特点:(1)递归就是在过程或函数里调用自身。(2)在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。(3)递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页,共 18 页 - - - - - - - - - (4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。递归算法所体现的“ 重复 ”
21、一般有三个要求:一是每次调用在规模上都有所缩小(通常是减半 );二是相邻两次重复之间有紧密的联系,前一次要为后一次做准备(通常前一次的输出就作为后一次的输入);三是在问题的规模极小时必须用直接给出解答而不再进行递归调用,因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件),无条件递归调用将会成为死循环而不能正常结束。第二课时:导入:大家玩汉诺塔游戏:图 4-5(7)汉诺塔程序运行界面图4.5.2一个应用递归算法解决的问题经典例子问题4-17:传说在古代印度的贝拿勒斯神庙,有一块黄铜板上插了3 根宝石柱,在其中一根宝石柱自上而下由小到大地叠放着64 个大小不等的金盘。 一名僧人把这些
22、金盘从一根宝石柱移到另外一根上。僧人在移动金盘时遵守下面3 条规则:第一,一次只能移动一个金盘。第二,每个金盘只能由一根宝石柱移到另外一根宝石柱。第三,任何时候都不能把大的金盘放在小的金盘上。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页,共 18 页 - - - - - - - - - 神话说,如果僧人把64 个金盘完全地从一根宝石移到了另外一根上,世界的末日就要到了。当然,神话只能当故事来听,世界不可以因为个别人的活动而导致末日。不过,从僧人搬完64 个金盘所需时间的角
23、度来说,即使僧人每秒都能移动一个金盘,那也得要几千亿年!试设计程序,模拟移动金盘的过程。(1)分析问题。我们把 3 根宝石柱分别命名为A、B、C。最初有 N 个金盘放在A,需要把它们全部按规则移动到B。当 N=1 时,直接把金盘从A 搬到 B 就可以了, 1 次成功。当 N 2 ,那么需要利用C 柱来过渡。 我们假设已经找到一种把N1 个金盘从一根柱搬到另外一根柱的方法,那么,我们只要把N1 个金盘从 A 搬到 C,然后把最大的金盘从A 搬到 B,最后把 C 上的 N 一1 个金盘搬到B 就可以了。靠递归的思想,我们轻而易举地完成了整个搬动。(2)设计算法。我们定义一个过程Hanoi(N ,A
24、,B,C),表示有 N 个金盘需要从A 柱搬到 B 柱(以 C 柱为过渡 )。那么完成它只需 3 步:Hanoi(N 一 1,A,C,B)它的意思是把A 柱上的 N 一 1 个金盘搬到C 柱;A B它的意思是把一个(最大的 )金盘从 A 柱搬到 B 柱;Hanoi(N1,C,B,A)它的意思是把c 柱上的 N 一 1 个金盘搬到B 柱。空中加油站:过程定义的格式:Private Sub procedurename(arguments) statements End Sub 其中的 procedurename 是函数名, arguments是函数中的参数表,statements是过程中的代码调用
25、过程的格式:Call procedurename(arguments) Function 函数与 Sub 过程的几点区别:名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页,共 18 页 - - - - - - - - - Function 函数可以返回一个值到调用程序。一般来说,让较大的语句或表达式的右边包含函数过程名和参数(returnvalue=function ),这就调用了函数。与变量完全一样,函数过程有数据类型,这就决定了返回值的类型。(如果没有AS 子句,缺省的数
26、据类型为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 用来统计移动次数。名师
27、资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页,共 18 页 - - - - - - - - - Else Call Hanoi(n - 1, A, C, B, t) Text3.Text = Text3.Text + A + + B + vbCrLft = 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 =
28、 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。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页,共 18 页 - - - - - - - - - 图 4-5(9)Hanoi 结果示意图(5)检测结果挑战自我:(以下部分由学生自己完成)如来不用递归,可不可以用其它的解决方案?把 A、B、C 三柱
29、看作是顺时排列的。C 之后又是A,那么搬动过程可以描述为:当搬动次数是奇数时,把最小的金盘移到顺时钟方向的下一根柱子上。当搬动的次数是偶数时则保持最小的金盘不动。而在其他两柱之间把较小的金盘从一根柱子移到另外一根拄子上。不断重复这个过程,即可以完成全部金盘的正确践移动。请同学们设计好该程序。本节小结:1、应用递归算法一般都需要调用子过程。2、子过程的参数,不能安排失当。3、在子过程中需要包含自我调用(或者几个子过程的相互调用)。4、对于调用的条件必须清楚,在最初始的简单情形,由人力来获得解答,让递归能够正常结束。递归三要素:每次递归调用都要缩小规模;前次递归调用为后次作准备:递归调用必须有条件进行。拓展名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页,共 18 页 - - - - - - - - - 针对 4 根柱子, N 片金叶片,研究汉诺塔问题的解决方案?相关资源:1)网络课程资料:http:/ VB的网络课件:http:/ - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页,共 18 页 - - - - - - - - -