资源简介

(共17张PPT)
3.3.2 枚举算法及其程序实现
凤鸣高中信息技术组
课堂回顾
解析算法解题的基本思路
1.建立正确的数学模型，即得出正确的数学代数式
2.将数学代数式转化为正确的python表达式
小试牛刀
学校举行趣味游戏，游戏规则如下：参与人员排成一个圈，从第一个人开始从50开始快速地报数，若遇到7的倍数或者包含7的数字，则说“跳过”，若没有跳过，则该人淘汰。一直报数，直到圈中只剩下一人，即为胜利者。你准备好了吗？
明枪易躲，暗箭难防啊！！！
刚才我们是如何找出所有需要跳过的数的？
思考
取第一个数50 判断是否需要跳过
取第二个数51 判断是否需要跳过
取第三个数52 判断是否需要跳过
…… ……
取最后一个数n 判断是否需要跳过
一一列举
逐个判断
枚举算法
枚举算法
基本思想：按照问题本身的性质，把问题所有可能的解一一列举，然后逐个判断每一个列举出来的可能解是否是问题真正的解，若是，采纳；否则，抛弃。
一一列举
逐个验证
循环结构
分支结构
解题思路：
逐一列举可能解的范围，这个过程用循环结构实现。
对每一个可能解进行验证，这个过程用分支结构实现。
枚举算法
解题步骤：
1.确定可能解的范围（不可重复，也不可遗漏；尽可能缩小范围）
2.确定判断条件（Python表达式）
基本框架：（循环结构嵌套分支结构）
for （列举所有可能解）：
if （判断条件）：
输出该解或计数
循环也可使用while语句实现
1.输出50-100之间是7的倍数或者包含数字7的数，并输出一共有几个数。
基础练习
解题步骤：
（1）确定可能解的范围：50-100
（2）确定判断条件：7的倍数或者包含数字7
如何用Python表达式进行判断
count=0
for i in :
if :
print(i,end=' ')
#填空3
print("一共找到"+str(count)+"个符合条件的数")
i%7==0 or i%10==7 or i//10==7
range(50,101)
count +=1
基础练习
2.有一个三位正整数，它有如下特点：
（1）偶数；（2）完全平方数；（3）比3的整数倍大1。
编程求解所有符合条件的数并输出结果。
解题步骤：
（1）确定可能解的范围：100-999
（2）确定判断条件：既是偶数又是完全平方数且比3的整数倍大1
尽可能缩小枚举范围
def my(x):
if :
f=True
else:
f=False
return f
for i in range(100,1000,2):
if :
print(i)
my(i) and i%3==1
x**0.5==int(x**0.5)
3.一个四位正整数，如果各个位上数字的四次方之和等于这个数本身，我们就称这个数为四叶玫瑰数。请编程找出所有的四叶玫瑰数。
解题步骤：
（1）确定可能解的范围：四位正整数：1000-9999
（2）确定判断条件：各个位上数字的四次方之和等于这个数本身
判断正解之前需要取出各个位上的数字
提取千位数字a：
提取百位数字b：
提取十位数字c：
提取个位数字d：
i//1000
i//10%10 或i%100//10
i%10
i//100%10 或i%1000//100
提高练习
count=0
for i in :
a=i//1000 #求四位数千位数字
b=i//100%10 #求四位数百位数字
c=i//10%10 #求四位数十位数字
d=i%10 #求四位数个位数字
if :
print(i)
count+=1
print("一个找到"+ +"个四叶玫瑰数")
range(1000,10000)
a**4+b**4+c**4+d**4==i
str(count)
4.一张纸上有个五位数密码，其中的百位数字和十位数字已经模糊不清，如图所示，已知这个数字是37或者67的倍数。请编程找到所有符合条件的密码。
提高练习
解题步骤：
（1）确定可能解的范围：百位和十位：00-99
可能解怎么表达？
（2）确定判断条件：是37或者67的倍数
#填空1
for i in range(0,100):
x = #填空2
if :
count=count+1
print(x)
print("一共找到"+str(count)+"个符合条件的密码！")
构造可能解
count=0
25006+10*i
x%37==0 or x%67==0
5.一张纸上有个五位数密码，其中的千位数字和十位数字已经模糊不清，如图所示，已知这个数字是27或者37的倍数。请编程找到所有符合条件的密码。
进阶练习
解题步骤：
（1）确定可能解的范围：无法整体枚举
逐个枚举：千位：0-9，十位：0-9
（2）确定判断条件：是27或者37的倍数
双重循环
count=0
for i in :
for j in :
#填空3
if m%37==0 or m%27==0:
count=count+1
print(m)
print("一共找到"+str(count)+"个符合条件的密码！")
m = 20500+1000*i+10*j
range(0,10)
range(0,10)
构造可能解
课堂总结
基本思想：按照问题本身的性质，把问题所有可能的解一一列举，然后逐个判断每一个列举出来的可能解是否是问题真正的解，若是，采纳；否则，抛弃。
解题步骤：
1.确定可能解的范围（不可重复，也不可遗漏；尽可能缩小范围）
2.确定判断条件（Python表达式）
基本框架：（循环结构嵌套分支结构）
for （列举所有可能解）：
if （判断条件）：
输出该解或计数
循环也可使用while语句实现

展开更多......

收起↑