2.4.2 基于枚举算法的问题解决 ppt课件（14张ppt）+教案-2023新中图版《高中信息技术》必修第一册.rar

课课题题2.4.2 基于枚举算法的问题解决课型课型新授课课时安排课时安排1教教 学学 过过 程程教教学学目目标标理解枚举算法的基本原理和求解问题的基本过程，能够完善程序代码实现算法。掌握枚举算法解决问题的基本过程，学会使用枚举算法解决生活中的实际问题，提高信息安全意识。体验枚举算法的执行效率，认识优化算法的必要性。教教学学难难点点 教教学学重重点点重点：理解枚举算法的基本思想，能够结合实际问题完善程序代码并调试运行，解决问题。难点：体验枚举算法的执行效率，认识优化算法的必要性。教学教学 方法方法讲授法、任务驱动法、合作探究法、体验法、云课堂演示等板板书书设设计计2.4.1 基于解析算法的问题解决枚举算法：依据已知条件，确定答案的大致范围，在此范围内列举出所有的可能的方法。注意：不能遗漏，不能重复优化算法：缩小枚举范围，提高解决问题的效率一、情景导入：数字解密问题票据上有一个 4 位数字组成的编号：甲说：数字编号的前两位数字相同，但都不是零；乙说：数字编号的后两位数字是相同的，但与前两位不同；丙说：数字编号是一个整数的平方。根据以上线索推断出编号。学生思考：你怎样应用学过的知识进行推断？二、新知探索：1.数字解密问题：分析问题：教师引导学生思考并回答分析出已知条件、求解目标、已知和未知之间的关系已知条件:四个数字应是 AABB，其中 A0，AB,且 AABB 是一个整数的二次方求解目标:票据中的数字已知与未知的关系:要求解的 4 位数字的编号必须同时满足所有的已知条件设计算法：根据问题分析，只要一一列举出 4 位数字 AABB 中 A 与 B 的所有可能组合，保证 AB 且 A0.装订线 授课教师：授课班级：教教学学反反思思本节课是在学生已经学习了解析算法的基础上学习的，因此课堂效率较高。首先通过“数字解密问题”的求解让学生理解枚举算法的基本原理和提高信息安全的意识，再以“输出 1000以内的素数”为例，让学生感受算法的效率，认识到优化算法的必要性，达到了预期的教学计划。再验证二次方问题，就可以得到同题的解。因此，该问题可使用枚举算法求解完成学生将老师展示的流程图半成品补充完整：编程实现与调试：学生在 Python 中 将下面程序补充完整并调试运行：import mathfor 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:print(票据编号是:,k)教师讲授枚举算法的基本原理，强调该算法的基本特征：枚举对象、枚举范围和验证条件 三、探究：输出 1000 以内所有素数分析问题：已知条件：n1000 素数的定义（只有 1 和它本身两个因数的数）求解目标：输出 1000 以内所有的素数设计算法：学生完善教师在白板上的流程图半成品编程实现与调试：（1）种k=1for n in range(2,1000):for j in range(2,n):if n%j=0:k=0 if k=1:print(n)k=1（2）种import mathk=1for n in range(2,1000):m=math.ceil(math.sqrt(n)+1 if n=2:print(n)for j in range(2,n):if n%j=0:k=0 break if k=1:print(n)k=1四、讨论归纳：1.学生体验完运行调试程序后，填写下表：方案 1方案 2枚举对象枚举范围验证条件2.师生共同总结：方案 2 的运算速度更快，效率更高，原因是方案 2 的程序缩小了枚举范围，进而减少了逐一验证的次数，提高了程序的运算效率，因此在以后求解问题过程中对代码优化很有必要的。3.教师讲授：算法效率：通常，算法的效率主要指算法执行时间的高效以及努力降低对存储空间的需求。这既是算法设计追求的目标，也是衡量一个算法优劣的重要标准。算法的效率实际上指的是执行算法时所需要的时间与空间，分为算法的时间复杂度(即时间效率)和空间复杂度(即空间效率)。算法的时间复杂度主要指算法在运行时花费的时间，但这里的“运行”是抽象的运行，并不是在具体计算机上的运行。时间复杂度可以通过测量算法步骤的执行次数来计算。对于同一个问题，如果有多个算法可以解决，那么步骤操作次数少、执行时间短的算法显然效率较高。空间复杂度主要指算法在执行时所需要的最大存储空间的大小。在计算机发展的早期，计算机的存储容量很小，所以人们很重视空间复杂度。但随着计算机技术的迅速发展，目前计算机的存储容量已经实现了很大的提升，许多时候也就不再关注算法的空间复杂度。因此，现在当我们评价一个算法效率的时候，更多的是在研究它的时间复杂度。五、作业：1.能不能运用今天所学知识任意破解别人的密码？2.如何保护自己的密码安全？人教中图版(2019)数据与计算 2.4 常见算法的程序实现人教中图版(2019)数据与计算 2.4 常见算法的程序实现票据上有一个4位数字组成的编号：甲说：数字编号的前两位数字相同，但都不是零；乙说：数字编号的后两位数字是相同的，但与前 两位不同；丙说：数字编号是一个整数的平方。根据以上线索推断出编号。票据中模糊数字推断问题：人教中图版(2019)数据与计算 2.4 常见算法的程序实现已知已知已知已知条件条件条件条件 :四四个数字应是个数字应是AABBAABB，其中，其中A A00，AAB,B,且且AABBAABB是一个是一个整数的二次方整数的二次方求解求解求解求解目标目标目标目标 :票据中的票据中的数字数字分析问题：已知与未知的关系已知与未知的关系已知与未知的关系已知与未知的关系 :要求解的要求解的4 4位数字的编号必须同时满足所有的已知条件位数字的编号必须同时满足所有的已知条件人教中图版(2019)数据与计算 2.4 常见算法的程序实现设计算法：根据问题分析，只要一一列举出4位数字AABB中A与B的所有可能组合，保证AB且A0.再验证二次方问题，就可以得到同题的解。因此，该问题可使用枚举算法求解完成人教中图版(2019)数据与计算 2.4 常见算法的程序实现编程实现与调试:importmathforAinrange(1,10):forBinrange(0,10):ifA!=B:k=A*1000+A*100+B*10+Bc=int(math.sqrt(k)ifc*c=k:print(票据编号是:,k)人教中图版(2019)数据与计算 2.4 常见算法的程序实现枚举枚举算法：算法：依据问题的已知条件，确定答案的大致范围，在此范围内列举出它所有可能情况的方法。设计算法设计算法编程实现与调试编程实现与调试分析问题分析问题保存文件保存文件适合解决求解的答案数量有限，并且可能的答案是能按照某种规则列举出来的问题。例如，用枚举法解决一些数学问题(“韩信点兵”“鸡兔同笼”等)、益智游戏和逻辑推理等。人教中图版(2019)数据与计算 2.4 常见算法的程序实现分组探究：输出1000以内所有素数素数是在大于1的自然数中，除了1和它本身以外不再有其他因数的数，如2,3,5,7,11,人教中图版(2019)数据与计算 2.4 常见算法的程序实现分析问题：已知条件已知条件求解目求解目标 n1000 素数的定义（只有1和它本身两个因数的数）输出1000以内所有的素数人教中图版(2019)数据与计算 2.4 常见算法的程序实现设计算法：开始K=1结束人教中图版(2019)数据与计算 2.4 常见算法的程序实现k=1for n in range(2,1000):for j in range(2,n):if n%j=0:k=0 if k=1:print(n)k=1import mathk=1for n in range(2,1000):m=math.ceil(math.sqrt(n)+1 if n=2:print(n)for j in range(2,n):if n%j=0:k=0 break if k=1:print(n)k=1人教中图版(2019)数据与计算 2.4 常见算法的程序实现方案方案1方案方案2枚举对象枚举范围验证条件21 00000021 0000002n n2(n n的整数部分的整数部分 +1)逐一验证是否能整除逐一验证是否能整除n n逐一验证是否能整除逐一验证是否能整除n n讨论归纳：人教中图版(2019)数据与计算 2.4 常见算法的程序实现课堂总结：枚举算法思想在生活中解决问题的适用情况及特点：枚举算法思想在生活中解决问题的适用情况及特点：1.求解的答案数量有限。求解的答案数量有限。2.所有的可能情况都符合一定的规则。所有的可能情况都符合一定的规则。人教中图版(2019)数据与计算 2.4 常见算法的程序实现算法效率：算法效率：算法的效率实际上指的是执行算法时所需要的时间与空间，分为算法的时间复杂度(即时间效率)和空间复杂度(即空间效率)。时间复杂度可以通过测量算法步骤的执行次数来计算。空间复杂度主要指算法在执行时所需要的最大存储空间的大小。人教中图版(2019)数据与计算 2.4 常见算法的程序实现课后思考：课后思考：1.能不能运用今天所学知识任意破解别人的密码能不能运用今天所学知识任意破解别人的密码？2.如何保护自己的密码安全？如何保护自己的密码安全？