3.5 经典算法—枚举与递归 课件 -青岛版（2024）初中 信息技术 第四册 课件

第5课 经典算法—枚举与递归 第三单元 基于算法的编程基础 山东省2024青岛版初中Python同步教学设计 1 技术 支持 1 什么是枚举、递归算法？ 2 如何使用枚举算法解决百钱买百鸡问题？如何用递归算法解决斐波那契数列问题？ 3 在程序设计中如何使用枚举、递归算法解决生活中的问题？ 学习目标 2 目 录 contents 01 02 探究二 用递归算法解决问题 03 探究三 我实践我创新 04 课堂小结 探究一 用枚举算法解决问题 3 基本思想 枚举算法的基本思想是把问题所有可能的解一一列举，然后逐一判断每一个列举出的解是否为正解。 一一列举，逐个检验 解题 思路 探究一 用枚举算法解决问题 1 不能遗漏任何一个正确解 尽可能地缩小解的枚举范围，提高算法的效率 确定枚举对象、范围 确定判断条件 逐一枚举可能解并判断 4 操作 模块 程序 一一列举 循环结构 for语句 / while语句 逐个比较 判断分支结构 if语句 枚举算法程序实现 1 1 探究一 用枚举算法解决问题 在一串不同的钥匙中找到机房门钥匙。 计算机程序 1 2 3 计算并联电路的电阻值。 查找100以内所有能同时被3和7整除的正整数。 下列问题能否用枚举算法求解 1 1 探究一 用枚举算法解决问题 优点：是对现实生活的直接描述，易于理解。 注意事项：要做到既不遗漏任何一个解，也不重复枚举。 探究一 用枚举算法解决问题 1 百钱百鸡 100元买100只鸡，公鸡5元1只，母鸡3元1只，小鸡1元3只。求公鸡、母鸡和小鸡各应买的数量。 最多买100只鸡，每种鸡的数量范围是1—100，我们用三个变量来存储3种鸡的数量，a代表公鸡数量，b代表母鸡数量，c代表小鸡数量，可列出方程组： 0<=a<=100,0<=b<=100,0<=c<=100 a+b+c=0, 5*a+3*b+c/3=100 7 8 x+y+z=100 and 5*a+3*b+c/3=100 开始 结束 z=z+1 探究一 用枚举算法解决问题 1 x=1 to100 y=1 to100 Z=1 to100 输出x、y、z y=y+1 x=x+1 F F F F for x in range(1,100): for y in range(1,100): for z in range(1,100): if (x+y+z=100) and (x+y+z=100) print(“鸡翁:”,x,“鸡翁母:”,y,“鸡雏:”,z) 探究二 用递归算法解决问题 2 斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。         斐波那契数列指的是这样一个数列： 0，1，1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，2584，4181，6765，10946，17711……         它的规律是：这个数列从第 3 项开始，每一项都等于前两项之和。 9 探究二 用递归算法解决问题 2 分析问题 10 探究二 用递归算法解决问题 2 1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月 小兔 1 1 1 2 3 5 8 13 21 34 55 大兔 1 1 2 3 5 8 13 21 34 55 89 合计 1 1 2 3 5 8 13 21 34 55 89 144 分析问题 11 探究二 用递归算法解决问题 2 递归算法：函数不断引用自身，直到引用的对象已知，否则 会成为死循环而不能正常结束。思路清晰，代码少。 斐波那契数列 12 探究二 用递归算法解决问题 2 13 探究二 用递归算法解决问题 2 开始 返回f(n)=f(n-1)+f(n-2) n==1 or n==2 输出月份 返回f(n)=1 输出x、y、z 结束 输出n个月后兔子对数为f(n) 设计算法 14 18% 28% 探究二 用递归算法解决问题 1 编写程序 def f(n): if n==1 or : return 1 else: return f(n-1)+f( ) n=int(input(“请输入月份：”)) print（n,“个月后兔子对数为：”，f(n)） 15 探究二：用递归算法解决问题 2 递归 递归算法是把问题转化为规模缩小了的同类问题的子问题，然后递归调用函数（或过程）来表示问题的解。因此，设计递归算法的关键在于，确定递归公式（过程的描述