2.4.2 基于枚举算法的问题解决课件2024-2025学年高一上学期高中信息技术必修1第2章人教/中图版（2019）

2.4.2基于枚举算法的问题解决 年 级：高一年级 学 科：信息技术（人教/中图版） 1 复习 顺序 结构 选择 结构 循环 结构 解析算法 根据问题的前提条件与所求结果之间的关系，找出求解问题的数学表达式，并通过表达式的计算来实现问题的求解 2 生活中的枚举 在一筐水果中找出坏掉的水果扔掉 在一串钥匙中找出所有能打开这把锁的钥匙 忘记了三位数密码箱的密码 一个一个查看，然后去除坏的水果 一把一把地试，找到然后取出 从000开始，001，002…………找到正确密码后记下来 共同点？ 一一列举 逐一检验 概念：枚举法是依据问题的已知条件，确定答案的大致范围，在此范围内列举出它所有可能情况的方法。 不遗漏 不重复 检验条件 （一）枚举算法的概念及特征 一一列举 循环结构（for语句、while语句） 逐一检验 分支结构（if判断语句） （二）枚举算法实现方法 for（列举所有可能解）: if(判断条件）： 输出解 也可以使用while语句实现 （二）枚举算法实现方法 枚举算法基本框架： 6 票据上有一个4位数字组成的编号： 甲说：数字编号的前两位数字相同，但都不是零； 乙说：数字编号的后两位数字是相同的，但与前两位不同； 丙说：数字编号是一个整数的平方。 　　根据以上线索推断出编号。 活动一 （三）如何设计枚举算法 例：票据中模糊数字推断问题。 7 1. 分析问题 已知条件：假设4位数字的编号是AABB，其中A≠0，A≠B，且AABB是一个整数的二次方； 求解目标：票据中的数字 变量A 变量B 变量k 变量c 枚举对象 枚举范围 检验条件 A B 1—9之间的整数 0—9之间的整数 A≠B c*c=k （三）如何设计枚举算法 8 一一列举 逐一检验 枚举对象 枚举范围 检验条件 A B 1—9之间的整数 0—9之间的整数 A≠B c*c=k 2. 设计算法 9 import math for A in range(1, 10): for B in range (0, 10): if A != B: k = A * 1000 + A * 100 + B * 10 + B c = int(math.sqrt(k)) # 求票据中数字的平方根并取其整数部分 if c * c == k: # 若k是完全平方数，则找到该票据编号 print("票据编号是：", k) 3. 编程调试 （三）如何设计枚举算法 4. 保存文件，运行程序 10 （四）枚举算法应用 活动二 今有雉兔同笼， 上有三十五头， 下有九十四足， 问雉兔各几何？ （雉兔至少有一只） 11 分析问题 鸡 兔 头的数量 脚的数量 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 12 13 鸡 兔 脚的数量 1 34 1 * 2 + 34 * 4 = 138 2 33 2 * 2 + 33 * 4 = 136 3 32 3 * 2 + 32 * 4 = 134 4 31 4 * 2 + 31 * 4 = 132 … … … 34 1 34 * 2 + 1 * 4 = 72 我们发现鸡和兔子头数量和为35 方案总数瞬间少了很多 13 14 一一列举可能的解，即枚举范围是多少？ 鸡的数量：1~34 逐一检验可能的解，判断条件是什么？ 鸡与兔共94只脚 2 * chicken + 4 * rabbit == 94 分析问题 14 15 设计算法 15 16 一一列举 逐一检验 循环执行34*34次 编写程序 16 17 一一列举 逐一检验 循环执行34次 算法优化 17 枚举算法要注意的问题 不能遗漏任何一个正确解 尽可能地缩小解的列举范围，提高算法的效率 18 可以用枚举算法解决吗 破解密码 求方程2x+y =9的整数解 寻找1000以内的所有素数 求方程2x+y =9的正整数解 求方程2x+y =9的实数解 19 一名警察抓获了4个盗窃嫌疑犯A、B、C、D，他们的供词如下： A说：“不是我偷的”； B说：“是A偷的”； C说：“不是我”； D说：“是B偷的”。 他们4个人中只有一个人说了真话，小偷是谁？ （四）枚举算法应用 20 21 （五）小结 22 23 编写程序解决以下问题： 1：从2000年到2050年，哪些年份是闰年？ 能够被4整除但不能被100整除的是闰年 能够被400整除的也是闰年 2：寻找1000以内的所有素数。 练习 23 3.“水仙花数”是指一个三位自然数，其各位数字的立方和等于该数本身。编程输出所有的水仙花数，每行一个。 例如153是“水仙花数”，因为：153 = 13 + 53 + 33。 24 谢谢聆听 25 $$