5.4.2 查找算法的应用-教学设计 (2)

教学设计 课程基本信息 课题 查找算法的应用 教学目标 1. 学会对具体问题进行抽象建模，能根据问题的特点选择合适的数据结构并设计算法。 2. 理解并掌握查找算法的实现过程，体会查找算法在生活中的应用。 3. 学会使用查找算法解决现实生活、学习中遇到的问题。 4.通过计算机编程解决实际问题的过程实践，逐步形成问题建模能力和分析解决问题的能力。 教学内容 教学重点： 1. 对具体问题的抽象建模。 2. 根据数据特征选择数据结构。 3. 查找算法的设计实现。 教学难点： 1. 查找算法的设计实现。 教学过程 1、 新课导入 教师：在生活中，我们经常需要用查找搜寻某个对象，然后对其进行相应操作，例如在学生七选三选课信息表中根据学号查找某位同学的选择科目；如何实现快速查询呢？我们以“航空公司VIP会员积分查询”为例共同探讨。 不少航空公司都会提供优惠的会员服务，当某会员飞行里程累计达到一定数量后，可以使用里程积分兑换奖励机票或奖励升舱等服务。现给定某航空公司部分VIP会员的飞行里程、积分等信息，如表1所示，要求实现根据VIP号码快速查询会员积分的功能。 表 1 某航空公司的部分会员信息表 VIP号 姓名 飞行里程（km） 积分 600214 韩江辉 16801 519 601278 蒋志来 5321 78 600815 李亚东 28745 436 607854 王庆生 1861 39 605719 李燕 7493 138 603532 王晓燕 6875 102 600101 郑煜明 14253 236 600087 蔡佳宁 112703 958 表1信息存储在excel表格中，如何实现根据VIP号码快速查询会员的积分呢？请同学们思考。 【设计意图】通过引入生活中的数据分析实例，引导学生思考根据VIP号码查找并显示某个会员的积分的过程。 2、 新授知识 【学习任务一：】抽象与建模 问题：如表1中数据所示，每个会员的信息是一条记录，记录中包含VIP号码、姓名、飞行里程、积分数据项。根据刚刚的思考，快速根据VIP号码找到对应会员的积分，查找应如何进行呢？ 教师总结：要想显示某个会员的积分信息，需要找到此会员在表中的记录，例如要查找VIP号为600087的会员积分，需要找到如下所示的记录； 600087 蔡佳宁 112703 958 【设计意图】引导学生思考复杂数据查找的规律。 【学习任务二：】设计算法与数据结构 问题：在Python中如何实现根据VIP号码找到对应会员的记录呢？首先，我们需要考虑用何种数据结构存储会员信息，其次，我们要考虑用哪种算法实现查找功能。 数据结构：对于每个会员，需要保存其完整的一条记录信息，查找之前需要将所有会员的信息进行存储，这里可以选取数组结构来实现。此时可以用两种方案进行储存： 一：采用4个一维数组按列存储，即每个数组分别存储每个会员的VIP号、姓名、飞行里程(km)和积分，如定义a数组存储表中8位会员的VIP号，其对应值为 [600214,601278,600815,607854,605719,603532,600101,600087]; 二：采用1个一维数组按行存储，每个数组元素对应某位会员的记录信息，例如用a数组存储，a[i]表示某条记录，a[i][3]则表示此条记录的第3个数据项，即为此条记录的积分。 设计算法：要显示某个会员的积分，先要从多条会员信息的数据中找到该会员。查找可采用顺序查找算法或二分查找算法，要实现快速查询，哪种算法的效率更高？请同学们根据查找算法的比较(见表2)思考。 表 2 查找算法的比较 教师总结：根据表2内容，进行多次查找时二分查找的算法效率优于顺序查找，但二分查找需要被查序列必须是有序的，因此要按VIP号为关键字对会员记录进行排序。排序时要实现记录的两两交换，因此采用1个一维数组按行存储处理起来更方便快捷。 【设计意图】引导学生思考用何种数据结构存储数据方便后续处理，引导学生比较不同查找算法的效率及使用要求。 【学习任务三：】编写程序并上机调试 教师：确定用1维数组存储数据二分查找进行查找后，我们来看一下根据vip号码查找会员积分的流程图，这里会员的记录信息存储在”vip.csv”文件中，首先需要读取文件中数据保存到数组a中，然后按照vip号码对数组a中每个记录进行冒泡排序，接着输出排好序的会员记录信息，最后对输入查询的vip号码进行二分查找并输出查找结果。 教师将“vip.csv”文件和程序文件分发给学生，鼓励学有余力的同学独立实现冒泡排序和二分查找算法并实现上机调试。 教师：经过编程实践，不断地调试运行，同学们有没有更加理解查找算法解决问题的过程？教师讲解程序代码的执行