2.4.2基于枚举算法的问题解决 课件 2023—-2024学年人教/中图版（2019）高中信息技术必修1

分析问题 分析出已知条件、求解目标和已知与未知的关系。 设计算法 然后推导构建出解析式。 编程调试 最后将数学解析式转换成程序表达式，进行编程实现并调试。 解析算法 基于解析算法的问题解决 课堂小结 2.4 常见算法的程序实现 1.基于解析算法的问题解决 2.基于枚举算法的问题解决 体验探索 鸡兔同笼 问题描述 ：一个笼子里面关了鸡和兔子（鸡有 2 只脚，兔子有 4 只脚，没有残疾的），上有35个头，下有94只足，问笼子里面有多少只鸡，有多少只兔子。 解析算法 1）分析问题 已知条件：假设鸡有x只,兔子有y只，头a有35个，足b有94足 求解 ：x,y值 二者之间的关系：x+y=a 2x+4y=b 2）设计算法 解析式x=2a-b//2 y=b//2-a 3）编程测试 a=35 b=94 x=2*a-b//2 y=b//2-a print("鸡有：",x,"只") print("兔子有：",y,"只") 鸡 兔 头的数量 脚的数量 1 1 1+1=2 1*2+1*4=6 1 2 1+2=3 1*2+2*4=10 1 3 1+3=4 1*2+3*4=14 …… …… …… …… 34 1 34+1=35 34*2+1*4=72 穷举法（枚举法）解决鸡兔同笼问题 一一列举可能的解，即枚举范围是多少？比如鸡是1~34只 逐一检测可能的解，判定条件是什么？比如头的数量1+3=4 脚的数量 1*2+1*4=6 1.分析问题 2.设计算法 一一列举 循环 逐一检测 分支 开始 鸡从1-34序列中依次取数 兔子的数量=35-鸡 2*鸡+兔子*4==94 输出鸡和兔子的数量 结束 False False True True for chicken in range(1,35): for rabbit in range(1,35): if (chicken+rabbit==35 and 2*chicken+4*rabbit==94): print("鸡有",chicken,"只。") print("兔子有",rabbit,"只。") 3.编程调试 优化程序 for chicken in range(1,35): for rabbit in range(1,24): if (chicken+rabbit==35 and 2*chicken+4*rabbit==94): print("鸡有",chicken,"只。") print("兔子有",rabbit,"只。") 　　枚举算法，也称枚举法是依据问题的已知条件，确定答案的大致范围，在此范围内逐一列举出它所有可能的情况的方法。在列举过程中，既不能遗漏，也不能重复，通过逐一判断，验证哪些情况满足问题的条件，从而得到问题的答案。 2.4.2 基于枚举算法的问题解决 １.基本概念 枚举算法解题的基本思路： （1）确定枚举对象、范围和判定条件。 （2）逐一枚举可能的情况并验证每个情况是否符合条件。 枚举算法的思想： 一一列举 逐一检验 开始 枚举值在给定范围吗？ 取下一个枚举值 枚举值符合条件吗？ 输出该枚举值 结束 False False True True 循环 分支 问题：票据上有一个4位数字组成的编号，甲说：数字编号的前两位数字相同，但都不是零；乙说：数字编号的后两位数字是相同的，但与前两位不同；丙说：数字编号是一个整数的平方。根据以上线索推断出编号。 例1 票据中模糊数字推断问题 假设四个数字应是AABB，其中A≠ 0，A≠B，且AABB是一个整数的二次方。 已知条件 求解目标 二者的关系 票据中的数字。 要求解的4位数字的编号必须同时满足所有的已知条件。 分析问题 设计算法 根据问题分析，只要一一列举出4位数字AABB中A与B的所有可以组合，保证A≠B且A ≠0,再验证二次方问题，就可以得到问题的解。因此，该问题可使用枚举算法求解完成，其算法的流程图如右所示： 结束 开始 A=1 A<10 K=1000A+100A+10B+B C=sqrt(k)的整数部分 A ≠B c*c=k 输出票据编号k B=B+1 B=0 B<10 A=A+1 False False False False True True True 编程实现与调试 import math A=1 while A<10: B=0 while B<10: if A!=B: k=A*1000+A*100+B*10+B c=int(math.sqrt(k))