资源简介

(共28张PPT)
.
4.1算法及其特征
2022
.
目标
GOAL
熟悉将解决问题的方法归结为一系列清晰、准确的步骤的过程
了解算法的基
本要素和重要
特征
运用适当方法
描述算法
运用Python
语言实现简单
算法，解决问
题
.
知识
回顾
02
03
01
算法
解决问题的方法与步骤
算法的描述方法
1、自然语言
2、流程图
3、代码
生活中的算法
1、食堂打饭：确定自己要吃的 排队购买 刷卡
2、超市购物：确定自己要买的 挑选 刷卡/刷脸
4
3
2
6
1
5
起止框
表示一个算法的开始与结束
输入/输出框
表示从外部输入数据到计算机内部或者从计算机内部输出数据到计算机.
处理框
表示操作的内容.
判断框
表示判断的条件。满足条件，执行标识为是的路径，反之，执行标识为否的路径.
流程线
指向算法运行的方向.
连接符
表示流程图的接续。在相互关系的流程图内，流程线将在具有相同字数或字母的另一连接符处继续下去.
流程图
三种
结构
1
2
3
4
有穷性：必须能在执行有限个步骤后终止
确切性：每一步运算都有明确定义
输入项：一个算法可以有0个或多个输入
可行性：执行的任何计算都可以在有限时间内完成
算法
特征
.
算法
特征
5
输出项：算法必须有输出，不能“无功而返”
01
活动一
寻找“开关对应关系”
.
一个房间有3盏灯，房间外有3个开关分别控制这3盏灯。在只允许进
房间一次的情况下，如何判断哪个开关控制哪盏灯？
.
活动一
1
2
3
4
灯只有亮，灭两种状态，
因灯的特殊性，开灯的同时会伴随发光发热。
因此灯被触摸时还有冷、热两种状态，
综上所述，一盏灯可能有4种不同状态
.
分析
问题
思考：怎样保证每盏灯的状态都是唯一的？
提示：题目中没有限制开关按动次数，所以3个开关的闭合状态可以随意改变
2
3
5
4
1
给灯和开关编号
同时打开1、2号开关
多分钟后关掉1号开关
进入房间
判断哪一盏灯发亮，亮着由2号开关控制
.
设计
算法
6
判断未发光的灯是否发热，如果发热了，这灯由1号开关控制，未发热的灯由3号开关控制
自然语言描述
设计
算法
流
程
图
描
述
设计
算法
流
程
图
描
述
流程图
自然语言
第一步：打开1、2两个开关
第二步：过2分钟关闭1号开关
第三步：进房间。亮着的是2号开关控制
第四步：摸一下不亮的灯发热的灯泡由1号开关控制
第五步：不亮不热的是3号控制
算法
描述
02
活动二
.
定量分析，寻找“被污染的药丸”
有四个装了药丸的瓶子，每颗药丸质量都相同，其中有一个药瓶中
所有药丸被污染了。每颗被污染的药丸比污染前增重1克。已知每
颗药丸的单颗标准质量，只允许称量一次，如何判断出哪个瓶
子的药被污染了？
.
活动二
3
2
1
从第1个药瓶取出1颗药丸，从第2个药瓶取出2颗药丸，
从第3个药瓶取出3颗药丸，
从第4个药瓶取出4颗药丸，
共10颗药丸。
某个药瓶取出n颗药丸，若被污染，增重 克
一颗药丸被污染则增重 克
分析
03
活动三
.
巧用运算，寻找“误删的ID号”
学校历届校友的海量数据存储在校网络中心服务器中（共10000条，无重复数据），某管理员因为误操作删除了一位校友的ID号（8位整数）信息，恰好在备份数据库中保存了一份所有人员ID号的文件（无重复数据，无序）。怎样快速找出被误删的ID号以便恢复数据
.
活动三
ID号的特征
数据类型及大小范围：
数据在两个文件中出现的次数：
备份文件ID号总和与故障文件的ID号总和的差值为：
.
活动三
整型int 8位数字
1次
被误删的ID号
算法描述—代码
target=0 #设置初始值
f1=open("copy.txt " , "r") #打开备份文件
list1=f1.readlines() #读取每行数据
for line in list1:
target=target+int(line) #将读取的数据做和运算
f1.close() #关闭备份文件
f2=open("trouble.txt " , "r") #打开故障文件
list2=f2.readlines() #读取每行数据
for line in list2:
target=target-int(line) #将读取的数据做和运算
f2.close() #关闭故障文件
print("被删除的ID号是:",target) #输出被删除的ID号
input("运行完毕，请按回车键退出...")
代码
04
活动四
.
求解“谁是冠军”
A
B
C
D
冠军不是我
是C
是D
C说的不对
.
活动四
已知四人中有一人说了假话，你能判断到底谁是冠军？
C
假设A说假话
B、C、D说的是真话，冠军是A，与B、C的话矛盾
假设B说假话
A、C、D说的是真话，冠军是D，与D的话矛盾
假设C说假话
A、B、D说的是真话，冠军是C
假设D说假话
A、B、C说的是真话， B 、C话矛盾
结果
C是冠军，C说了假话
.
分析
算法描述—代码
champion=['A','B','C','D’] #设置选手列表
for i in champion: #循环读取选手编号
cond=(i!='A') +(i=='C') + (i=='D')+(i!='D') #查找符合条件的选手
if cond==3: #说真话是否是3人
print("冠军是:",i) #输出冠军
input("运行完毕，请按回车键退出...")
代码
通常穷举算法都是用多重循环来实现的
一、确定穷举范围
问题所涉及的情况有哪些，情况的种数可不可以确定。
二、确定验证条件
分析出来的这些情况，需要满足什么条件，才成为问题的答案。
经常使用循环+判断的格式
利用计算机运算速度快、精确度高的特点，对要解决的问题的所有可能情况，一个不漏地进行检查，从中找出符合要求的答案
穷举算法
举例
两个关键
实现
密码暴力破解
如IBM为美军方设计的“飓风
破译机
查找罪犯指纹
超女“海选”
.
枚举
（穷举）
1） 有A、B两个人，从20个苹果中轮流拿苹果，每次只能拿1个或者2个，如果你是A，你可选择先拿或后拿，你应该采取什么样的策略才能保证自己获胜。（腾讯面试题）
.
拓展
练习
答：A要想获胜，就必须保证他在倒数第二次拿苹果之后还剩下3个，这样无论B拿1个还是2个，最后一个都是A拿到。A要保证最后剩3个，则A需要考虑自己第一次拿了苹果之后，剩下的苹果是3的倍数，这样A可以控制每次A和B拿的苹果之和为3，最后一定会剩下3个。该题中A只需刚开始拿2个，然后保证以后每次拿的个数与B拿的个数之和为3即可。
.
拓展
练习
2） A、B两个人从一堆玻璃球（共100个）中向外拿球，规则如下：① A先拿，然后一人一次交替进行；
② 每次只能拿1个、2个或者4个。
③ 谁拿最后一个球，谁就是最后的失败者。
请问，A、B两个人谁将是失败者？（阿里巴巴面试题）
答：B只要保证最后剩下的是1个或者4个，那么最后一个就一定是A拿。具体的策略是B要保证每次A和B拿玻璃球的个数之和为3个或者6个，这样B拿玻璃球之后剩下的玻璃球就是1个或者4个。
.
感谢观看

展开更多......

收起↑