4.1 算法及其特征【学习目标】1.通过解决开关问题，能够分析出算法的基本特征，感受算法在解决问题中的重要性。2.通过解决药丸问题，尝试运用恰当的方法描述算法。3.能够将部分简单算法转换为程序，并调试运行得出结果。4.通过解决冠军问题，了解枚举法的含义，并能使用枚举法解决相关问题。【教学重点】能够分析问题，设计解决问题的算法，并用恰当的方法描述算法；了解枚举法的含义，并能使用枚举法解决相关问题。【教学难点】能够设计出解决问题的算法；能够用枚举法解决相关问题。【教学过程】第一课时一、引入师：叶达报名参加学校软件开发社团时。面试中有一道 IQ 题：有四个装了药丸的罐子，每个药丸都有一定的重量，其中有一个药罐被污染了。每片被污染的药丸比污染前增重 1 克。只允许称量一次，判断出哪个罐子的药被污染了。（同座位讨论该问题的解决步骤）生：用自然语言描述问题解决的步骤。第一步：第二步：师：在生活中很多类似的问题，在解决问题过程中都需要有一定方法。这种问题解决的方法实际就是算法。二、算法及其表示方法师：算法的定义在 2.1 节已经学过了，请大家再回顾一下，算法的表示方法有几种。生：自然语言、流程图、程序。师：来看下面这个问题的解决。学校历届校友的海量数据存储在校网络中心服务器中（共 10000 条，无重复数据），某管理员因为误操作删除了一位校友的 ID 号（8 位整数）信息，恰好在备份数据库中保存了一份所有人员 ID 号的文件（无重复数据，无序）。怎样快速找出被误删的 ID 号以便恢复数据？例如：网络中心服务器 ID 列表备份服务器 ID 列表197500011999000319760230197500011999000219760230199900032001043219990002请同座位讨论，用自然语言描述问题求解的算法。生：取出网络中心服务器 ID 列表中第一条数据；和备份服务器中的 ID 列表逐条进行对比,如果能够找到相同的 ID 号，则完成目标，否则取出网络中心服务器 ID 列表中下一条数据继续比对。师：最差情况下，按照该算法解决问题需要进行多少次比较？生：10000*10000，1 亿次。师：还有没有其他方法？（提示：可以利用异或运算）异或应用于逻辑运算，其运算法则为：0"0=0,「0=1,0"1=1,「1=0。由于两个相同数异或结果为 0，而任何数异或 0 的结果等于数据本身。因此，可以把两文件中所有 ID 号直接进行异或，只出现一次的数据就能被找出，并且最后出现的异或结果就是这个数。（学生可能会提出将中心服...
