(
课件网) 枚举算法及其优化 山东省济南第一中学 焦学仕 枚举法 (又称穷举法) 是指一一列举出所有与问题相关的情况，然后根据问题设定的条件，逐个加以检查判断，找到满足条件的解的方法。 枚举算法的概念 枚举算法的实现过程 二、在一定的范围内进行列举 一、对枚举的每一组数据进行检验 在不遗漏正确解的前提下，枚举范围尽可能的缩小以提高效率 如果结果唯一，数据一旦检验成功则结束枚举，输出答案、提前结束程序；如果结果不唯一，则一定要检验可能范围内的所有数据，并输出答案。 枚举算法及其优化 例题 百钱买百鸡 设1个公鸡值5钱，1个母鸡值3钱，3个小鸡值1钱。现用100钱来买100只鸡。 问：公鸡、母鸡、小鸡各买多少只？（公鸡、母鸡、小鸡每种最少一只） 【分析】 公鸡的数量x：最少1只，不超过 只 母鸡的数量y：最少1只，不超过 只 小鸡的数量z：最少1只，不超过 只 ①5 x + 3 y + z / 3 = 100 ②x + y + z = 100 满足条件： 20 33 100 程序实现 import time cishu=0 #初始循环次数为0 starttime = time.perf_counter() #枚举开始时读取系统当前时间 for x in range(1,20): for y in range(1,33): for z in range(1,100): cishu+=1 #每循环一次，次数加1 if x 5+y 3+z/3==100 and x+y+z==100: print(x,y,z) endtime = time.perf_counter() #枚举完成时读取系统当前时间 totaltime=endtime-starttime print('共循环%.f次'%cishu) print('总共耗时：%.6f秒'%totaltime) 用三重循环来枚举所有的情况 优化策略之一：剪枝法 缩小枚举范围来提高解决问题的效率。同时也要避免重复枚举。 优化分析 百钱买百鸡 设1个公鸡值5钱，1个母鸡值3钱，3个小鸡值1钱。现用100钱来买100只鸡。 问：公鸡、母鸡、小鸡各买多少只？（公鸡、母鸡、小鸡每种最少一只） 【分析】 公鸡的数量x：最少1只，不超过 只 母鸡的数量y：最少1只，不超过 只 小鸡的数量z： 只 100-x-y 20 33 （提示：小鸡的数量可不可以用x,y来表示？） import time cishu=0 #初始循环次数为0 starttime = time.perf_counter() #枚举开始前读取系统当前时间 for x in range(1,20): for y in range(1,33): z=100-x-y cishu+=1 #每循环一次，次数加1 if x 5+y 3+z/3==100: print(x,y,z) endtime = time.perf_counter() #枚举完成时读取系统当前时间 totaltime=endtime-starttime print('共循环%.f次'%cishu) print('总共耗时：%.6f秒'%totaltime) 优化后的程序 优化后由三重循环变成两重循环 import time cishu=0 starttime = time.perf_counter() for x in range(1,20): for y in range(1,33): z=100-x-y cishu+=1 if x 5+y 3+z/3==100: print(x,y,z) endtime = time.perf_counter() total=endtime-starttime print('共循环%.f次'%cishu) print('总共耗时：%.6f秒'%total) 优化前后程序对比 import time cishu=0 starttime = time.perf_counter() for x in range(1,20): for y in range(1,33): for z in range(1,100): cishu+=1 if x 5+y 3+z/3==100 and x+y+z==100: print(x,y,z) endtime = time.perf_counter() totaltime=endtime-starttime print('共循环%.f次'%cishu) print('总共耗时：%.6f秒'%totaltime) 循环由三重变为两重，判断条件少了x+y+z=100（思考:为什么可以去掉？） 借助数学知识继续优化： 第一步： 使用加减消元的方法消掉一元，比如z，然后用x来表示y和z 第二步： 令x=4k，则有 第三步： 根据题目中x,y,z的范围，列出不等式组： 第四步：求出， for k in range(1,4): x=4 k y=25-7 k z=3 k+75 print(x,y,z) 终极优化 终极优化之后，只有3次循环！ 至此，可以明确，只要求出k值，公鸡、母鸡 ... ...
