4.5递归算法与递归程序(一、二) 下载本文

内容发布更新时间 : 2024/12/24 0:12:11星期一 下面是文章的全部内容请认真阅读。

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、教材处理

教材选自《广东省普通高中信息技术选修一:算法与程序设计》第四章第五节,原教材的编排是以本节以斐波那契的兔子问题引人,导出递归算法,从而自定义了一个以递归方式

1

解决的函数过程。然后利用子过程解决汉诺塔的经典问题。

教材经处理后,让同学们玩汉诺塔的游戏,导入递归问题,从用普通程序解决斐波那契的兔子问题入手,引导学生用自定义了一个以递归方式解决的函数过程解决问题,同时让同学们做三个递归练习,巩固提高。然后让学生做练习(2)和练习(3),这两道题目的形式相差很远,但方法和答案却都是完全相同的练习,体会其中的奥妙,加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。

教学方法采用讲解、探究、任务驱动和学生自主学习相结合 2、预备知识

学生已掌握了用计算机解决问题的过程,掌握了程序设计基础,掌握了解析法、穷举法、查找法、排序法设计程序的技巧。

3、硬件要求

建议本节课在多媒体电脑教室中完成,最好有广播教学系统或投影仪,为拓展学习,学生机应允许上互联网。

五、教学过程

导入:

大家玩汉诺塔游戏:

2

图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 = \第\月的兔子数目是:\ & c End Sub

3