4.5递归算法与递归程序.doc

一、教学目标1、知识与技能(1).认识递归现象。(2).使用递归算法解决问题往往能使算法的描述乘法而易于表达(3).理解递归三要素:每次递归调用都要缩小规模;前次递归调用为后次作准备:递归调用必须有条件进行(作者:朱寿成 修改时间:2006年8月11日)二、重点难点1、教学重点(1)了解递归现象和递归算法的特点。(2)能够根据问题设计出恰当的递归程序。2、教学难点(1)递归过程思路的建立。(2)判断问题是否适于递归解法。(3)正确写出递归程序。三、教学环境1、教材处理教材选自《广东省普通高中信息技术选修一:算法与程序设计》第四章第五节,原教材的编排是以本节以斐波那契的兔子问题引人,导出递归算法,从而自定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。教材经处理后,让同学们玩汉诺塔的游戏,导入递归问题,从用普通程序解决斐波那契的兔子问题入手,引导学生用自定义了一个以递归方式解决的函数过程解决问题,同时让同学们做三个递归练习,巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远,但方法和答案却都是完全相同的练习,体会其中的奥妙,加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。教学方法采用讲解、探究、任务驱动和学生自主学习相结合2、预备知识学生已掌握了用计算机解决问题的过程,掌握了程序设计基础,掌握了解析法、穷举法、查找法、排序法设计程序的技巧。3、硬件要求建议本节课在多媒体电脑教室中完成,最好有广播教学系统或投影仪,为拓展学习,学生机应允许上互联网。4、。5、所需课时2课时(90分钟)四、教学过程导入:大家玩汉诺塔游戏:  图4-5(1)汉诺塔游戏的部分界面 这个游戏盘子在A、B、C三根柱子上不停运动,有没有规律,和你在照过镜子时遇到的情况相同吗?当你往镜子前面一站,镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果甲、乙两面镜子相互面对面放着,你往中间一站,嘿,两面镜子里都有你的千百个“化身”!为什么会有这么奇妙的现象呢?原来,甲镜子里有乙镜子的像,乙镜子里也有甲镜子的像,而且这样反反复复,就会产生一连串的“像中像”。这是一种递归现象。由同学们总结出递归算法的概念递归算法:是一种直接或者间接地调用自身的算法。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。问题4-16:著名的意大利数学家斐波那契(i)在他的著作《算盘书》中提出了一个“兔子问题”:假定小兔子一个月就可以长成大兔子,而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子,问到年底时将有多少对兔子? (当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖) 我们不难用以前学过的知识设计出如下算法:①   输入计算兔子的月份数:n②   Ifn<3Thenc=1Elsea=1:b=1③   i=3④   c=a+b:a=b:b=c⑤   i=i+1,如果i≤n则返回④⑥   结束 参考程序如下:mand1_Click() n=Val() Ifn<3Thenc=1Elsea=1:b=1 Fori=3Ton   c=a+b   a=b   b=c Nexti ="第"&n&"月的兔子数目是:"&cEndSub图4-5(2)斐波那契兔子程序运行结果图 开动脑筋:我们有没有更简单的方法解决该问题呢?  (1)分析问题。我们可以根据题意列出表4-3来解决这个问题:表4—3兔子问题分析表1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1 123581321345589合计1123581321345589144 这个表格虽然解决了斐波那契的兔子问题(年底时兔子的总数是144只),但仔细观察一下这个表格,你会发现兔子的数目增长得越来越快,如果时间再长,只用列表的方法就会有困难。(例如,你愿意用列表的方法求出5年后兔子的数目吗?)我们需要研究表中的规律,找出一般的方法,去解决这个问题。交流仔细研究表4-8,你有些什么发现?每一个月份的大兔数、小兔数与上一个月的数字有什么联系,能肯定这个规律吗?恭喜你,你快成功了?(2)设计算法。“兔子问题”很容易列出一条递推式而得到解决。假设第N个月的兔子数目是F(N),我们有: 这是因为每月的大兔子数目一定等于上月的兔子总数,而每个月的小兔子数目一定等于上月的大兔子数目(即前一个月的兔子的数目)。由上述的递推式我们可以设计出递归程序。递归程序的特点是独立写出一个函数(或子过程),而这个函数只对极简单的几种情况直接给出解答,而在其余情况下通过反复的调用自身而把问题归结到最简