教科版信息技术--算法与程序设计递归算法的实现.doc

递归算法的实现

【基本信息】

作者
刘其政
课时
1课时
单位
海南省儋州市那大二中

【课标要求】
（三）算法与问题解决例举
1. 内容标准
递归法与问题解决
（1）了解使用递归法设计算法的基本过程。
（2）能够根据具体问题的要求，使用递归法设计算法、编写递归函数、编写程序、求解问题。

【教材分析】

“算法的程序实现”是《算法与程序设计》选修模块第三单元的内容，本节课是“递归算法的程序实现”，前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序以及本节的前一小节知识点“什么是自定义函数”的学习，在学习自定义函数的基础上，学习递归算法的程序实现是自定义函数的具体应用，培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。
『递归算法在算法的学习过程中是一个难点，在PASCAL和C语言等程序语言的学习过程中，往往是将其放在“函数与过程”这一章节中来讲解的。递归算法的实现也是用函数或是过程的自我调用来实现的。从这一点上来讲，作者对教材的分析与把握是准确的，思路是清晰的，目标是明确的。』

【学情分析】

教学对象是高中二年级学生，前面学习了程序设计的各种结构，在学习程序设计各种结构的应用过程中培养了用计算机编程解决现实中问题的能力，特别是在学习循环语句的过程中，应用了大量的“递推”算法。前一节课学习了如何自定义函数，在此基础上学习深入学习和体会自定义函数的应用。以递推算法的逆向思维进行求解问题，在学习过程中体会递归算法的思想过程。多维度的思考问题和解决问题是提高学生的学习兴趣关键。
『递归算法的本质是递推，而递推的实现正是通过循环语句来完成的。作者准确把握了学生前面的学习情况，对递归算法的本质与特征也分析的很透彻，可以说作者对教学任务的分析是很成功的，接来就要看，在成功分析的基础上作者是如何通过设计教学来解决教学难点的了。』

【教学目标】

知识与技能：
理解什么是递归算法，学生会用递归算法的思想分析问题
能够应用自定义函数方法实现递归算法的编程
过程与方法：
学生参与讨论，通过思考、动手操作，体验递归算法的方法
情感态度与价值：
结合数学中的实例，激发学生的数学建模的意识，培养学生多维度的思考问题和解决问题。
『教学目标设计的合理、准确。这也是在意料之中的，一般情况下，成功的教学任务分析一定会带来成功的教学目标设计。』

【重点难点】

重点：理解什么是递归算法，学生用递归算法的思想分析问题；
应用自定义函数方法实现递归算法的编程
难点：应用自定义函数方法实现递归算法的编程
『大部分教师在确立教学重、难点时不会给出确立的依据，可能这些依据早就在教师的脑中明确了，也有可能是一笔糊涂账，只不过是教参上是这样写的就照搬过来而已如果在写教学重、难点的同时能再给出确立重、难点的依据会令教案更具借鉴意义。本案例的作者虽然没有写依据，但由于前面成功的教学任务分析，也就自然确立了教学重、难点。这也是很好的。』

【教学过程】

进程
教师活动
学生活动
设计意图
创设情境
课堂导入：
今天很高兴，特此我给大家准备了一份礼品（精美包装猴与兔艺术品），你们想知道里面有什么礼物吗？
学生：想……
师：好！我们班有一位同学知道里面有什么礼物！(在上课之前事先告诉其中的一个同学)但是他不能就这样告诉大家，有一个规则可以让我们知道里面装的是什么……
规则是：
1.从第一排的第一个同学开始。
2.每位同学只问他相邻的同学，每位同学最多只能被问一次，而且一个同学不能再问第二人，当任何一个同学知道了答案,要求立即告诉曾经问过他的那个同学 (不能告诉其他同学)以此类推。
3.一直到得出答案为结束。
以游戏规则开展，我想让第一位同学告诉大家，精装的礼物是什么？

师生共同活动“找答案”

