3.5用递归法解决问题.docx

用递归法解决问题一、教材分析“算法的程序实现”是中学信息技术教化出版社算法与程序设计选修模块第三单元的内容，本节课是“递归算法的程序实现”，前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序以及本节的前一小节学问点“什么是自定义函数”的学习，在学习自定义函数的基础上，学习递归算法的程序实现是自定义函数的详细应用，培育学生“自顶向下”、“逐步求精”的意识起着重要的作用。课时支配：1课时二、学情分析教学对象是中学二年级学生，前面学习了程序设计的各种结构，在学习程序设计各种结构的应用过程中的培育了用计算机编程解决现实中的问题，特殊的学习循环语句的过程中，应用了大量的“递推”算法。前一节课学习了如何自定义函数，在此基础上学习深化学习和体会自定义函数的应用。以递推算法的逆向思维进行求解问题，在学习过程中体会递归算法的思想过程。多维度的思索问题和解决问题是提高学生的学习爱好关键。三、教学目标学问与技能：1、 理解什么是递归算法，学生用递归算法的思想分析问题2、 能够应用自定义函数方法实现递归算法的编程过程与方法：学生参加探讨，通过思索、动手操作，体验递归算法的方法情感看法与价值：结合数学中的实例，激发学生的数学建模的意识，培育学生多维度的思索问题和解决问题。四、教学重点难点重点：理解什么是递归算法，学生用递归算法的思想分析问题应用自定义函数方法实现递归算法的编程难点：应用自定义函数方法实现递归算法的编程五、教学过程进程老师活动学生活动设计意图创设情境课堂导入：今日很兴奋，特此我给大家打算了一份礼品（精致包装猴与兔艺术品），你们想知道里面有什么礼物吗？学生：想师：好！我们班有一位同学知道里面有什么礼物！（在上课之前事先告知其中的一个同学）但是他不能就这样告知大家，有一个规则可以让我们知道里面装的是什么规则是：1、从第一排的第一个同学起先。师生共同活动“找答案”运用情境教学法在此活动过程中能让学生初步从活动中体验”问题的发与收”从而走进了递归的思维模式，为进2、 每位同学只问他相邻的同学，每位同学最多只能被问一次，而且一个同学不能再问其次人，当任何一个同学知道了答案,要求马上告知曾经问过他的那个同学（不能告知其它同学）以此类推。3、 始终到得出答案为结束以嬉戏规则开展，我想让第一位同学告知大家，精装的礼物是什么？一步学习递归算法埋下伏笔启发主体师：前面我们学习了自定义函数，知道函数是为了实现某种功能而编写的一段相对独立的程序，并且可以多次的调用。算法描述：functionwhat（student）假如我知道答案，那么我就告知你否则，我要问下一位同学再告知你endfunction探讨活动过程，总结嬉戏规则，了解活动规律，并将活动过程进行算法描述分析问题确定方案,培育学生思维程序化，为下面新学习递归算法做好移植打算学习新知展示题：小猴吃桃：有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。其次天接着吃剩下桃子中的一个，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子？1、激励学生进行探讨，共同找寻答案或解决方法2、师生共同分析题：以4位同学排成了行，（设从行的后面起先的第一位同学知道第10的桃子数（1个），倒数其次位同学知道第9天的桃子数是）从老师提问排在前面第一位（第7天）的同学，你知道，你今日的桃子数有多少？目的是探讨出，只有倒数第一位同学知道，其它有同学都不知道,但是他只要知道他后一位同学的桃子数就可以求出本人所具有的桃子数，（后同学的桃子数+1）*2就是本人的桃子数。建立数学模型：假设第n,n<10天的桃子数为tao（n）那么tao=10n=ltao（n）=（tao（n+l）+1）*2n<10探讨、比较、分析、归纳推导数学建模实例教学，选择“小猴吃桃”这一题的目的是为了简化教材“裴波那契”数列的多函数调用，总是问题分析的困难性较大的特点，从使得重点难点得以轻松的突破。我们能不能这样设一个函数：算法描述：function你有多少桃子？（第几天）假如我第10天，那么我就有一个桃子。否则，我的桃子数=（前一天的桃子数+1）*2endfunction学生进行算法描述培育学生养成良好的编程习惯学生编程实现：示图帮助学生Functiontao(ByValdaysAsInteger)AsIntegerIfdays=10Thentao=1Elsetao=(tao(days+1)+1)*2EndIfEndFunction分析算法的实现过程算法实现过程的始末思维，学生编程实现培育学生的编程和调试程序实力，让学生获得胜利的体检自主我们再来看其次题：(学生阅读教材P68,让学生阅读教材敬重学生的个构建的“裴波那契”，培育学生的自学实力、和学问迁移建构自阅读体发展，让学我的学问体系)思索、分生进行自主探裴波那契(FibonacciIeonardo,约1170-1250)是意大利闻名数学家.在他的著作算盘书中很多好玩的问题，最富胜利的问题是闻名的“兔子繁殖问题”：假如每对兔子每月繁殖一对子兔，而子兔在诞生后其次个月就有生殖实力，试问第一月有一对小兔子第十二月时有多少对兔子？1、1、2、3、5、8、13、21假设第n个月的兔子数目为f(n),那么f(n)=F(n-l)+f(n-2)当n23,f(l)=f(2)=l探讨得出算法描述FUnetiOn有多少对兔子(第几月)假如是第一月或其次月，那么就有一对兔子。否则，(本月)兔子数=(本月T)月的兔子数十(本月-2)月的兔子数endFunctionFunctiontu(ByValmonthAsInteger)AsInteger析、探讨，究学习，运用学主动、主动的学习新学问，培育他们的自学实力。培育学生分析问题、解决问题实力，煨练学生“数学建模”建构主义的学习观认为：学习不是被动接收信息，而是主动地建构意义，以自己原有的Ifmonth=1Ormonth=2Thentu=1编程实现。学问阅历为基础对外部信息Elsetu=tu(month-1)+tu(month-2)EndIfEndFunction进行主动地选择、加工和处理，人而获得自己的意义过程。深化学问阅读教材的循环结构实现，比较探讨两种算法的区分和特点学生探讨培育学生分析问题、归纳、课堂我们今日所学习的算法是“递归算法”，我们谈谈什么是递梳理学问的实小结归算法，递归算法有什么特点。师生探讨，共同小结：力，通过两种算法的对比，1、 递归算法是数值层层调用实现的，函数先由上向下调用，当达到最底层后，再将函数值层层向上返回。（递下去，收回来，简称：递归）2、 必需有个结束条件（有个该收回来的条件）3、可读性强4、计算机资源耗费大，所以效率比较底（常驻内存的数据比较多）达成共识让学生深化体会递归算法的魅力。加深对本节课所学学问的理解。布置1、N!（用递归算法编程实现）巩固和发展本作业2、 求1+2+3+4+5N（用递归算法编程实现）3、 用递推算法实现“猴子吃桃”问题求解节课的学习内容。六、教学反思从嬉戏的方式导入活动，充分的调动学生的思维，慢慢的走入了“递归的思维”模式，从而引出“猴子吃桃”，运用的前面活动（礼物是什么？）的思维，诱导学生进入了“递归”思想解题。学生阅读教材范例“裴波那契”，培育学生的自学实力、和学问迁移建构自我的学问体系。内化递归算法的实现，再由递归思维的逆向思维探讨“递推”的算法，进行比较计算机资源的耗费高，可读性差。为下一步导出结论做好了铺垫。学好本节课的前提是：懂得自定义函数的运用方法，假如学生对自定义函数理解程度，是本节课效果是否得以完成的关键