4.3非数值计算 教学设计

4.3非数值计算 教学设计 课程基本信息 学科 信息技术 年级 高一 学期 秋学期 课题 非数值计算 教学目标 1. 理解递归的含义，能找出递归问题中缩小问题规模的递归处理方法及递归算法的三要素。 2.能用程序实现递归算法，了解递归的过程，学会用简单模式解决复杂问题的方法。 3.领悟递归的基本思想，体验递归思想在实际生活中的应用。 教学重难点 教学重点： 1. 理解什么是递归算法，学生使用递归算法的思想解决问题 2. 了解递归的三要素 教学难点： 1. 用递归的思想去理解和解决问题 2. 将大问题分解为小问题，找到递归通式和边界条件。 教学过程 （一）新课导入 观看视频—初识递归《盗梦空间》电影片段，重温电影情节。 可以将递归简单类比为具有自相似性重复的事物。这是递归的形象表示。 （二）新课内容 1.生活中的递归现象 斐波那契螺旋线也称“黄金螺旋线”是根据“斐波那契数列”画出来的螺旋曲线。 设计意图：学生通过观看《盗墓空间》》电影片段发现自相似性重复的事物，引出递归的形象表示，并延伸到生活中的递归现象。从斐波那契螺旋线回顾上节课学过的斐波那契数列的内容，学习新的解决问题的办法。 活动1：建立模型—定义递归 每月兔子的对数为1,1,2,3,5,8,13……，从第三个月起，当月兔子数为前两月兔子数之和。这个数列在数学上称做“斐波那契数列”。 分析：设定每月兔子对数为f（n）,n为月份，可以递归定义为： 这种定义方式将问题分成了两种情况，其中一种比较简单，可以直接求出结果；另一种是把问题分解成规模更小的、具有与原问题相同解法的问题。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况，这种使用方法我们称之为递归，这个函数就是递归函数。 采用递归解决斐波那契数列问题，使用自定义函数：def f(n): #定义斐波那契函数 if n==1 or n==2: return 1 else: return f(n-1)+f(n-2） def 函数名(参数列表): 函数体 return [返回值] 递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。 设计意图：斐波那契数列是一个非常典型的递归实例，充分体现了用简单模式解决复杂问题的递归算法含义。递归函数通过自定义函数来实现，这是前面课程学习过的内容，做到温故知新。 活动2：举一反三—体验递归 问题：利用递归算法求5的阶乘（n!=1×2×…×n）, 设函数f(n)=n!,由数学知识可知,n阶乘的递归定义为： 完成程序填空： def f(n): if ____①____: _____②_____ else: return _____③_____ print(f(5)) 设计意图：求n的阶乘——递归最最典型的案例，以代码填空的方式，有目的的将部分代码进行留白，引导学生进行参考斐波那契数列模仿完成程序代码并调试运行求得5的阶乘。 小结：通过刚才的实例，我们可以总结出递归实现的基本格式如下（以5的阶乘为例）： def f(n): 自定义函数   if n==1:     递归边界条件     return 1   直接求解   else:     return f (n-1)*n 调用自身，递归通式 2.归纳小结—递归的基本思想 递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归，二者缺一不可。 递归可用“分”，“治”，“合”三个字概括 现在，我们再来看5的阶乘问题的递归过程：def f(n): if n==1: return 1 else: return f(n-1)*n print(f(5)) print(f(5)) f(5)=f(4)*5 f(4)=f(3)*4 递推 f(3)=f(2)*3 回归 f(2)=f(1)*2 问题逐渐缩小 f(1)=1 出口（边界条件） 不会无限循环 设计意图：学生通过前面的尝试体验已经对递归用法有了大概的了解，在本环节中进一步归纳总结，以5！为例体验递归调用过程，了解递归解决问题的基本模式。这种通过具体的实例、算法中不断发现的问题的规律，更加有助于学生对知识进行内化，并将此规律运用于解决新的问题，从而真正达到应用、迁移的目的。 3.观看视频，思考问题 (1)使用什么图腾可以辨别现实和梦境？ (2)共展现几重梦境？ 活动3：问题呈现—再识递归 现实生活 ------> 一层梦境 ----------->二层梦境 ---------->三层梦境 现实生活 <------ 一层梦境 <----------二层梦境<---------- 三层梦境 假设人有多重梦境，现实生活中的1s在第一层梦境的虚拟时间是0.05s，在第二层梦境度过的虚拟时间就是第一层梦境的0.05倍，以此类推...如果这个人有1层梦境，那么他在现实中度过一秒，就相当于真实时间+梦境的虚拟时间也就是1.05s，那如果这个人有n层梦境，那他相当于度过了多少时间？有3层梦境呢？ 递归的过程—图解递归 设计意图：通过对《盗梦空间》电影片段中相关场景的分析，学生初步了解递归的过程，并用动画的形式深入理解递归算法的递和归的过程，并强调递归的“出口”，是递归算法的典型特征，以便引出后面的要素之一“边界条件”。 设计算法——方法1：递归法 求3层梦境度过的时间？ def dreamtime(n,x): #n是多少层梦境，x是真实时间 if n==0: return _①_ else: return ___②___+x*0.05**n print (dreamtime(_③_,1)) 设计算法——方法1：迭代法 分析：y就是度过的时间，x是真实时间，n是多少层梦境，可得出关系式：从已知条件出发，利用循环方式按照一定规则从前往后迭代计算，最后得到结果，这种解决问题方式称为迭代法。 y = x+x*0.05^1+x*0.05^2+......+x*0.05^n 当n=3时： y = 1+1*0.05^1+1*0.05^2+1*0.05^3=1.052625 程序如下： 设计意图：由“盗梦空间”的实例深入了解递归的过程，有了前面的斐波那契数列和阶乘的基础，此处用盗梦空间题目让学生尝试独立完成代码，更容易理解和掌握，并深刻感受到递归法描述问题的简洁、直白。学生还可以使用之前学过的迭代的方式解决问题，然而循环的方法有时并不会那么清晰地描述解决问题的步骤，递归定义中给出了两种不同情况的解决方法。基础较好的同学可以直接编写完整代码，无需用填空的方式。由递归到回顾学习过的迭代用法，让学生感受到一种全新的解决问题的方式，并为接下来引出迭代和递归的关系做铺垫。 4.递归的三要素 (1)第一要素：递归法通过自定义函数来实现，明确你这个函数想要做什么。 def 函数名称(参数列表): 函数体 return [返回值] (2)第二要素：寻找递归边界条件。递归的出口：必须有⼀个明确的结束条件。通过分支判断“递”还是“归” (3)第三要素：找出递归通式,直接或间接调用自身。 规模大、较难解决的问题变成规模小、易解决的同一问题，通过什么步骤或公式实现。 活动4：比较迭代算法和递归算法 迭代算法与递归算法都需要重复执行某些代码，两者既有区别又有密切的联系。 迭代 递归 重复方式：是重复反馈过程的活动，其目的通常是逼近所需目标或结果。 重复方式是重复调用函数自身。 结束方式：通常使用计数器结束循环。 结束方式：遇到满足终止条件的情况时逐层返回。 设计意图：学生通过多个例题了解解决同一问题不同算法迭代法和递归法，通过过程和结果更加直观地总结出递归和迭代的异同，以此布置课后作业，以学生为主体，通过多种实践方法来自己寻找解决问题的办法并进行归纳总结。 5. 课堂小结 本节课我们学习了递归的定义，递归的思想体现分治策略，将一个难以直接解决的大问题分解成若干子问题，对子问题分别求解，子问题的解合并成原问题的解，了解了递归的三要素，尝试合理使用递归算法理解和解决问题，完成课后作业: 1.请分别运行迭代算法和递归算法程序输出斐波那契数列的第100个数等，并比较两种算法的效率，填写如下表格：递归算法： def f(n): if n==1 or n==2: return 1 else: return f(n-1)+f(n-2） 迭代算法： def f(n): f1=f2=1 for i in range(3,n+1): f1,f2=f2,f1+f2 return f2 算法设计 输出第100个数（程序运行时间） 输出第1000个数（程序运行时间） 迭代算法 递归算法 优点 缺点 递归算法 2.青蛙跳台阶问题：一只青蛙一次可以跳1级或2级台阶,求该青蛙跳n级的台阶总共有多少种跳法？ 学科网（北京）股份有限公司 $$