使用情境教学法
在此活动过程中能让学生初步从活动中体验“问题的发与收”从而走进了递归的思维模式，为进一步学习递归算法埋下伏笔
『这样的课堂导入方式是一种令人兴奋的方式。令人兴奋的原因有两个：
其一，以“活动”的方式来引导学生探讨一个问题是学生们非常喜欢的方式，学生喜欢，就会产生强烈的兴趣，但还不是学习动机。但因为“活动”与“所要探讨的问题”十分的贴切，是问题的典型代表，学生强烈的兴趣就会自然而然地转化为学习动机。这种学习动机的激发方式比我们直白地告诉学生某某知识点有多么多么重要，我们一定要好好学要来的自然有效的多，是我们需要努力借鉴并执之以恒的。
其二，由于递归算法的学习比较难，直接进行教学对学生的思维能力要求较高，往往达不到预想的效果。但用新颖有趣的活动来引导学生在积极的参与过程中自然地思考老师希望他们思考的问题，并体验问题解决的过程，就会获得较好的学习效果和较高的学习效率。以“活动”的方式引导教学的形式虽然很好，但也是比较难设计的。难就难在“活动”的设计一定要能充分恰当地展示要学习的内容和要探讨的问题。如果只是为了活动而活动，既浪费了宝贵的课堂教学时间，也降低了课堂教学效率，是非常不可取的。因此，成功的活动设计对教师的要求很高，需要老师有扎实的学科知识功底和丰富的社会阅历。』
启发主体
师：前面我们学习了自定义函数，知道函数是为了实现某种功能而编写的一段相对独立的程序，并且可以多次的调用。

算法描述：
function what(student)
如果我知道答案，那么我就告诉你
否则，我要问下一位同学再告诉你
end function

讨论活动过程，总结游戏规则，了解活动规律，并将活动过程进行算法描述
分析问题
确定方案,培养学生思维程序化，为下面新学习递归算法做好移植准备
『这一部分的设计较之于前一段，立刻显得平淡，缺乏“热闹”。然而，这看似平淡的教学过程却是画龙点睛之笔。如果没有这一段教学的及时总结，对前一“活动”过程思维上的提升，那前面的活动就只能流于形式、止步于“热闹”了。因此，我们在用“活动”的方式引入教学之后，要注意及时总结活动并提升到所要探讨的问题，这样才算完成了教学。活动的开展，目的也是为了让学生能较容易地掌握新知进行铺垫并对问题进行深入思考。』
学习新知
展示题：
小猴吃桃:
    有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子?
1.鼓励学生进行讨论，共同寻找答案或解决方法
2.师生共同分析题：
以4位同学排成了行，（设从行的后面开始的第一位同学知道第10的桃子数（1个），倒数第二位同学知道第9天的桃子数是……）从教师提问排在前面第一位（第7天）的同学，你知道，你今天的桃子数有多少？
讨论、比较、分析、归纳

实例教学，选择“小猴吃桃”这一题的目的是为了简化教材“裴波那契”数列的多函数调用回避问题分析的复杂性较大的特点，从而使得
重点难点得以轻松的突破。

目的是讨论出，只有倒数第一位同学知道，其他有同学都不知道，但是他只要知道他后一位同学的桃子数就可以求出本人所具有的桃子数，（后同学的桃子数+1）*2就是本人的桃子数。

『看来作者真是一个善于通过“活动”的方式来完成教学的“高手”，在降低了分析问题的难度以后，再一次用活动的方式来引导学生来分析问题，这是一种真正意义上的循循善诱，比教师不厌其烦地教给学生十遍公式要来的高效的多。』

建立数学模型：
假设第n,n<10天的桃子数为tao(n)那么
tao1 n=1
tao(n)=(tao(n+1)+1)*2 n<10

推导数学建模

我们能不能这样设一个函数：
算法描述：
function你有多少桃子？（第几天）
如果我第10天，那么我就有一个桃子。
否则，我的桃子数=（前一天的桃子数+1）*2
end function
学生进行算法描述

