4.1 算法及其特征【新教材】2021-2022学年教科版（2019）高中信息技术必修一 课件（23张PPT）
文档属性
| 名称 | 4.1 算法及其特征【新教材】2021-2022学年教科版（2019）高中信息技术必修一 课件（23张PPT） |  | |
| 格式 | pptx | ||
| 文件大小 | 9.8MB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 教科版（2019） | ||
| 科目 | 信息技术（信息科技） | ||
| 更新时间 | 2021-12-26 19:12:31 | ||
图片预览
文档简介
(共23张PPT)
第2单元 编程计算
第1单元 初识数据与计算
第3单元 认识数据
第4单元 计算与问题解决
第5单元 数据分析与人工智能
信息技术
（必修1）
4.1 算法及其特征
学习目标
★ 熟悉将解决问题的方法归结为一系列清晰、 准确的步骤的过程。
★ 了解算法的基本要素和重要特征。
★ 运用恰当的方式描述算法。
★ 运用Python语言实现简单算法，解决问题。
软件设计师是业务领域和技术领域的专家。面对客户需求，软件设计师要对问题进行整体分析以找到解决方案，通过洽当的方式与客户沟通；面对技术问题，软件设计师需要借助计算机编程解决实际问题。我们将通过“软件开发社招新”项目讨论计算机编程解决问题的过程。
※ 活动1 寻找“开关对应关系”
软件开发社团要招募新成员，报名的同学要经过面试才能加入。第一关面试题是：“一个房间有3盏灯，房间外有3个开关分别控制这3盏灯在只允许进房间一次的情况下， 如何判断哪个开关控制哪盏灯？”
设计算法是解决问题的核心，它的基本任务是对问题进行定性分析和定量分析，遵循算法的特征和约定，寻求计算的方法和规则，明确解决问题的途径。
任务一 探讨面试题的解决方案
分析问题—灯的状态和特性
灯只有亮、灭两种状态，但是灯又具有一种特殊性，即开灯的同时会伴随发光发热，因此灯被触摸时还有冷、热两种状态。综上所述，一盏灯可能有4种不同的状态。
灯亮
灯灭
发热
不发热
怎么样保证每盏灯的状态都是唯一的？题目中并没有限制开关按动次数，所以3个开关的闭合状态是可以随意改变的。
想一想，划一划
第一步：打开1、2两个开关
第二步：过2分钟后关闭1号开关
第三步：进房间，亮着的灯是由2号开关控制
第四步：摸一下另外两盏不亮的灯，发热的灯泡是由1号开关控制
第五步：不亮又不热的灯是由3号开关控制
自然语言
流程图
关1号开关
灯亮？
灯热？
该灯由2号开关控制
该灯由1号开关控制
该灯由3号开关控制
解决问题的方法及步骤
算法
设计算法
计算a,b两数和与差
第一步：输入两个数a,b
第二步：计算两数和s1=a+b
第三步：计算两数差s2=a-b
第四步：输出s1,s2
输入两个数a,b
计算s1=a+b,s2=a-b
Print s1,s2
输入a,b
S1=a+b
S2=a-b
输出s1,s2
输入a,b
S1=a+b,s2=a-b
输出s1,s2
算法的描述
自然语言
流程图
伪代码
N-S框图
PAD图
程序代码
算法的特征
有穷性
确切性
输出项
可行性
输入项
算法必须能在执行有限个步骤之后终止。
算法中的每一次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果。
算法一定要有输出。任何算法都不能 “无功而返＂ 。
输入项。一个算法有0个或多个输入，以刻画运算对象的初始悄况，所谓0个输入是指算法本身给出了初始条件。
算法中执行的任何计算都可以在有限时间内完成（也称为有效性）。
有4个分别装了4种药丸的药瓶，里面每颗药丸都有单颗标准质量，其中有一个药瓶中的所有药丸都被污染了。 每颗被污染的药丸比正常药丸增重1克。请在只允许称量一次的情况下，判断出哪个药瓶中的药丸被污染了。
活动2 定量分析， 寻找”被污染的药丸”
如果从每个药瓶中取出1颗药丸分别进行称重，肯定可以判断出哪颗药丸被污染了，但是这种做法显然不符合 ”只能称量一次＂ 的要求。 你能改进判断方法吗？
考虑1颗药丸的重量变化，如果药丸被污染，则增重_____克，否则增重________克。
改进算法
从某一个药瓶中取出n颗药丸，如果被污染，则增重_____克，否则增重________克。
如果我们从不同的药瓶中取出不同颗数的药丸，你能根据增重情 况找出被污染的药丸吗？
第1个药瓶取1颗，第2个药瓶取2颗，第3个药瓶取3颗，笫4个药瓶取4颗，共10颗药丸。
如果增重______克，则_______号药瓶中的药丸被污染。
分析 现象（可多选） 算法的特征
哪些信息属于输入： 输入项： □0个输入 □1个输入 □多个输入
哪些信息属于输出： 输出项： □0个输出 □1个输出 □多个输出
执行的结果： 执行的结果：□确定的 □不确定的 □都可以
需要 步得到结果。 执行的步骤：□有限 □无限 □都可以
题耗时 。 执行的时间：□有限 □无限 □都可以
标准重量，称重后重量
多出的重量
找到被污染的瓶子
4
几秒
√
√
√
√
√
0个或多个输入
一定有输出
确切性
有穷性
可行性
设计算法
回顾算法的特点，思考一下，在这个问题中，哪些信息属于输入、哪些信息属于输出呢？
请设计程序并运行，使输入10颗药丸的总重量及4种药丸的单颗准质量就可以看到结果，找到被污染的药丸。
d=int(input('请输入每颗药丸的标准重量：'))
w=int(input('请输入药丸称得的重量：'))
x=w-10*d
print('被污染的药瓶序号是：',x)
input("运行完毕，请按回车键退出...")
活动3 巧用运算， 寻找＂误删的ID号”
学校历届校友的数据存储在学校网络中心服务器中（共10000条，无重复数据），某管理员由于误操作删除了一位校友的ID号(8位整数）。恰好在备份文件中保存了所有人员的ID号（无重复数据，无序）。怎样快速找出被误删的ID号以便恢复数据？
ID号的特征
1.ID数据类型：____________
2.数据在两个文件中出现的次数：________
3.备份文件中1D号总和与故障文件中的ID号总和的差值为：__________
整型（int）
2次
被删除的ID
自然语言描述算法
第一步：打开备份数据f1与故障数据f2
第二步：读取备份数据list1，并数据求和target
第三步：读取故障文件list2，并用备份数据和target减去故障数据和
第四步：输出差值，即为误删ID号
备份ID号
故障ID号
设计算法——找出被删除的ID
通过分析，我们发现计算备份文件ID号总和与故障文件ID号总和的差值就是误删的ID号。
target=________
f1=open('copy.txt', 'r’)
listl=fl.readlines()
for line in _____ :
target= target+int(line)
fl.____________
f2=open('trouble.txt', 'r’)
list2= _________
for ___________ :
target= __________
_________________
print(被误删的ID号是：，_______)
#设置初始值
＃打开备份文件
＃按行读取备份文件
＃依次处理列表listl中的数据
＃将读取的数据做加运算
＃关闭备份文件
＃打开故障文件
＃按行读取故障文件
＃依次处理列表list2中的数据
＃将读取的数据做减运算
＃关闭故障文件
#输出被误删的ID号
0
list1
Close()
f2.readlines()
line in list2
target – int(line)
F2.close()
target
代码解析
f1=open(‘copy.txt’, ‘r’) #open()函数打开外部存储器中的文件，并赋值给内存中的f1变量；
listl=fl.readlines() #按行读取txt文件中的数据，并赋值到list1列表中；
f1.close() #close()函数关闭正在打开的文件
这次面试的冠军在A 、 B 、 C 、 D四位同学中。 A说：“不是我。” B说：“是C”。“C说： “是D。”D说：“C说的不对。”已知四人中有一人说了假话。 你能判断出到底谁是冠军吗？说出你的结论和判断过程。
※ 活动 尝试枚举
不是我
是C
是D
C说的不对
A
B
C
D
任务二 求解“谁是冠军”
枚举
有一种算法是把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法称作“枚举”或“穷举”。
枚举法解决问题的一般结构：循环+判断。
优势：易证明正确性
在不知道谁说真话、谁说假话的情况下，最简单的方法就是把所有可能都枚举出来。因为只有一位冠军，所以可以枚举选手的编号，并对A、B、C、D四个人的话进行判断。
解析：利用枚举法，逐一假设A、B、C、D是冠军，判断是否正确。
冠 军 A说：“不是我。” B说：“是C。” C说：“是D。” D说：“C说的不对。”
A × × × √
B √ × × √
C √ √ × √
D √ × √ ×
用程序求谁是冠军时，我们需要把每个人说的话转化成计算机能够执行的表达式。如A说：“不是我。”可以表示为“i!='A'”，其中i为枚举的冠军选手编号。
champion= ['A','B','C','D'] ＃设置选手列表
for i in champion: # 遍历champion列表
cond=(i! ='A')+(i=='C')+(i=='D')+(i! ='D')
if cond==3:
print(“冠军是”,i)
设计算法
答案 冠军是: C
在《孙子算经》中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”。（即一个数除以3余2，除以5余3，除以7余2，求这个数。）
参考答案：
i=0
while (i%3!=2 or i%5!=3 or i%7!=2):
i=i+1
print(i)
巩固提升
课堂小结
算法：解决问题的方法和步骤；
算法的描述：
算法的特征：
有穷性：算法步骤有限；
确切行：每一次运算的含义明确；
输入项：一个算法有0个或多个输入；
输出项：算法一定要有输出；
可行性：在有限时间内完成；
计算机解决问题的一般过程：
自然语言
流程图
伪代码
N-S框图
PAD图
程序代码
具体问题
分析问题
问题解决
设计算法
编写程序
调试运行
第2单元 编程计算
第1单元 初识数据与计算
第3单元 认识数据
第4单元 计算与问题解决
第5单元 数据分析与人工智能
信息技术
（必修1）
4.1 算法及其特征
学习目标
★ 熟悉将解决问题的方法归结为一系列清晰、 准确的步骤的过程。
★ 了解算法的基本要素和重要特征。
★ 运用恰当的方式描述算法。
★ 运用Python语言实现简单算法，解决问题。
软件设计师是业务领域和技术领域的专家。面对客户需求，软件设计师要对问题进行整体分析以找到解决方案，通过洽当的方式与客户沟通；面对技术问题，软件设计师需要借助计算机编程解决实际问题。我们将通过“软件开发社招新”项目讨论计算机编程解决问题的过程。
※ 活动1 寻找“开关对应关系”
软件开发社团要招募新成员，报名的同学要经过面试才能加入。第一关面试题是：“一个房间有3盏灯，房间外有3个开关分别控制这3盏灯在只允许进房间一次的情况下， 如何判断哪个开关控制哪盏灯？”
设计算法是解决问题的核心，它的基本任务是对问题进行定性分析和定量分析，遵循算法的特征和约定，寻求计算的方法和规则，明确解决问题的途径。
任务一 探讨面试题的解决方案
分析问题—灯的状态和特性
灯只有亮、灭两种状态，但是灯又具有一种特殊性，即开灯的同时会伴随发光发热，因此灯被触摸时还有冷、热两种状态。综上所述，一盏灯可能有4种不同的状态。
灯亮
灯灭
发热
不发热
怎么样保证每盏灯的状态都是唯一的？题目中并没有限制开关按动次数，所以3个开关的闭合状态是可以随意改变的。
想一想，划一划
第一步：打开1、2两个开关
第二步：过2分钟后关闭1号开关
第三步：进房间，亮着的灯是由2号开关控制
第四步：摸一下另外两盏不亮的灯，发热的灯泡是由1号开关控制
第五步：不亮又不热的灯是由3号开关控制
自然语言
流程图
关1号开关
灯亮？
灯热？
该灯由2号开关控制
该灯由1号开关控制
该灯由3号开关控制
解决问题的方法及步骤
算法
设计算法
计算a,b两数和与差
第一步：输入两个数a,b
第二步：计算两数和s1=a+b
第三步：计算两数差s2=a-b
第四步：输出s1,s2
输入两个数a,b
计算s1=a+b,s2=a-b
Print s1,s2
输入a,b
S1=a+b
S2=a-b
输出s1,s2
输入a,b
S1=a+b,s2=a-b
输出s1,s2
算法的描述
自然语言
流程图
伪代码
N-S框图
PAD图
程序代码
算法的特征
有穷性
确切性
输出项
可行性
输入项
算法必须能在执行有限个步骤之后终止。
算法中的每一次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果。
算法一定要有输出。任何算法都不能 “无功而返＂ 。
输入项。一个算法有0个或多个输入，以刻画运算对象的初始悄况，所谓0个输入是指算法本身给出了初始条件。
算法中执行的任何计算都可以在有限时间内完成（也称为有效性）。
有4个分别装了4种药丸的药瓶，里面每颗药丸都有单颗标准质量，其中有一个药瓶中的所有药丸都被污染了。 每颗被污染的药丸比正常药丸增重1克。请在只允许称量一次的情况下，判断出哪个药瓶中的药丸被污染了。
活动2 定量分析， 寻找”被污染的药丸”
如果从每个药瓶中取出1颗药丸分别进行称重，肯定可以判断出哪颗药丸被污染了，但是这种做法显然不符合 ”只能称量一次＂ 的要求。 你能改进判断方法吗？
考虑1颗药丸的重量变化，如果药丸被污染，则增重_____克，否则增重________克。
改进算法
从某一个药瓶中取出n颗药丸，如果被污染，则增重_____克，否则增重________克。
如果我们从不同的药瓶中取出不同颗数的药丸，你能根据增重情 况找出被污染的药丸吗？
第1个药瓶取1颗，第2个药瓶取2颗，第3个药瓶取3颗，笫4个药瓶取4颗，共10颗药丸。
如果增重______克，则_______号药瓶中的药丸被污染。
分析 现象（可多选） 算法的特征
哪些信息属于输入： 输入项： □0个输入 □1个输入 □多个输入
哪些信息属于输出： 输出项： □0个输出 □1个输出 □多个输出
执行的结果： 执行的结果：□确定的 □不确定的 □都可以
需要 步得到结果。 执行的步骤：□有限 □无限 □都可以
题耗时 。 执行的时间：□有限 □无限 □都可以
标准重量，称重后重量
多出的重量
找到被污染的瓶子
4
几秒
√
√
√
√
√
0个或多个输入
一定有输出
确切性
有穷性
可行性
设计算法
回顾算法的特点，思考一下，在这个问题中，哪些信息属于输入、哪些信息属于输出呢？
请设计程序并运行，使输入10颗药丸的总重量及4种药丸的单颗准质量就可以看到结果，找到被污染的药丸。
d=int(input('请输入每颗药丸的标准重量：'))
w=int(input('请输入药丸称得的重量：'))
x=w-10*d
print('被污染的药瓶序号是：',x)
input("运行完毕，请按回车键退出...")
活动3 巧用运算， 寻找＂误删的ID号”
学校历届校友的数据存储在学校网络中心服务器中（共10000条，无重复数据），某管理员由于误操作删除了一位校友的ID号(8位整数）。恰好在备份文件中保存了所有人员的ID号（无重复数据，无序）。怎样快速找出被误删的ID号以便恢复数据？
ID号的特征
1.ID数据类型：____________
2.数据在两个文件中出现的次数：________
3.备份文件中1D号总和与故障文件中的ID号总和的差值为：__________
整型（int）
2次
被删除的ID
自然语言描述算法
第一步：打开备份数据f1与故障数据f2
第二步：读取备份数据list1，并数据求和target
第三步：读取故障文件list2，并用备份数据和target减去故障数据和
第四步：输出差值，即为误删ID号
备份ID号
故障ID号
设计算法——找出被删除的ID
通过分析，我们发现计算备份文件ID号总和与故障文件ID号总和的差值就是误删的ID号。
target=________
f1=open('copy.txt', 'r’)
listl=fl.readlines()
for line in _____ :
target= target+int(line)
fl.____________
f2=open('trouble.txt', 'r’)
list2= _________
for ___________ :
target= __________
_________________
print(被误删的ID号是：，_______)
#设置初始值
＃打开备份文件
＃按行读取备份文件
＃依次处理列表listl中的数据
＃将读取的数据做加运算
＃关闭备份文件
＃打开故障文件
＃按行读取故障文件
＃依次处理列表list2中的数据
＃将读取的数据做减运算
＃关闭故障文件
#输出被误删的ID号
0
list1
Close()
f2.readlines()
line in list2
target – int(line)
F2.close()
target
代码解析
f1=open(‘copy.txt’, ‘r’) #open()函数打开外部存储器中的文件，并赋值给内存中的f1变量；
listl=fl.readlines() #按行读取txt文件中的数据，并赋值到list1列表中；
f1.close() #close()函数关闭正在打开的文件
这次面试的冠军在A 、 B 、 C 、 D四位同学中。 A说：“不是我。” B说：“是C”。“C说： “是D。”D说：“C说的不对。”已知四人中有一人说了假话。 你能判断出到底谁是冠军吗？说出你的结论和判断过程。
※ 活动 尝试枚举
不是我
是C
是D
C说的不对
A
B
C
D
任务二 求解“谁是冠军”
枚举
有一种算法是把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法称作“枚举”或“穷举”。
枚举法解决问题的一般结构：循环+判断。
优势：易证明正确性
在不知道谁说真话、谁说假话的情况下，最简单的方法就是把所有可能都枚举出来。因为只有一位冠军，所以可以枚举选手的编号，并对A、B、C、D四个人的话进行判断。
解析：利用枚举法，逐一假设A、B、C、D是冠军，判断是否正确。
冠 军 A说：“不是我。” B说：“是C。” C说：“是D。” D说：“C说的不对。”
A × × × √
B √ × × √
C √ √ × √
D √ × √ ×
用程序求谁是冠军时，我们需要把每个人说的话转化成计算机能够执行的表达式。如A说：“不是我。”可以表示为“i!='A'”，其中i为枚举的冠军选手编号。
champion= ['A','B','C','D'] ＃设置选手列表
for i in champion: # 遍历champion列表
cond=(i! ='A')+(i=='C')+(i=='D')+(i! ='D')
if cond==3:
print(“冠军是”,i)
设计算法
答案 冠军是: C
在《孙子算经》中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”。（即一个数除以3余2，除以5余3，除以7余2，求这个数。）
参考答案：
i=0
while (i%3!=2 or i%5!=3 or i%7!=2):
i=i+1
print(i)
巩固提升
课堂小结
算法：解决问题的方法和步骤；
算法的描述：
算法的特征：
有穷性：算法步骤有限；
确切行：每一次运算的含义明确；
输入项：一个算法有0个或多个输入；
输出项：算法一定要有输出；
可行性：在有限时间内完成；
计算机解决问题的一般过程：
自然语言
流程图
伪代码
N-S框图
PAD图
程序代码
具体问题
分析问题
问题解决
设计算法
编写程序
调试运行