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

教学设计 课程基本信息 学科 信息技术 年级 高一 学期 秋季 课题 2.4.2基于枚举算法的问题解决 教学目标 1.进一步体验算法思想，通过实例了解用枚举法解决问题的基本方法。（信息意识） 。 2. 理解枚举算法的核心思想，抽取数学模型（计算思维）。 3.体验枚举算法的执行效率，认识优化算法的必要性（数字化学习与创新） 教学重难点 教学重点： 1. 建立正确的数学模型，确定枚举方案。 2. 能结合实际问题，编写程序实现枚举算法并调试运行，解决问题。 教学难点： 1. 恰当安排枚举方式，感受不同算法的执行效率，体验算法优化在解决问题中的价值。 教学过程 一、导入 在前面的学习中，我们学习了三种程序结构，顺序结构，选择结构，循环结构。了解了解析算法的思想：通过找出解决问题的前提条件与结果之间关系的表达式，并计算表达式的值来实现问题的求解。 今天我们来一起学习一种新的算法枚举算法。枚举就是一一列举。枚举法在生活中也常常用到。 如：在一筐水果中找出坏掉的水果扔掉，一个一个查看，然后去除坏的水果。 在一串钥匙中找出所有能打开这把锁的钥匙，一把一把地试，找到然后取出。 忘记了三位数密码箱的密码，从000开始，001，002…………找到正确密码后记下来。 在计算机解决问题的过程中也常常用到这种方法。我们把它叫做枚举算法。 设计意图：复习以前所学内容，为这节课学习做铺垫，引入生活中的例子更好理解枚举算法。 二、新课讲授 枚举算法： 1、概念：依据已知条件，确定答案的大致范围，在此范围内列举出所有的可能的方法。 注意：一一列举，不能遗漏，不能重复，逐一检验要确定正确的检验条件。 2、实现方法：运用循环结构嵌套分支结构实现，流程图如右所示： 3、基本框架： for（列举所有可能解）:也可以使用while语句实现 if(判断条件）： 输出解 设计意图：学生学习枚举算法概念并分析其实现方法和基本框架，为解决实际问题做准备。 探究活动一： 票据上有一个4位数字组成的编号： 甲说：数字编号的前两位数字相同，但都不是零； 乙说：数字编号的后两位数字是相同的，但与前两位不同； 丙说：数字编号是一个整数的平方。 根据以上线索推断出编号。 学生思考：你怎样应用学过的知识进行推断？ 1、分析问题： 教师引导学生思考并回答 分析出已知条件、求解目标、已知和未知之间的关系 已知条件 : 四个数字应是AABB，其中A≠0，A≠B,且AABB是一个整数的二次方 求解目标 : 票据中的数字 为了方便表达枚举对象与检验条件，我们可以将这个四位数设为变量k,前两位上的数字设为变量A，后两位上的数字设为变量B,其中的一个整数设为变量c。 枚举对象 枚举范围 检验条件 A 1-9之间的整数 A≠B c*c=k B 0-9之间的整数 2、设计算法： 根据问题分析，只要一一列举出4位数字AABB中A与B的所有可能组合，保证A≠B 且A≠0. 3、编写程序，解决问题。 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) 4、保存文件，运行程序。 设计意图：通过实际案例体会用枚举算法解决实际问题的过程。 3、 实践活动 活动二．枚举法解“鸡兔同笼”问题 今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？（雉兔至少有一只） （1） 分析问题 列举出所有可能，逐一尝试验证，输出其中满足题目条件的鸡兔数量. 以上方案不太聪明，效率太低。 我们发现鸡和兔子头数量和为35，我们只需列举鸡的只数，兔的只数也相应确定，如下表： · 一一列举可能的解，即枚举范围是多少？ 鸡的数量：1~34 · 逐一检验可能的解，判断条件是什么？ 鸡与兔共94只脚 （2） 设计算法：输入数据、处理数据、输出结果 逐一列举，用循环结构就可以解决。一一校验，则需要用到分支结构，验证哪些情况满足问题的条件，如果满足就输出。 （3） 编程调试 代码1 循环执行34*34次 代码2 循环执行34次 我们从时间复杂度及代码的简化程度上分析，可以发现第二种方案更优，枚举需要一一列举所有情况，运算量较大，效率不够高，我们在用它解决问题时需要注意要选择恰当的枚举对象，尽量分析隐含条件，缩小枚举范围。 枚举算法要注意的问题： · 不能遗漏任何一个正确解 · 尽可能地缩小解的列举范围，提高算法的效率 设计意图：进一步体会枚举算法实现过程，并让学生体会解决问题时不同的算法效率不同，从而要注意优化算法。 枚举算法的应用： 想一想：以下问题可以用枚举算法解决吗？ 第1，4，5个问题可以用枚举法解决，其它问题不可以。因为枚举算法适用于答案数量有限并且可能的答案是能按照某种规则列举出来的问题。 说一说：除了上述问题之外，生活中有哪些问题是可以用枚举算法来解决的？ 逻辑问题：警察抓小偷问题，走迷宫问题，“二十四点”的趣味题等问题。 设计意图：通过例子学习枚举算法适用于哪些问题，并了解枚举算法适用的例子。 四、总结 1. 枚举算法的基本思想：一一列举，逐一检验 2. 枚举算法的结构特征：循环结构嵌套分支结构 3. 枚举算法的应用：注意优化算法，缩小枚举范围 设计意图：帮助学生梳理教学线索，总结重点内容。 五、布置练习 编写程序解决以下问题: 1：从2000年到2050年，哪些年份是闰年？ · 能够被4整除但不能被100整除的是闰年 · 能够被400整除的也是闰年 2：寻找1000以内的所有素数。 3、“水仙花数”是指一个三位自然数，其各位数字的立方和等于该数本身。编程输出所有的水仙花数，每行一个。 例如153是“水仙花数”，因为：153 = 13 + 53 + 33。 设计意图：布置课后练习，学生自测学习效果，进行查缺补漏。 学科网（北京）股份有限公司 $$