递归法与问题解决-冠军奖.docxVIP

第三节递归法与问题解决

一、教材分析

“递归法与问题解决”是中图版信息技术（选修一）《算法与程序设计》第三单元第三节的内容，前面学习了“解析法与问题解决”、“穷举法与问题解决”，递归算法属于比较难理解与运用的一节。“递归算法”的基本思想：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。

二、学情分析

教学对象是高中二年级学生，是高中所学的最后一个算法，之前学过了程序设计的各种语句，方法、模块化程序设计思想，还学习过了“解析法”、“穷举法”等算法。

三、教学目标

1．知识与技能：

(1)理解什么是“递归算法”，能用“递归算法”的思想分析问题；

(2)能够应用自定义函数方法实现“递归算法”的编程。

2．过程与方法：

学生参与讨论，通过游戏过程，思考“递归算法”思想，体验“递归算法”的程序。

3．情感态度与价值观：

(1)通过游戏中的“坚持”一词，让学生感悟“再坚持一下”的含义；

(2)结合数学中的实例，激发学生的数学建模意识，培养学生多维度的思考问题和解决问题。

四、教学重点、难点

1．教学重点：

理解什么是“递归算法”，能用“递归算法”的思想分析问题。

2．教学难点：

应用自定义方法实现“递归算法”的编程。

五、教学方法

任务驱动、小组讨论、讲授法、演示法

六、教学过程

1．课堂导入

师：今天我们先做一个游戏，请几个同学出来站成一排，然后我们让最后一个同学说出他站在第几个位置，期间不能自己去数，只可以询问前面或者后面的同学，得到答案后说出自己是第几个位置。请同学们思考一下，怎么才解决这个问题。

学生活动：按照游戏规则思考怎样解决问题。

师：下面游戏开始。

学生活动：按照自己的思路进行游戏。

2．交流探索

师：刚才的游戏，最后一个同学想知道结果，就必须向前面的同学询问位置，前面的同学又得向前面的同学询问位置，直到第一个同学前面没有人，他就是第一个，然后向后面的同学报告自己的位置，以此类推，直到最后一个同学直到自己的位置后，向老师报告。这个过程就是我们今天要学习的递归算法的思想。

师：刚才的游戏，如果想游戏结束，必须有个什么条件

学生回答：必须得有第一个同学。

师：也就是说，这个程序在递推的时候必须有一个结束条件，如果没有这个条件，程序就会无限制得递推下去，最后就会像死循环那样，造成死机。

师：递归算法都是借助自定义方法来实现，方法是为了实现某种功能而编写的一段相对独立的程序，并且可以多次的调用。这个和我们数学中所说的函数其实是一样的。

师：这个游戏的伪代码描述

intf(n)

{

如果是第一个同学，返回1.

如果不是第一个同学，返回f(n-1)+1

}

用数学的函数表示为f(n)=f(n-1)+1

3.解决问题

例题1：有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子(猴子摘桃)

师：以小组为单位，讨论此题应该如何解决

学生口述此题的解决方法

建立数学模型：

师：假设第n天(n10)的桃子数为taozi(n)，那么当n10时，就有taozi(n)=

生：(taozi(n+1)+1)*2

师：此题的底在哪里

生：第10天的桃子数是1个。

幻灯片出示自定义方法taozi的代码：

例题2：汉诺塔

师：法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

师：这个东西相信大家都玩过。那么谁能说说它怎么玩呢

师：打开汉诺塔游戏软件，设置2层。

生：先将最上面的一片移到中间，然后将下面的一片移动到右边，最后将中间的移动到右边。

师：非常好。这个同学很清楚这个游戏怎么玩，下面我们来算一下移动n层需要多少次。

学生活动：讨论这个问题。

师：先请同学说一下怎么才能将n片移动过去。

生：要移动n片，首先要移动n-1片到中间，然后把第n片移动到右边，然后把这n-1片移动到右边。然后再讨论移动n-1片的情况，以此类推，直到移动1片的时候。

师：非常好。我们来画一个图就更容易看懂了。

师：那么下面我们来编写代码：

师：下面我们来计算一下步数和n的关系。

假设移动n片的步数为T（n），

T(n)=T(n-1)+1+T(n-1