资源简介

(共21张PPT)
4.1算法及其特征
回 顾 旧 知
大象进冰箱
第一步：打开冰箱门；
第二步：把大象装进去；
第三步：把冰箱门关上。
寻找“开关对应关系”
一个房间有3盏灯，房间外有3个开关分别控制这3盏灯，在只允许进房间一次的情况下，如何判断哪个开关控制哪盏灯？
活动1
亮
灭
冷
热
灯的
状态
寻找“开关对应关系”
算法
寻找“开关对应关系”
第一步：开1号、2号两个开关，2分 钟后关闭1号开关；
第二步：进房间，显然亮着的灯由2号开关控制；
第三步：摸一下另外两盏不亮的灯，发热的灯肯定由1号开关控制；
第四步：确定3号开关控制的灯。
流程图
寻找“开关对应关系”
第一步：开1号、2号两个开关，2分钟后关闭1号开关；
第二步：进房间，显然亮着的灯由2号开关控制；
第三步：摸一下另外两盏不亮的灯，发热的灯肯定由1号开关控制；
第四步：确定3号开关控制的灯。
关1号开关
灯亮
灯热
该灯由2号开关控制
该灯由1号开关控制
该灯由3号开关控制
定义
特征
描述方式
1.有穷性
2.确切性
3.输入项
4.输出项
5.可行性
1、自然语言
2、流程图
解决问题的方法和步骤
算法
算法的描述方式（自然语言）
01
02
第一步：打开冰箱
第二步：把大象放冰箱
第三步：关上冰箱门
大象进冰箱
第一步：确定要购买的物品
第二步：进行挑选、比较
第三步：到收银台结账付款
到超市购物
算法的描述方式（流程图）
流程线
处理框
判断框
连接符
起止框
输入输出框
算法的基本结构
流程图
顺序
循环
选择
分支
循环结构
分支/选择结构
顺序结构
02
04
01
03
05
算法必须能在执行有限个步骤之后终止
有穷性
算法一定要有输出。任何算法都不能“无功而返”
输出项
一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身给出了初始条件
输入项
算法中的每一次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果
确切性
算法中执行的任何计算都可以在有限时间内完成（也称为有效性），算法中的运算都必须是可以实现的
可行性
算法的重要特征
寻找“被污染的药丸”
有4个分别装了4种药丸的药瓶，里面每颗药丸都有单颗标准质量，其中有一个药瓶中的所有药丸都被污染了。每颗被污染的药丸比正常药丸增重1克。请在只允许称重一次的情况下，判断出哪个药瓶中的药丸被污染了？
活动2
如果从每个药瓶中取出1颗药丸分别进行称重，肯定可以判断出哪颗药丸被污染了，但是这种做法显然不符合“只能称量一次”的要求。
从第一个药瓶中取出1颗药丸，从第二个药瓶中取出2颗药丸，从第三个药瓶中取出3颗药丸，从第四个药瓶中取出4颗药丸，共10颗药丸。如果增重______克，则________号药瓶中的药丸被污染。
寻找“被污染的药丸”
考虑一颗药丸的重量变化，如果药丸被污染，则增重______克，否则增重________克。
从某一个药瓶中取出n颗药丸，如果被污染，则增重________克，否则增重
__________克。
寻找“误删的ID”
学校历届校友的数据存储在学校网络中心服务器中（共10000条，无重复数据），某管理员由于误操作删除了一位校友的ID号（8位整数）。恰好在备份文件中保存了所有人员的ID号（无重复数据，无序）。怎么快速找出被误删的ID号以便恢复数据？
活动3
ID号的特征
1
3
2
误删的ID号
备份文件中ID号总和与故障文
件中的ID号总和的差值为
两次
数据在两个文件中出现的次数
整数11111111—99999999
数据类型及大小范围:
寻找“误删的ID”
target = ________ #设置初始值
f1 = open(‘copy.txt’, ‘r’) #打开备份文件
list1 = f1.readlines() #按行读取备份文件
for line in list1 : #依次处理列表list1中的数据
target = target + int(line) #将读取的数据做加运算
f1.close() #关闭备份文件
f2 = open(‘trouble.txt’ , ‘r’) #打开故障文件
list2 = f2.readlines() #按行读取故障文件
for line in ______: #依次处理列表list2中的数据
target = ____________ #将读取的数据做减运算
____________ #关闭故障文件
print(“被误删的ID号是：” , ______) #输出被误删的ID号
0
list1
target – int(line)
f2.close()
Target
寻找“误删的ID”
求解“谁是冠军”
这次面试的冠军在A、B、C、D四位同学中。A说：“不是我。”B说：“是C。”C说：“是D。”D说：“C说的不对。”已知四人中有一人说了假话。你能判断出到底谁是冠军吗？说出你的结论和判断过程。
活动4
求解“谁是冠军”
结论：___________是冠军
则B和C说的也是假话
1、A说的是假话
则根据D所说的，推出C说的也是假话
2、B说的是假话
则C是冠军
3、C说的是假话
则B说的是假话
4、D说的是假话
C
枚举
我们常利用计算机运算速度快、精确度高的特点解决实际问题。在设计算法时，最简单的方法就是“直译”我们的思维过程。有一种算法就是把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法称“枚举”或“穷举”。
求解“谁是冠军”
01
02
03
解决问题的一般结构：
循环+判断
知道什么样的条件满足题意
确定枚举范围
求解“谁是冠军”
代码
分析
#设置选手列表
champion = [‘A’, ‘B’, ‘C’, ‘D’]
#循环读取选手编号
for i in champion :
#查找符合条件的选手
cond = (i != ‘A’) + (i == ‘C’)
+ (i ==‘D’) + (i != ‘D’)
if cond == 3 :
print(“冠军是：” ， i)
感谢观看！

展开更多......

收起↑