4.1 算法及其特征 教学设计（2课时）

教科版 高一信息技术 必修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中的数据 ... ...