高中信息技术教科版（2019）必修一 4.3非数值计算 课件

非数值计算 页面统一为16:9宽幅画面比例尺寸；PPT统一格式为PPT或PPTX。 中文： 1. 课名：微软雅黑48号字； 2.（第一课时）：微软雅黑32号字； 3.学校名称：请填写全称； 4.学科、年级、主讲人、学校：华文楷体28号字（具体根据文字量可适当调整）。 英文 1.课名：字体以Times New Roman为主，字号一般使用32——36号，特别强调可以用40号； 2.（Period 1）：字体使用Arial，字号为28； 3.正文一般用24——28号，特别强调可用32号。 注意标点的规范（例如：中文省略号为……，可用Shift+数字键6打出中文省略号，英文省略号为…） 1 观看视频——初识递归 我们可以将递归简单类比为具有自相似性重复的事物。 ——视频来源于网络 2 斐波那契螺旋线也称“黄金螺旋线”,是根据“斐波那契 数列”画出来的螺旋曲线。 生活中的递归现象 ——图片均来源于网络 活动1：建立模型——定义递归 第1个月 第3个月 第6个月 第4个月 第2个月 每月兔子对数为1,1,2,3,5,8,13……从第3个月起，当月兔子对 数为前两月兔子对数之和。这个数列在数学上称做“斐波那 契数列”。 第5个月 第7个月 分析：设定每月兔子对数为f（n）,n为月份，可以递归定义为： f(n)= 1(n=1或n=2) f(n-1)+f(n-2)(n>2) 那么在一个函数的定义中直接或间接调用自身，这种方 法我们称之为递归,这个函数就是递归函数。 活动1：建立模型——定义递归 一种比较简单，可以直接求出结果 另一种是把问题分解成更小的问题，与原问题相同解决方法，需要调用自身。 def f(n): #定义斐波那契函数 if n==1 or n==2: return 1 else: return f(n-1)+f(n-2） 采用递归解决斐波那契数列问题，使用自定义函数： 活动1：建立模型——定义递归 def 函数名(参数列表): 函数体 return [返回值] 自定义函数 完成程序填空： def f(n): #定义阶乘函数 if ____①____: _____②_____ else: return __③_____ print(f(5)) f(n)= 1(n=1) f(n-1)*n (n>1) 活动2：举一反三——体验递归 问题：利用递归算法求5的阶乘（n!=1×2×…×n）,设函数f(n)=n!,由数学知识可知,n阶乘的递归定义为： 活动2：举一反三——体验递归 def f(n): f(5)=f(4)*5 f(4)=f(3)*4 f(3)=f(2)*3 f(2)=f(1)*2 f(1)=1 递推 问题逐渐缩小 return if n==1: return 1 else: 出口（边界条件） 不会无限循环 回归 f(n-1)*n print(f(5)) 归纳小结——递归的基本格式 以5的阶乘为例，我们可以小结出递归实现的基本格式： def f(n): 自定义函数   if n==1:              递归边界条件     return 1               直接求解   else:     return f (n-1)*n    调用自身，递归通式 递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。递推和回归，二者缺一不可。 递归可用“分”，“治”，“合”三字概括 观看视频 思考问题 1.使用什么图腾可以辨别现实和梦境？2.共展现几重梦境？ ——视频来源于网络 10 活动3：问题呈现——再识递归 现实生活 ----> 一层梦境 --->二层梦境 ---->三层梦境 现实生活<---- 一层梦境 <----二层梦境 <----三层梦境 问题： 假设人有多重梦境， 现实生活中的1s， 在第一层梦境的虚拟时间是0.05s， 在第二层梦境度过的虚拟时间就是第一层梦境的0.05倍，以此类推... 如果这个人有1层梦境，那么他在现实中度过1秒，就相当于真实时间+梦境的虚拟时间也就是1s+1s*0.05=1.05s。 如果进入到n层梦境，那他相当于度过了多少时间？有3层梦境呢？ 活动3：问题呈现——再识递归 未知的大问题 解决大问题 梦境1 梦境2 梦境3 递 归 递归出口(现实：真实时间） 已知的小的情况 图解递归——递归的过程 def dreamtime(n,x): #n是多少层梦境，x是真实时间 if n==0: return _①_ else: return ___②___+x*0.05**n print (dreamtime(_③_,1)) 设计算法——方法1：递归法 x dreamtime(n-1,x) 3 求3层梦境度过的时间？ 递归法通过自定义函数来实现。 第一要素 寻找递归边界条件 第二要素 找出递归通式,直接或间接调用自身。 第三要素 思考通过什么步骤 或公式实现。 递归的出口：必须有⼀个明确的结束条件 def 函数名称(参数列表): 函数体 return [返回值] 归纳小结——递归的三要素 分析：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 设计算法——方法2：迭代法 程序如下： y=1 x=float(input("请输入现实时间:")) for n in range(1,4): y=y+x*0.05**n print(y) 从已知条件出发，利用循环方式按照一定规则从前往后迭代计算，最后得到结果，这种解决问题方式称为迭代法。 归纳小结——迭代与递归的关系 迭代算法与递归算法都需要重复执行某些代码，两者既有区别又有密切的联系。 迭代 递归 重复方式：是重复反馈过程的活动，其目的通常是逼近所需目标或结果。 重复方式是重复调用函数自身。 结束方式：通常使用计数器结束循环。 结束方式：遇到满足终止条件的情况时逐层返回。 课堂总结——递归的特点 非数值计算 (递归） 递归：直接或间接地调用自身的方法称为递归。 迭代算法与递归算法的关系 分治策略 递归 三要素 将一个难以直接解决的大问题，分割 成一些较小的同类问题，各个击破 。 分：原问题分解成若干子问题 治：对子问题分别求解 合：子问题的解合并成原问题的解 自定义函数 寻找递归边界条件 找出递归通式 1.请分别运行迭代算法和递归算法程序输出斐波那契数列的第100个数和第1000个数，比较两种算法的效率，填写表格： 2.青蛙跳台阶问题：一只青蛙一次可以跳1级或2级台阶,求该青蛙跳n级的台阶总共有多少种跳法？ 巩固拓展——课后作业 算法设计 输出第100个数 （程序运行时间） 输出第1000个数 （程序运行时间） 迭代算法 递归算法 优点 缺点 递归算法 再 见 Lavf58.28.100 Lavf58.28.100 $$