第三单元《第14课枚举算法》教学课件 -2023—2024学年浙教版（2020）初中信息技术八年级上册

第十四课 枚举算法 1 密码锁 我们知道一般的带密码的行李箱都要三位密码，要去旅游的你突然忘记了行李箱的密码的某一位，没有额外工具的情况下和其他人的帮助下，改怎么办？ 2 生活中的穷举法 你还要想法生活中其他利用穷举法的情况吗？ 生活中利用穷举法解决问题一般步骤是什么？ 3 什么是穷举（枚举）法 穷举（枚举）法就是一一列举所以可能的情况，再逐个验证。 4 穷举（枚举）法的一般思路 5 1、框定候选解的范围 2、在范围内去枚举所有的可能解，逐个验证 3、从而求得问题的可行解或者最优解 枚举例题分析-鸡兔同笼 在一个笼子里有若干只鸡与若干只兔子，其中脚有x只，头有y个，问鸡和兔子各有几只。其中还存在若干只鸡单脚站立，问可能的方案总数。 单脚鸡 1 2 双脚鸡 5 3 兔 0 1 6 鸡兔同笼-确定候选解的范围 分析:我们要用枚举法找到所有的答案，分为两步 1、确定候选解的范围 2、逐个验证 设 单脚鸡有a只。 双脚鸡有b只。 兔子有c只。 a、b、c的范围分别？ 0<=a<=y 0<=b<=y 0<=c<=y 7 鸡兔同笼-逐个验证 分析:我们要用枚举法找到所有的答案，分为两步 1、确定候选解的范围 2、逐个验证 a、b、c要满足什么条件？ 0<=a<=y 0<=b<=y 0<=c<=y 单脚鸡，有a只，则有a个头，a只脚 双脚鸡，有b只，则有b个头，2*b只脚 四脚兔，有c只，则有c个头，4*c只脚 a+b+c=y a+2b+4c=x 8 建立模型 问题就变成了给出x和y，求满足条件的a、b、c的组合多少种？ 其中0<= a、b、c<=y 要满足条件： a+b+c=y a+2b+4c=x 9 流程图 请补充完成流程图 10 流程图 11 编程解决问题 请补充完成程序 12 编程解决问题 13 算法优化思路 枚举法的特点：算法设计、实现都想对简单，但列举过程复杂，往往需要尽量优化算法，从而减少枚举的次数，提高枚举的效率。 优化思路： （1）结合约束条件，通过数学推导，减少枚举的范围和数量（能否减少循环的次数？） （2）通过预处理，以空间换时间，避免在枚举的过程中重复计算或判断 14 算法优化 在a和b都确定的情况下c有必要从0开始枚举吗？ c=y-a-b; 同时条件应该如何修改？ 请修改你的程序！ 15 算法优化-进一步优化 当a确定了，b有必要从0开始枚举吗？ b遍历到y-a即可，同时也保证了c>=0 请修改你的程序！ 16 算法优化-最终程序 17 课后练习——水仙花数 春天是鲜花的季节，水仙花就是其中最迷人的代表，数学上有个水仙花数，他是这样定义的：“水仙花数”是指一个三位数，它的各位数字的立方和等于其本身比如：153=1^3+5^3+3^3。 现在要求输出所有在m和n范围内的水仙花数。 18 水仙花数——枚举思路 19 思路1：枚举所有的三位数，然后拿出每个数的每一位判断 思路2：枚举百位、十位、个位上的数，然后组成一个三位数进行判断 总结 20 $$