算法及其特征-教案

4.1算法及其特征【学习目标】1.通过解决药丸问题，尝试运用恰当的方法描述算法。2.能够将部分简单算法转换为程序，并调试运行得出结果。【教学重点】能够分析问题，设计解决问题的算法，并用恰当的方法描述算法；了解枚举法的含义，并能使用枚举法解决相关问题。【教学难点】能够设计出解决问题的算法。【教学过程】第一课时一、引入师：叶达报名参加学校软件开发社团时。面试中有一道IQ题：有四个装了药丸的罐子，每个药丸都有一定的重量，其中有一个药罐被污染了。每片被污染的药丸比污染前增重1克。只允许称量一次，判断出哪个罐子的药被污染了。（同座位讨论该问题的解决步骤）生：用自然语言描述问题解决的步骤。第一步：第二步：师：在生活中很多类似的问题，在解决问题过程中都需要有一定方法。这种问题解决的方法实际就是算法。二、算法及其表示方法师：算法的定义在2.1节已经学过了，请大家再回顾一下，算法的表示方法有几种。生：自然语言、流程图、程序。师：来看下面这个问题的解决。学校历届校友的海量数据存储在校网络中心服务器中（共10000条，无重复数据），某管理员因为误操作删除了一位校友的ID号（8位整数）信息，恰好在备份数据库中保存了一份所有人员ID号的文件（无重复数据，无序）。怎样快速找出被误删的ID号以便恢复数据？例如：网络中心服务器ID列表备份服务器ID列表19750001197602301999000219990003……1999000319750001197602302001043219990002……请同座位讨论，用自然语言描述问题求解的算法。生：取出网络中心服务器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()#读取每行数据forlineinlist1:#依次处理列表list1中的数据target=target^int(line)#将读取的数据做异或运算f1.close#关闭备份文件f2=open(r"trouble.txt")#打开故障文件list2=f2.readlines()#按行读取故障文件forlineinlist2:#依次处理列表list2中的数据target=target^int(line)#将读取的数据做异或运算f2.close#关闭备份文件print("被删除的ID号是:",target)#输出被删除的ID号三、算法的特征师：思考解决“被删除的ID号”算法中的一些规律，思考算法应该具有哪些特征。填写下表。现象（可多选）算法的特征输入项：□0个输入□1个输入□多个输入输出项：□0个输出□1个输出□多个输出执行的结果：□确定的□不确定的□都可以执行的步骤：□有限□无限□都可