5.4.2 查找算法的应用-教学设计（表格式）

教学设计 课程基本信息 课题 查找算法的应用 教学目标 1. 学会对具体问题进行抽象建模，能根据问题的特点选择合适的数据结构并设计算法。 2. 理解并掌握查找算法的实现过程，体会查找算法在生活中的应用。 3. 学会使用查找算法解决现实生活、学习中遇到的问题。 4.通过计算机编程解决实际问题的过程实践，逐步形成问题建模能力和分析解决问题的能力。 教学内容 教学重点： 对具体问题的抽象建模。 根据数据特征选择数据结构。 查找算法的设计实现。 教学难点： 1. 查找算法的设计实现。 教学过程 新课导入 教师：在生活中，我们经常需要用查找搜寻某个对象，然后对其进行相应操作，例如在学生七选三选课信息表中根据学号查找某位同学的选择科目；如何实现快速查询呢？我们以“航空公司VIP会员积分查询”为例共同探讨。 不少航空公司都会提供优惠的会员服务，当某会员飞行里程累计达到一定数量后，可以使用里程积分兑换奖励机票或奖励升舱等服务。现给定某航空公司部分VIP会员的飞行里程、积分等信息，如表1所示，要求实现根据VIP号码快速查询会员积分的功能。 表 1 某航空公司的部分会员信息表 VIP号姓名飞行里程（km）积分600214韩江辉16801519601278蒋志来532178600815李亚东28745436607854王庆生186139605719李燕7493138603532王晓燕6875102600101郑煜明14253236600087蔡佳宁112703958 表1信息存储在excel表格中，如何实现根据VIP号码快速查询会员的积分呢？请同学们思考。 【设计意图】通过引入生活中的数据分析实例，引导学生思考根据VIP号码查找并显示某个会员的积分的过程。 新授知识 【学习任务一：】抽象与建模 问题：如表1中数据所示，每个会员的信息是一条记录，记录中包含VIP号码、姓名、飞行里程、积分数据项。根据刚刚的思考，快速根据VIP号码找到对应会员的积分，查找应如何进行呢？ 教师总结：要想显示某个会员的积分信息，需要找到此会员在表中的记录，例如要查找VIP号为600087的会员积分，需要找到如下所示的记录； 600087蔡佳宁112703958 【设计意图】引导学生思考复杂数据查找的规律。 【学习任务二：】设计算法与数据结构 问题：在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号码查找会 ... ...