培养学生养成良好的编程习惯

『还是的，在“活动”过后要及时的总结与提升。先在分析的基础上建立数学模型，再用伪代码来描述，严格按计算机解决问题的基本过程来展开课堂教学，不断培养与强化学生良好的编程习惯。』

学生编程实现：
Function tao(ByVal days As Integer) As Integer
If days = 10 Then
tao = 1
Else
tao = (tao(days + 1) + 1) * 2
End If
End Function

分析算法的实现过程

学生编程实现
示图协助学生算法实现过程的始末思维，

培养学生的编程和调试程序能力，让学生获得成功的体检
『再用示图的方式来帮助学生进行思维，降低学生思维的难度（并没有降低思维的质量），从而提高教学效率。再让学生动手编写代码，实践计算机解决问题基本过程的最后一步。至此，用递归算法解决“猴子摘桃”问题的全过程完成了。』
自主构建
我们再来看第二题：（学生阅读教材P68，让学生阅读教材的“裴波那契”，培养学生的自学能力、和知识迁移建构自我的知识体系）
裴波那契（Fibonacci leonardo，约1170-1250）是意大利著名数学家．在他的著作《算盘书》中许多有趣的问题，最富成功的问题是著名的“兔子繁殖问题”： 如果每对兔子每月繁殖一对子兔，而子兔在出生后第二个月就有生殖能力，试问第一月有一对小兔子第十二月时有多少对兔子？
1、1、2、3、5、8、13、21……

假设第n个月的兔子数目为f(n)，那么
f(n)=F(n-1)+f(n-2) 当n≥3，
f(1)=f(2)=1
讨论得出算法描述
Function有多少对兔子（第几月）
如果是第一月或第二月，那么就有一对兔子。
否则，（本月）兔子数=（本月-1）月的兔子数+（本月-2）月的兔子数
end Function

Function tu(ByVal month As Integer) As Integer
If month = 1 Or month = 2 Then
tu = 1
Else
tu = tu(month - 1) tu(month - 2)
End If
End Function

阅读
思考、分析、讨论，

编程实现。
尊重学生的个体发展，让学生进行自主探究学习，使用学主动、积极的学习新知识，培养他们的自学能力。

培养学生分析问题、解决问题能力，煅练学生“数学建模”建构主义的学习观认为：学习不是被动接收信息，而是主动地建构意义，以自己原有的知识经验为基础对外部信息进行主动地选择、加工和处理，人而获得自己的意义过程。
『在学生经历了上一问题解决的完整过程之后，再抛出较难的问题，并让学生自主完成。一方面，学生有了前面的基础，自主完成稍难一点问题的解决是完全可能的，另一方面，通过问题的“变式”，强化了新知，也训练了学生独立思考，分析解决问题的能力。』
深化知识
阅读教材的循环结构实现，比较讨论两种算法的区别和特点
学生讨论
培养学生分析问题、归纳、梳理知识的能力，通过两种算法的对比，让学生深入体会递归算法的魅力。加深对本节课所学知识的理解。
『通过比较两种算法的不同来加深学生对递归算法的理解是一种比较好的方法。不过，可惜的是这里没能看到学生讨论并总结不同的过程与结论。』
课堂小结
我们今天所学习的算法是“递归算法”，我们谈谈什么是递归算法，递归算法有什么特点。
师生讨论，共同小结：

1. 递归算法是数值层层调用实现的，函数先由上向下调用，当达到最底层后，再将函数值层层向上返回。(递下去，收回来，简称：递归)
2. 必须有个结束条件（有个该收回来的条件）
3. 可读性强
4. 计算机资源耗费大，所以效率比较底（常驻内存的数据比较多）

达成共识

