教科版 高一信息技术 必修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。 由于