教科版 高一信息技术 必修1 第四单元 4.1 算法及其特征 教学设计
4.1 算法及其特征
【学习目标】
1.通过解决开关问题,能够分析出算法的基本特征,感受算法在解决问题中的重要性。
2.通过解决药丸问题,尝试运用恰当的方法描述算法。
3.能够将部分简单算法转换为程序,并调试运行得出结果。
4.通过解决冠军问题,了解枚举法的含义,并能使用枚举法解决相关问题。
【教学重点】
能够分析问题,设计解决问题的算法,并用恰当的方法描述算法;
了解枚举法的含义,并能使用枚举法解决相关问题。
【教学难点】
能够设计出解决问题的算法;能够用枚举法解决相关问题。
【教学过程】
第一课时
一、引入
师:叶达报名参加学校软件开发社团时。面试中有一道IQ题:有四个装了药丸的罐子,每个药丸都有一定的重量,其中有一个药罐被污染了。每片被污染的药丸比污染前增重1克。只允许称量一次,判断出哪个罐子的药被污染了。(同座位讨论该问题的解决步骤)
生:用自然语言描述问题解决的步骤。
第一步:
第二步:
师:在生活中很多类似的问题,在解决问题过程中都需要有一定方法。这种问题解决的方法实际就是算法。
二、算法及其表示方法
师:算法的定义在2.1节已经学过了,请大家再回顾一下,算法的表示方法有几种。
生:自然语言、流程图、程序。
师:来看下面这个问题的解决。
学校历届校友的海量数据存储在校网络中心服务器中(共10000条,无重复数据),某管理员因为误操作删除了一位校友的ID号(8位整数)信息,恰好在备份数据库中保存了一份所有人员ID号的文件(无重复数据,无序)。怎样快速找出被误删的ID号以便恢复数据?
例如:
网络中心服务器ID列表 | 备份服务器ID列表 |
19750001 19760230 19990002 19990003
…… | 19990003 19750001 19760230 20010432 19990002 …… |
请同座位讨论,用自然语言描述问题求解的算法。
生:取出网络中心服务器ID列表中第一条数据;和备份服务器中的ID列表逐条进行对比,如果能够找到相同的ID号,则完成目标,否则取出网络中心服务器ID列表中下一条数据继续比对。
师:最差情况下,按照该算法解决问题需要进行多少次比较?
生:10000*10000,1亿次。
师:还有没有其他方法?(提示:可以利用异或运算)
异或应用于逻辑运算,其运算法则为:0^0=0,1^0=1,0^1=1,1^1=0。
由于两个相同数异或结果为0,而任何数异或0的结果等于数据本身。因此,可以把两文件中所有ID号直接进行异或,只出现一次的数据就能被找出,并且最后出现的异或结果就是这个数。
(学生可能会提出将中心服务器的ID号全部加起来,然后减去备份服务器的ID号,得到的数就是被删除的ID号,可以让学生比较它和异或的方法)
请重新思考该问题解决的算法,并用流程图表示出来。(可以用^表示异或)
生:
图1
师:请思考下面的问题。
1.计算备份库ID号异或结果的循环结构和计算中心库ID号异或结果的循环结构能不能交换顺序?
2.如何存放两个数据库中ID号?
生:1.可以交换;2.列表、文件、数据库。
师:已知备份数据库文件存放在“copy.txt”中,中心服务器文件存放在“trouble.txt”中,用程序实现该问题的解决。
提示:文件的一般使用方法
f1=open(r"copy.txt") #打开文件
list1=f1.readlines() #读取每行数据,list1是一个记录了问题所有元素的列表
……
f1.close #关闭文件
生:
target=0 #设置初始值
f1=open(r"copy.txt") #打开备份文件
list1=f1.readlines() #读取每行数据
for line in list1: #依次处理列表list1中的数据
target= target^int(line) #将读取的数据做异或运算
f1.close #关闭备份文件
f2=open(r"trouble.txt") #打开故障文件
list2=f2.readlines() #按行读取故障文件
for line in list2: #依次处理列表list2中的数据
target= target^int(line) #将读取的数据做异或运算
f2.close #关闭备份文件
print("被删除的ID号是:", target) #输出被删除的ID号
三、算法的特征
师:思考解决“被删除的ID号”算法中的一些规律,思考算法应该具有哪些特征。填写下表。
现象(可多选) | 算法的特征 |
输入项: □0个输入 □1个输入 □多个输入 |
|
输出项: □0个输出 □1个输出 □多个输出 |
|
执行的结果:□确定的 □不确定的 □都可以 |
|
执行的步骤:□有限 □无限 □都可以 |
|
执行的时间:□有限 □无限 □都可以 |
|
生:注意对输出的理解。
四、总结
算法的特征:0或多个输入项;1或多个输出项;算法的确定性(确定的执行结果或者运算的确定性);算法的有穷性;算法的可行性。
第二课时
一、复习
师:回顾上一节课的内容,回答算法具有哪些特征?
生:输入项、输出项、确定性、有穷性、可行性等。
师:算法的常见表达方式有哪些?
生:自然语言、流程图、程序。
练习:任选一种方法表达一道IQ题的解决方法:“房间里有三盏灯,房间外有三个开关,