3.3.2枚举算法 课件　2023—2024学年浙教版（2019）高中信息技术必修1

3.3.2 枚举算法 1 问题： 票据编号为5位，最后2位磨损了，请复原可能的数值，该票据编号正好满足规律票据数值为24的倍数 （1）如何解决 （2）范围？ 24300——24399 （3）条件？（合成新的5位数，是否票据数值=开头24的倍数） （4）用自然语言总结（将24300——24399范围里的数，一个一个试，如果票据数值是24的倍数，就输出） （5）术语讲解，数就是枚举对象、范围对应枚举范围、条件对应验证条件 for i in range( 24300,24400 ): #确定枚举范围 if i%24==0: #验证条件 print(‘可能的编号为：’, i) 问题： 票据编号为5位，百位和十位磨损了，请复原可能的数值，该票据编号正好满足规律票据数值为37的倍数 （1）如何解决?算法描述一下 （2）枚举对象 （3）枚举范围？ 37007——37997 且个位不变 （4）验证条件？是否票据数值=开头37的倍数 for i in range( 37007,37998,10 ): #确定枚举范围 if i%37==0: #验证条件 print(‘可能的编号为：’, i) for i in range( 24300,24400 ): #确定枚举范围 if i%24==0: #验证条件 print(‘可能的编号为：’, i) 小结： 枚举法解决问题的思路 小结： 枚举法解决问题的思路 （1）三要素：枚举对象、范围、验证条件 （2）算法特征：一一列举，逐个验证 （3）程序结构：循环语句嵌套分支结构。 通过循环一一列举该问题所有可能的解，在循环内逐一判断对象是否有问题真正的解，若是，则采用，否则不采用，然后下一轮。 拓展提升:优惠券发放。 家居广场酬宾活动发放优惠券，计划共发放y (假定为10000)元，优惠券包含的面值分别为[100, 500, 1000]，计划100元不多于1000 张，500 元不多于200张，1000 元不多于100张，且发放的不同金额票据张数要是10的整数倍，问可以有多少种发放方式? 枚举对象? 100的数量、500的数量、1000的数量 枚举范围? 0<=100 元的数量<=1000， 0<=500 元的数量<=100， 0<= 1000元的数量<= 100 验证条件? (总金额等于要发放的金额，金额票据单数要是10的整数倍 import time sum =int( input(‘优惠券总发放金额为：’) ) start=time.time( ) #记录开始时间 for i in range( 0,1001 ): #100元枚举范围 for j in range( 0,201 ): #500元枚举范围 for m in range( 0,101 ): #1000元枚举范围 num=i*100+j*500+m*1000 if num==sum and i%10==0 and j%10==0 and m%10==0: print(‘100元’,i,‘单’,‘500元’,j，’单’,1000元’,m，’单’) end=time.time() #记录结束时间 print(‘结束’，‘耗时’，end-start,’s’) for i in range( 0,1001,10 ): for j in range( 0,201,10 ): for m in range( 0,101,10): 优化： 方案1中仅设置最大枚举范围，可以根据条件进-步减小枚举范围，每个间隔为10。 for i in range( 0,1001,10 ): for j in range( 0,201,10 ): for m in range( 0,101,10): for i in range( 0,1001 ): for j in range( 0,201 ): for m in range( 0,101 ): 思考：还可以继续优化吗？减少枚举次数 for i in range( 0,1001,10 ): for j in r