资源简介

(共19张PPT)
微项目2
用枚举算法寻求问题多解
Phthon编程------枚举算法
学习目标
1.通过对枚举对象、范围、条件的构造，体验枚举算法解决问题的思想。
2.借助枚举算法解决问题的思想，寻找解决问题的多种答案组合。（培养计算思维）
把问题的所有可能解都一一列举出来，并按照问题要求的条件逐个判断每个答案是否是正确的解，这就是枚举算法。
在本项目中，我们将借助计算机的高速运算能力，采用枚举算法通过逐一尝试，最终得出求解结果。
枚举就是将问题所有可能的答案一一列举，然后根据条件判断各个答案是否合适，保留合适的，丢弃不合适的，做到既不遗漏也不重复。
要使用枚举算法，首先要确定枚举对象、枚举范围和判定条件。
(1)通过确定枚举范围列举该问题所有可能的解;
(2)应用判定条件，验证每一个方案是不是问题真正的解。
循环结构
选择结构
变量
枚举对象
判定条件
枚举范围
枚举算法
活动一：快速寻找有规律的数据
同学们有没有玩过一种叫作“拍7”的游戏
假设一起游戏的有33人，请记录经过3轮报数后拍手的数据。
游戏规则:把从1开始的自然数中含“7”的数称作“明7”;把不含“7”且是“7”的倍数的数称作“暗7”。从1开始轮流报数，轮到报“明7”或“暗7”的人，不能出声，只拍一下手。
1.做游戏
找规律
“拍7” 流程图
确定枚举的对象、范围和条件
枚举对象
判定条件
枚举范围
1~100的的自然数
循环结构
选择结构
变量
变量i
明7 （含有7）
暗7 （能被7整除）
当数据越来越大，就越难发现“明7和“暗7”，这时，不防使用枚举算法，借助Phthon程序快速找出想要的结果。
思考：
假如报数到100，
如何确定 枚举的对象 ？
枚举范围 ？
判定条件 ？
2.用程序寻找答案
#!/usr/bin/en python3
n=100
for i in range(1,n+1):
print(i)
枚举1~100的程序基本结构如下： 使用什么结构？
（1）确定枚举的对象、 范围和条件
#!/usr/bin/envpython3
n=100
for i in range(1,n+1):
if "7" in str(i): # 找出所有的 明"7",即含7的数
print("找到明7数字字:",i)
（2）.编写程序判断“明7”
#!/usr/bin/env python3
n=100
for i in range(1,n+1):
if "7" in str(i) or i%7==0 :
print("找到的拍手数 数: ",i)
“暗7”： 如何判断暗7？ 完善程序设计
（3）.增加 “暗7” 的判定条件
请尝试补全下面程序代码中缺少的枚举范围和判定条件，用枚举算法寻找遗忘的旅行箱密码。
for x in range(100, ): #三位密码的范围
if and
print(x)
3.用枚举算法找回忘记的密码
借助枚举算法可以尝试寻找遗忘的记忆。
某人将自己密码旅行箱的密码遗忘了。经过讨论，有的人认为密码是生日，有的人认为是电话号码……各种猜测激活了当事人的记忆，记起当时设置的密码是一个三位自然数，并且密码个位数是8，其他位含有1但是不能确定在哪一位置。
3.用枚举算法找回忘记的密码
提示信息:
① 通过取余运算%判断个位数。如x%10==8成立，则可判断个位数为8。
② 借助逻辑运算符“and”可以判断复杂情况。
③ 可使用整除运算取得该自然数的前两位数，利用in判断前两位中是否有1。
活动2:一一列举可行的解决方案
日常生活中，一些问题的解决往往具有多种方案组合，可以用枚举算法寻找答案。
现有足量的1克、2克、5克、10克砝码，共允许取用40枚砝码，现在有100克食盐，要求每种砝码至少使用1枚，共有多少种称量方案
1.分析问题，确定枚举范围
枚举对象可以确定为4种质量的砝码。每种砝码至少使用1枚，因此数量都不小于1，以下列出大概取值范围。
用a表示10克砝码的枚数，大概取值范围是1~10。
用b表示5克砝码的枚数，大概取值范围是1~20。
用c表示10克砝码的枚数，大概取值范围是1~40。
用d表示5克砝码的枚数，大概取值范围是1~40。
枚举的对象、范围
确定枚举的对象、范围和条件
枚举对象
判定条件
枚举范围
确定枚举的对象、范围和条件
枚举对象
判定条件
枚举范围
a:1~10
b:1~20
c:1~40
d:1~40
循环结构
选择结构
变量
变量 a, b,c,d
a+b+c+d=40
10×a+5×b+2×c+d=100
#!/usr/bin/env python3
j=0 #记录方案数量
for a in range(1,11): #10克砝码的范围
for b in range(1,21): #5克砝码的范围
for c in range(1,41): #2克砝码的范围
for d in range(1,41): #1克砝码的范围
if a+b+c+d==40 and 10*a+5*b+2*c+d==100:
print(a,b,c,d)
j+=1
print(j,"种方案")
水仙花数是各位数字的立方之和等于该数本身，如153=1 +5 +3 。请求出所有三位数的水仙花数。
请参考程序进行枚举实验，要特别注意体验通过取整除、取余的方式获取数位的技巧。
技术实验: 寻找水仙花数
#!/usr/bin/env python3
#寻找三位数中的水仙花数
for i in range(100,1000):
a =i // 100
b =i // 10% 10
c=i%10
if i == a ** 3 + b ** 3 + c ** 3:
print(i)
课堂小结
1、什么是枚举算法？枚举算法的3要素的构成
2、枚举算法和循环结构的关系？
3、枚举算法主要适合解决哪类问题？利用了计算机的哪种优势？

展开更多......

收起↑