资源简介

枚举算法
课题
枚举算法
单元
算法与程序设计
学科
信息
年级
八年级
主备人
时间
教学目标
1、理解枚举算法的思想，掌握枚举算法的步骤。
2、初步掌握枚举算法的程序设计方法，提高分析问题、解决问题的能力。
重点
枚举算法解决问题的思想和步骤，循环嵌套语句的使用。
难点
枚举算法的程序实现。
教 学 过 程
二次备课
一、生活中的枚举实例
1、在一串相同的钥匙中找到所有能开启某扇门的钥匙？
一把一把地去试，找到后取出来。
2、课代表收作业时，将不同学科的作业混在一起了？
一本一本地检查归类。
3、忘记了三位数密码箱的密码了？
从000开始，001，002……找到正确密码后记下来。
二、初识枚举算法
232600517843500计算机由于运算速度快和存储容量大的特点，经常会采用最原始的解决方法——枚举算法（穷举法）。
枚举算法核心思想——列举，逐一检验。
例1：水仙花数——三位数，每个数位上的
数的44451873253次幂之和等于它本身。
5715196850例2：要求：在15到100中，找出所有是3倍数的自然数。
2113280215901、确定枚举对象：自然数 i
2、确定枚举范围：15到100之间
3、确定判断条件：为3的倍数
4、逐一枚举并验证：循环、判断
三、经典案例：百钱买百鸡
我国古代数学家张丘建在他的《算经》一书中提出了著名的“百钱买百鸡”问题：鸡翁一值钱五；鸡母一值钱三；鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？
（一）问题分析
-19051835151、确定枚举对象，范围和条件。
2、逐一枚举可能的解， 并根据条件验证每个解是否为问题的解。
21209003365500不重复、不遗漏、有次序、有规律
331470167005（二）算法设计
验证
177165178435条件
（三）编写代码
374655080
（四）调试运行
6350180975按F5键，观察运行结果。
（五）优化程序
76201924051、减少枚举范围
261239059690
76201993902、减少枚举对象
2660015172085
88901714503、减少枚举对象及范围
274955026035
使用枚举算法解决问题时，要尽量减少枚举对象和枚举范围，以提高算法效率。
四、随堂练习
1、将一张100元面额的纸币兑换成零钱（5元，10元，20元中任意多个面额），编写程序计算有多少种换法。
7620-444500
508055245
（拓展练习）2、完全数又称完美数，是一些特殊的自然数，其因数（不包含本身）的和恰好等于它本身。
第一个完全数是6，6=1+2+3。
第二个完全数是28，28=1+2+4+7+14
第三个完全数是496，496=1+2+4+8+16+31+62+124+248
要求：请找出10000以内的所有完全数。
确定枚举对象
10000以内的数
确定枚举范围
2~10000
确定判断条件
累加和等于
-16510161290
#初始空列表
lst=[]
for n in range(2,10001):
s=0 #因数累加器
for i in range(1,n-1):
if n%i==0:

64325524130 if s==n:
lst.append(n)
print("10000以内的完全数有：",lst)
（课后练习）3、一张单据上有一个5位数的编码，其百位数和千位数已经变得模糊不清。但是知道这个5位数是57或67的倍数。现要设计一个算法，输出所有满足条件的5位数，并统计这5位数的个数。
四、总结
1、枚举算法的概念，应用范围
2、枚举算法使用时注意枚举范围和对象的选择
五、布置作业
作业本第14课
课堂反思

展开更多......

收起↑