资源简介

(共16张PPT)
算法及其特征
——枚举算法
学 习 目 标
深入学习算法的重要特征
运用Python语言实现简单算法，解决问题
学会用枚举算法解决问题
01
02
03
PART 1
算法及其特征
一、旧知回顾
什么是算法？
怎样描述算法？
算法的基本特征有哪些？
二、问题导入
小王报名参加学校社团时。面试中有一道IQ题：有四个装了药丸的罐子，每个药丸都有一定的重量，其中有一个药罐被污染了。每片被污染的药丸比污染前增重1克。只允许称量一次，判断出哪个罐子的药被污染了。
分析问题
考虑1颗药丸的质量变化，如果药丸被污染，则增重 克，否则增重0 克。
从任一药瓶中提取n颗药丸，如果被污染，则增重 克，否则增重0 克。
从第一罐中取出1颗，第二罐中取出2颗，第三罐中取出3颗，从第四罐中取出4颗（共10颗）。如果增重________克，则________号药瓶被污染。
输入：？
计算：？
输出：？
几
几
思考：
三、算法及其特征
1
n
请设计程序并运行，使输入10颗药丸的总重量及单颗药丸标准质量就可以看到结果，找到被污染的药丸。
2.设计算法
分析 现象（可多选） 算法的特征
哪些信息属于输入： 输入项： □0个输入 □1个输入 □多个输入
哪些信息属于输出： 输出项： □0个输出 □1个输出 □多个输出
执行的结果： 执行的结果：□确定的 □不确定的 □都可以
需要 步得到结果。 执行的步骤：□有限 □无限 □都可以
题耗时 。 执行的时间：□有限 □无限 □都可以
单颗标准重量，称重后重量
多出的重量
找到被污染的瓶子
4
几秒
√
√
√
√
√
0个或多个输入
一定有输出
确切性
有穷性
可行性
称重后的质量-10颗标准质量
danke=int(input(‘请输入每颗药丸的标准重量：’))
zongde=int(input(‘请输入药丸称得的重量：’))
x=zongde-10*danke
print('被污染的药瓶序号是：',x)
3.编写程序
运行代码
PART 2
枚举算法
有一种算法是把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法称作“枚举”或“穷举”。
四、枚举算法
枚举算法基本思想：一 一列举、逐一检验
枚举法解决问题的一般结构：
枚举使用要点：确定枚举范围和验证条件
循环+判断
密码暴力破解
火柴棒摆数字
查找罪犯指纹
生活中的枚举：
查找1000以内所有能被3、5 、7整除的数：
例：
范围：
条件：
1--1000
整除3
整除5
整除7
for i in range(1,1001):
if (i%3==0)and (i%5==0)and (i%7==0):
print(i)
GO
循环
判断
这次面试的冠军就在小王和其他A、B、C、D四位同学中。消息很快传到了班上，当A、B、C、D四人回到班上，小王迫不及待地问他们中谁得了冠军。四人相对一笑：
A说：“不是我。”
B说：“是C。”
C说：“是D。”
D说：“C说的不对。”
原来他们想让小王猜出答案，而且有一人说了假话。小明很快就知道了答案，大家都想知道他的方法。你能判断到底谁是冠军吗？
三、枚举算法
解析：利用枚举法，逐一假设A、B、C、D是冠军，判断是否正确。
冠军 A说：“不是我。” B说：“是C。” C说：“是D。” D说：“C说的不对。”
A
B
C
D
分子问题+设计算法
×
×
×
×
×
×
×
×
√
√
√
√
√
√
√
√
用程序求谁是冠军时，我们需要把每个人说的话转化成计算机能够执行的表达式。如A说：“不是我。”可以表示为“i!='A'”，其中i为枚举的冠军选手编号。
冠军 i!=‘A’ i==‘C’ i==‘D' i!='D’
A × × × √
B √ × × √
C √ √ × √
D √ × √ ×
实现方法：布尔值数值化
i!=‘A’的运算结果是一个逻辑值，在数值计算中会自动转换成1（True）或0（Flase）
分析以下代码的含义，理解解题思路。
xuanshou=['A','B','C','D'] #设置选手列表
for i in xuanshou: #循环读取选手编号
tiaojian=(i!=‘A’)+(i==‘C’) + (i==‘D')+(i!='D‘) #查找符合条件的选手
if tiaojian==3: #说真话是否是3人
print("冠军是:",i)
GO
范围：
条件：
A、B、C、D
说真话的人数是否为3人
编写程序
课堂小结
枚举算法基本思想：一 一列举、逐一检验
枚举法解决问题的一般结构：循环+判断。
枚举使用要点：确定枚举范围和验证条件

展开更多......

收起↑