微项目2 用枚举算法寻找问题多解　课件　2022—2023学年泰山版（2019）初中信息技术第2册

微项目2 用枚举算法寻找问题多解 例1 逢7跳过游戏： 第1位同学从1开始数起，依次每人尽快数下一个数，凡是遇到7的倍数（如7、21等）或是数字中带7的数字(如17、71等)，就要喊“过”说错或卡住了即被淘汰，这样一直数到100为止。 用枚举算法寻找问题多解 算法分析 把问题所有的可能解一一列举出来， 并对每一个可能解进行判断，是真正解的时候输出“过” 例1 逢7跳过游戏： 第1位同学从1开始数起，依次每人尽快数下一个数，凡是遇到7的倍数（如7、21等）或是数字中带7的数字(如17、71等)，就要喊“过”说错或卡住了即被淘汰，这样一直数到100为止。 用枚举算法寻找问题多解 用枚举算法寻找问题多解 这种算法就叫做“枚举算法”，又称为“穷举法” 算法思想：把问题的所有的可能解一一列举出来，并对每一个可能解进行判断，以确定是否是问题的真正解。 逢7跳过游戏 一一列举： 1~100 逐个检验： 是7的倍数或包含7 7的倍数 个位为7 十位为7 for i in range(1,101): i%7==0 i%10==7 i//10==7 用枚举算法寻找问题多解 用枚举算法寻找问题多解 利用枚举算法思想解决问题： 1、确定枚举范围 1~100 2、确定判断条件 是7的倍数或包含7 3、编程求解 用枚举算法寻找问题多解 例2、破解密码 1、确定枚举范围 812000~812990 求解密码，小明有一张藏宝图，上面有宝藏开启的密码，但是他不小心打翻了墨水，导致十位和百位模糊不清了，幸好藏宝图有提示：该密码是31或187的倍数，且十位是奇数。 2、确定判断条件 是31或187的倍数，且十位是奇数 for i in range(812000,812991,10): if i%31==0 i%187==0 i//10%2!=0: 用枚举算法寻找问题多解 例2、破解密码 1、确定枚举范围 812000~812990 求解密码，小明有一张藏宝图，上面有宝藏开启的密码，但是他不小心打翻了墨水，导致十位和百位模糊不清了，幸好藏宝图有提示：该密码是31或187的倍数，且十位是奇数。 2、确定判断条件 是31或187的倍数，且十位是奇数 for i in range(812000,812991,10): if i%31==0 i%187==0 i//10%2!=0: or ( ) and 用枚举算法寻找问题多解 例2、求解被墨水密码 结论：尽可能使罗列的范围最小，选择最优化的方法 100 991 用枚举算法寻找问题多解 例3、百钱买百鸡 用100元钱买100只鸡，公鸡，母鸡，小鸡都要有。公鸡5元1只，母鸡3元1只，小鸡1元3只。请问公鸡，母鸡，小鸡各应该买多少只？ 确定枚举对象 确定枚举范围 确定判断条件 公鸡（5元） 0≤x≤20 ① x+y+z=100 ② 5x+3y+⅓z=100 母鸡（3元） 0≤y≤33 小鸡（1/3元） 0≤z≤100 用枚举算法寻找问题多解 用枚举算法寻找问题多解 例4、水仙花数 1、确定枚举范围 100-1000 输出1000以内的所有水仙花数。水仙花数是指一个3位数，它的每个位上的数字的3次幂之和等于它本身。例如：1^3 + 5^3+ 3^3 = 153 2、确定判断条件 每个位上的数字的3次幂之和等于它本身： a=i%10 for i in range(100,1000): 个位 十位 百位 b=i//10%10 c=i//100 if a**3+b**3+c**3==i: 用枚举算法寻找问题多解 用枚举算法寻找问题多解 例5、鸡兔同笼问题 1、确定枚举范围 heads=35 Legs=94 兔数量：1-heads-1 编程解决：今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？ 2、确定判断条件 鸡和兔的总脚数之和等于94 leg=tu*4+(heads-tu)*2 for tu in range(1,heads): if legs==leg: 1、求当前兔子数量下鸡和兔的总脚数 2、判断脚数是否相等 用枚举算法寻找问题多解 小结 1. 枚举算法的基本思想：一一 列举，逐个检验 2. 尽可能使罗列的范围最小，选择最优化的方法 3. 可以借助列表实现枚举算法 用枚举算法寻找问题多解 随堂练习 把问题的所有可能解都—一列举出来，并按照问题要求的条件逐个判断每个答案是否是正确的解，这就是（） A.排序算法 B.递归算法 C.迭代算法 D.枚举算法 用枚举算法寻找问题多解 随堂练习 下列问题中，适合使用枚举法解决的是（） A.计算1+2+3+.….+1000的值 B.计算学校