资源简介

(共16张PPT)
2021浙江教育出版社信息技术八（上）
第14课 枚举算法—百钱百鸡和寻找完全数
罗海燕
厦门市音乐学校
学习任务：理解枚举算法的思想，掌握枚举算法的步骤。
2
目标：通过“百钱买百鸡”问题的求解，初步掌握枚举算法的程序设计方法，提高分析问题、解决问题的能力。
重点：枚举算法解决问题的思想和步骤，循环嵌套语句的使用。
难点：枚举算法的实现。
厦门市音乐学校 罗海燕
1
枚举算法的思想：穷举法
2
枚举算法的步骤：流程图
3
枚举算法的实例：百钱百鸡
4
编写程序，调试运行
观察结果
CONTENT
厦门市音乐学校 罗海燕
4
枚举算法：
把问题所有可能的解一一列举，然后判断每一个列举出来的可能解是否为正确的解。
日常生活中很多问题可以用枚举算法解决：
如检测两篇文章的相似度、求解大面额纸币等值兑换成若干张小面额纸币的方案。
1
枚举算法的思想
厦门市音乐学校 罗海燕
2
枚举算法的步骤：流程图
确定枚举对象、范围和判定条件
逐一列举可能的解，并验证每个解是否为问题的解。
适合解的候选项是有限的、可列举的场合。判断正确解的过程可采用循环结构实现。
枚举算法一般比较直观、容易理解。
厦门市音乐学校 罗海燕
2
枚举算法的步骤：流程图
循环语句
分支结构
不能遗漏、不能重复。
（1）不能遗漏任何一个真正的解
（2）缩小搜索范围，提高效率。
厦门市音乐学校 罗海燕
3
枚举算法的实例：百钱百鸡
厦门市音乐学校 罗海燕
设公鸡有x只 母鸡有y只 小鸡有z只 若全部买公鸡，则最多可以买100/5只，因此设x的取值范围为0≤x≤20；
若全部买母鸡，则最多可以买100/3只，因此设x的取值范围为0≤y≤33；
若全部买小鸡，则最多可以买100*3只，因此设x的取值范围为0≤z≤100
我国古代数学家张丘建在《算经》一书中提出的数学问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？
3
枚举算法的实例：百钱百鸡
厦门市音乐学校 罗海燕
3
学生任务：半成品代码
厦门市音乐学校 罗海燕
count=0 # 循环计数
for x in range(21):
for y in range(<1>): #请补充完整代码
count=<2> #请补充完整代码
<3> #请补充完整代码
print("公鸡:",x,"母鸡:",y,"小鸡:",100-x-y)
print("循环运行次数:",count)
本题没有输入
本题出现了双重循环，即循环嵌套。同时体现了计算机解决问题的方法与数学方法的区别。
3
学生任务一：运行结果
厦门市音乐学校 罗海燕
count=0 # 循环计数
for x in range(21):
for y in range(34):
count=count+1
if 5*x+3*y+(100-x-y)/3==100:
print("公鸡:",x,"母鸡:",y,"小鸡:",100-x-y)
print("循环运行次数:",count)
厦门市音乐学校 罗海燕
随堂练习
将一张100元面额的纸币兑换成零钱(5元、10元、20元中的任意多个面额），编程序计算有多少种换法。
设5元有x张母10元有y张 20元有z张 若全部换成5元，则最多可以买100/5张，因此设x的取值范围为0≤x≤20；
若全部换成10元，则最多可以买100/10张，因此设x的取值范围为0≤y≤10；
若全部换成20，则最多可以买100/20只，因此设x的取值范围为0≤z≤5
学生任务二:零钱兑换
12
#将一张100元面额的纸币兑换成零钱(5元、10元、20元中的任意多个面额），编程序计算有多少种换法。
a=100
for x in range(21):
for y in range(11):
for z in range(6):
if a==5*x+10*y+z*20:
print("5元有",x,"张","10元有",y,"张","20元有",z,"张")
厦门市音乐学校 罗海燕
随堂练习
寻找完全数：程序填空
完全数又称为完美数，是一些特殊的自然数，其因数（不包含本身）的和恰好等于它本身。
第一个完全数是6,6=1+2+3。
第二个完全数是28，28=1+2+4+7+14
第三个完全数是496,496=1+2+4+8+16+31+62+124+248
……
在程序处填空，找出10000以内的所有完全数。
# 初始空列表
lst=[]
for n in range(2,10001):
s=0
for i in range(1,n-1):
if n%i==0:
<1>
if s==n:
lst.append(n)
print("2-10000中的完全数有:",lst)
厦门市音乐学校 罗海燕
随堂练习
寻找完全数答案
# 初始空列表
lst=[]
for n in range(2,10001):
s=0
for i in range(1,n-1):
if n%i==0:
s=s+i
if s==n:
lst.append(n)
print("2-10000中的完全数有:",lst)
板书
15
15
厦门市音乐学校 罗海燕
人生的算法亦是如此，只有一步一步，脚踏实地，总能到达成功的彼岸。
厦门市音乐学校 罗海燕

展开更多......

收起↑