资源简介

(共25张PPT)
4.1 算法及其特征
学习目标
02计算思维
运用恰当的方式描述算法。
03数字化学习与创新
运用Python语言实现简单算法,解决问题。
01信息意识
熟悉将解决问题的方法归纳为一系列清晰、准确的步骤的过程。
解算法基本要素及重要特征。
同学们：
中国空间站在2022年建成。载人空间站为“天宫”；核心舱为“天和”；实验舱Ⅰ为“问天”；实验舱Ⅱ为“梦天”；货运飞船为“天舟”。同学们刚刚观看了航天员返回地球的整个过程，他们返回地球的方法和步骤有哪些呢？你是有没有想成为一名“航天员”的梦想呢？
那我们来一场“航天员”招募活动。
如果你想成为我们今天课堂上的“航天员”，你必须通过三个挑战才能入选，你准备好了吗？下面，让我们一起来依次挑战吧！
假设“天和”核心舱工作台上有三盏指示灯，分别对应3个系统。一旦灯亮起就说明该系统发生故障。如果情况紧急，只允许你进舱一次的情况下，如何判断哪盏指示灯对应哪一个系统呢
？
系统
系统
系统
＊设计算法是解决问题的核心，它的基本任务是对问题进行定性分析和定量分析。遵循算法的特征和约定，寻求计算的方法和规则，明确解决问题的途径。
挑战一:定性分析，判断“指示灯与控制系统的对应关系”。
灯只有亮、灭两种状态，但是灯又具有一种特殊性，即灯亮的同时会伴随发光发热，因此灯被触摸时还有冷、热两种状态。综上所述，一盏灯可能有4种不同的状态。
分析问题─指示灯的状态和特性
灯亮 灯灭 发热 不发热
怎么样保证每盏灯的状态都是唯一的 题目中并没有限制故障发生的次数，所以3个系统的灯状态是可以随意发生的。
挑战一:定性分析，判断“指示灯与控制系统的对应关系”。
根据自己的分析设计一个算法：
算法的描述—自然语言
第一步:1、2故障灯亮起。
第二步:过2分钟后强行关闭系统1。
第三步:靠近工作台，亮灯的与系统2连接。
第四步:摸一下另外两盏不亮的指示灯，发热的指示灯与系统1连接。
第五步:不亮又不热的指示灯与系统3连接。
？
系统
1
系统
2
系统
3
给指示灯和系统编号
1 2 3
挑战一:定性分析，判断“指示灯与控制系统的对应关系”。
开始
结束
为系统和指示灯编号
系统1,系统2故障，过2分钟后
靠近工作台
是
否
是
否
流程图
算法：解决问题的方法和步骤。
第一步:1、2故障灯亮起。
第二步:过2分钟后强行关闭系统1。
第三步:靠近工作台，亮灯的与系统2连接。
第四步:摸一下另外两盏不亮的指示灯，发热的指示灯与系统1连接。
第五步:不亮又不热的指示灯与系统3连接。
自然语言
强行关闭系统1
灯热？
指示灯亮？
该灯与系统2连接
该灯与系统1连接
该灯与系统3连接
挑战一:定性分析，判断“指示灯与控制系统的对应关系”。
假设“问天”实验舱中有4盒实验药品，每一盒里都用小布袋装着相同重量的实验药品。其中有1盒实验药品被污染，污染后每个小布袋中的实验药品增重1g，请你在只允许称重一次的情况下，判断出哪个盒药品被污染 （注意：此处称重是按照在地球引力环境下来计算的。）
提示：如果从每一盒中取出1袋分别称重，肯定可以判断那盒被污染，但不符合“只称重一次”的要求。你能改进你的判断方法吗？
1
2
3
4
挑战二:定量分析，寻找“被污染的实验药品”。
考虑1小布袋实验药品的重量变化，如果药品被污染，则增重 l 克，否则增重 0 克。
从某一盒中取出 n 袋药品，如果被污染，则增重 n 克，否则增重 0 克。
改进判断方法：
如果从不同的盒中取出不同袋数的药品，你能根据增重情况找出被污染的那一盒药品吗
1
2
3
4
挑战二:定量分析，寻找“被污染的实验药品”。
问题1:从第1个盒中取出1袋药品，从第2个盒中取出2袋药品，从第3个盒中取出3袋药品，从第4个盒中取出4袋药品，一共10袋药品。如果增重 克，则 号盒中药品被污染。
根据以上分析，请填写以下数据:
该算法需要输入的数据是: （ ）
该算法需要输出的数据是: （ ）
10袋
1袋
2袋
3袋
4袋
=
+
+
+
n
n
每一小袋药品的标准重量
一盒药品称的重量
1
2
3
4
挑战二:定量分析，寻找“被污染的实验药品”。
d=int(input('请输入每袋药品的标准重量:'))
w=int(input('请输入药品称得的重量:'))
【请填写此处】
print(‘被污染那盒的序号是:', x)
input("运行完毕,请按回车键退出...")
x = w-10*d
问题2:针对以上算法分析，补全python程序代码:
挑战二:定量分析，寻找“被污染的实验药品”。
＊有穷性：算法必须能在执行有限个步骤之后终止。
＊确切性：算法中的每一次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果。
＊输入项：一个算法有0个或多个输入，以刻画运算对象的初始悄况，所谓0个输入是指算法本身给出了初始条件。
＊输出项：算法一定要有输出。任何算法都不能“无功而返”。
＊可行性：算法中执行的任何计算都可以在有限时间内完成(也称为有效性)。算法中的运算都必须是可以实现的。
算法的重要特征
有穷性
确切性
输入项
输出项
+
+
+
可行性
+
依次输出100以内所有的正整数
依次输出所有的正整数
a=3
a=自然数
输入：a
输入：b
输出：a*b
a=3
b=4
输出：a*b
至少有一个输出
就算问题是无解，也要把无解的状态输出
a=3
b=4
c=a/b
a=3
b=0
c=a/b
√
√
√
√
√
×
×
×
×
×
算法的重要特征
1.有穷性 A☆算法中的运算都必须是可以实现的。
2.确切性 B☆输出被污染药盒的序号。
3.输入项 C☆算法有四个步骤
4.输出项 D☆输入每一袋药品的标准重量和称得的总重量。
5.可行性 E☆算法中的每一次运算都有明确的定义。
问题3:请将下面的名称与对应含义进行连线。
挑战二:定量分析，寻找“被污染的实验药品”。
假设“天舟”货运舱中的一台服务器中存有共10000条无重复的数据，如果你因为误操作删除了一个物品的ID号（8位整数）信息，幸运的是在备份数据库中保存了一份所有物品ID号的文件（无重复数据，没有顺序）。怎样快速找出被误删的ID号以便恢复数据？
挑战三:巧用运算，寻找“误删ID号”
备份ID号
故障ID号
方法一：
取出网络中心服务器ID列表中第一条数据；和备份服务器中的ID列表逐条进行对比，如果能够找到相同的ID号，则完成目标，否则取出网络中心服务器ID列表中下一条数据继续比对。按照该算法解决问题需要10000*10000，1亿次。
挑战三:巧用运算，寻找“误删ID号”
方法二：
（提示：可以利用异或运算）异或应用于逻辑运算，其运算法则为：0^0=0，1^0=1，0^1=1，1^1=0。由于两个相同数异或结果为0，而任何数异或0的结果等于数据本身。因此，可以把两文件中所有ID号直接进行异或，只出现一次的数据就能被找出，并且最后出现的异或结果就是这个数。
备份ID号
故障ID号
挑战三:巧用运算，寻找“误删ID号”
方法三：
将服务器的ID号全部加起来，然后减去备份服务器的ID号，得到的数就是被删除的ID号。
备份ID号
故障ID号
挑战三:巧用运算，寻找“误删ID号”
第一步:打开备份数据f1与故障数据f2。
第二步:读取备份数据list1，并数据求和target。
第三步:读取故障文件list2，并用备份数据和target减去故障数据和。
第四步:输出差值，即为误删ID号
自然语言描述算法
备份ID号
故障ID号
挑战三:巧用运算，寻找“误删ID号”
target = # 设置初始值
f1 = open('copy.txt','r') # 打开备份文件
list1 = f1.readlines() # 按行读取备份文件
for line in : # 依次处理列表list1中的数据
target = target+int(line) # 将读取的数据做加运算
f1. # 关闭备份文件
f2 = open('trouble.txt','r') # 打开故障文件
list2 = # 按行读取故障文件
for : # 依次处理列表list2中的数据
target = # 将读取的数据做减运算
# 关闭故障文件
print("被误删的ID号是：", ) # 输出被误删的ID号
list1
close
f2.close
f2.readlines()
line in list2
target-int(line)
target
0
程序源代码1：
挑战三:巧用运算，寻找“误删ID号”
sum1=0 #设置初始值
sum2=0 #设置初始值
f1=open(r"copy.txt") #打开备份文件
li=f1.readlines() #读取每行数据
for line in li:
sum1=sum1+int(line) #将读取的数据做和运算
f1.close() #关闭备份文件
f2=open(r"trouble.txt") #打开故障文件
li=f2.readlines() #读取每行数据
for line in li:
sum2=sum2+int(line) #将读取的数据做和运算
f2.close() #关闭故障文件
print("被删除的ID号是:",sum1-sum2) #输出被删除的ID号
input("运行完毕，请按回车键退出...")
程序源代码2：
挑战三:巧用运算，寻找“误删ID号”
1
2
3
在挑战一中，复习了算法的描述自然语言和流程图；更好的理解了算法的概念。
在挑战二中，我们学习了算法的重要特征:有穷性、确切性、输入项、输出项、可行性。
在挑战三中，通过分析问题、设计算法、补全python程序、调试运行四个过程更好了理解了计算机解决问题的过程。
学习回顾
1.算法的重要特征不包括（ ）
A.无穷性 B.确定性 C.数据输出 D.可行性
2.下列关于算法特征的的描述，错误的是（ ）
A.一个算法的每一个步骤必须有确切的含义
B.一个算法可以有多个输出，但是至少有一个输入
C.一个算法可以永无止境的进行下去
D.一个算法不一定必须可行，理论上想法对就可以执行
3.以下关于算法的描述正确的是（ ）
A.计算方法 B.计算公式 C.计算机程序 D.解决问题的步骤或指令
B
C
D
课堂练习
算法及其特征
算法的概念
算法的特征
算法描述方法
有穷性
确切性
可行性
输入项
输出项
算法必须能在有限个步骤之后终止
算法的每个步骤都具有确定的含义
一个算法通常要求有0个或多个输入
一个算法至少有一个输出
算法中的每一步都是可以执行的
自然语言
流程图
伪代码
用日常所用语言来描述算法的步骤
流程图是用图形表示算法的一种常用工具
用一种类似程序设计语言的代码来描述算法
算法就是解决问题的方法和步骤（确定的，有限的步骤）
课堂小结
课后作业
这次挑战的冠军在甲、乙、丙、丁四位同学中。
甲说:“不是我。”
乙说:“是丙。”
丙说:“是丁。”
丁说:“丙说的不对。”
已知四人中有一人说了假话，你能判断出到底谁是冠军吗
挑战四:找出“谁是冠军”

展开更多......

收起↑