4.1.2 枚举算法　　课件-2022—2023学年高中信息技术教科版（2019）必修1

第二单元 编程计算 2.4 可以复用的代码 例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、求生肖 1、确定枚举范围 zodiac=["鼠","牛","虎","兔","龙","蛇","马","羊","猴","鸡","狗","猪"] 编写程序，实现输入一个人的出生年份，程序计算并输出他对应的生肖。如输入2023，结果输出为“兔” 2、明确检验条件 index=(year-1900)%12 print( zodiac[index]) 一、枚举算法 例3、求生肖——拓展 1、确定枚举范围 zodiac=["鼠","牛","虎","兔","龙","蛇","马","羊","猴","鸡","狗","猪"] 编写程序，实现输入一个人的出生年份，程序计算并输出他对应的生肖，直到输入0结束。 2、明确检验条件 index=(year-1900)%12 print( zodiac[index]) 一、枚举算法 例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、确定枚举范围 1-1000 一个数如果恰好等于它的真因子（即除了自身以外的约数）之和，这个数就称为“完数”，例如6=1+2+3。编程输出1000以内的所有完数。 2、明确检验条件 一个数如果恰好等于它的真因子之和 a=0 for i in range(1,1001): for j in range(1,i): a=a+j if i%j==0: 1、设定变量，存放真因子之和 2、利用循环，计算真因子之和 3、判断真因子之和是否和该数相等 if a==i: 一、枚举算法 例5、鸡兔同笼问题 1、确定枚举范围 heads=35 Legs=94 兔数量：1-heads-1 编程解决：今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？ 2、明确检