『最后的课堂小结是统一学生思维结果的过程，这在活动性课堂教学中是必不可少的，它能帮助学生将发散的思维归结在教学的核心目标上，不至于让学生在一节课下来，感觉不知道学到了什么（其实学到了很多，只是没能总结出来）。然而，我们也看到，在小结的第4点上，在整个教学过程中，并没有给予关注。所以这个结论只是教师直接给出的，如果也能通过活动的方式来让学生体会到递归算法的低效就更好了。当然，这部分也许是下一节课的教学内容，本节课的小结只是一个提示。还有一种可能，就是在前面的算法比较环节中让学生体验到了递归算法的低效。但一般来说，如果要让学生通过问题来体验递归算法的低效性，就一定要通过比较的方法，而且需要足够的课时，相信，这一点在本节课上是难以实现的。』
布置作业
1.N！（用递归算法编程实现）
2.求1+2+3+4+5……N （用递归算法编程实现）
3.用递推算法实现“猴子吃桃”问题求解
巩固和发展本节课的学习内容。

【教学反思】

从游戏的方式导入活动，充分的调动学生的思维，渐渐的走入了“递归的思维”模式，从而引出“猴子吃桃”，使用的前面活动(礼物是什么?)的思维，诱导学生进入了“递归”思想解题。学生阅读教材范例“裴波那契”，培养学生的自学能力和知识迁移建构自我的知识体系。内化递归算法的实现，再由递归思维的逆向思维讨论“递推”的算法，进行比较计算机资源的耗费高，可读性差。为下一步导出结论做好了铺垫。
学好本节课的前提是：懂得自定义函数的使用方法，学生对自定义函数的理解程度，是本节课效果是否得以完成的关键。

【案例分析】

本案例语言流畅，结构清晰，对教材与学情的分析准确、到位，对教学目标和教学重、难点设计准确、合理。本案例覆盖的是程序设计中“递归法与问题解决”这一知识点，适合用于这一知识点的第一节课。
本案例能够通过“活动”的形式，使学生了解使用递归法设计算法的基本过程，使学生能够根据具体问题的要求，使用递归法设计算法、编写递归函数、编写程序、求解问题。
本案例能够通过“活动”（或游戏）的方式来导入教学，展开教学。而且能关注到培养学生自主学习探究能力的培养，并通过降低讨论问题的复杂程度和图示的方法来引导和帮助学生进行思考。再通过同一问题用不同算法来实现后的比较，来带领学生总结递归算法的优缺点。这些都是在比较难的算法教学内容的教学过程中，突破教学重难点的好的方法，很值得大家借鉴。
建议，在不同算法解决同一问题的比较设计中，能够更为详细的进行描述，并能给出整节课的时间安排，会增加本案例的可借鉴性。

【专家点评】

作者创设的“猜想游戏”情景，与递归算法有较高的关联性，而且长短适中，有助于学生迅速进入情景，进而通过引出“自定义函数”巧妙地引导学生走出情景。经过教师的精心设计，学生在较短的时间内就为递归算法做好了移植准备。
递归算法有一定的难度，对逻辑思维能力要求较高，如果选择切入的问题过于复杂，学生容易产生畏难情绪。教材中选用的“兔子问题”是一个经典的递归问题，但问题分析的复杂度较大，花费的学时较多。作者并没有拘泥于教材，而是精心设计任务调整难度，选择了相对简单的“猴子吃桃问题”作为学习递归函数的切入点，在难度上较为贴近学生的实际水平。另一方面，算法的内容大多很枯燥，不易调动学生兴趣，而“猴子吃桃问题”既生动又贴切，容易激发学生的兴趣，让学生在解决问题的过程中充分感受算法的魅力，获得成就感。作者对教材的处理，可谓之“依据教材又超越教材”，既保留了教材的精华，又通过适当的调整满足了学生的实际需求，带领学生由浅入深地接触到递归算法。在此过程中，采取的学习方法也有所改变，让学生通过自主探究来掌握相关内容，促进学生知识迁移和自我构建能力的提升。作者的设计可谓独具匠心。
值得商榷之处，所设计的教学内容用一个课时来完成，时间非常紧迫，特别是“自主构建”环节，需要一定的自主探究和教师讲解的时间。
（广东珠海一中高中部 魏小山）