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号码查找会员积分的流程图，这里会员的记录信息存储在”vip.csv”文件中，首先需要读取文件中数据保存到数组a中，然后按照vip号码对数组a中每个记录进行冒泡排序，接着输出排好序的会员记录信息，最后对输入查询的vip号码进行二分查找并输出查找结果。 教师将“vip.csv”文件和程序文件分发给学生，鼓励学有余力的同学独立实现冒泡排序和二分查找算法并实现上机调试。 教师：经过编程实践，不断地调试运行，同学们有没有更加理解查找算法解决问题的过程？教师讲解程序代码的执行过程。 教师总结：这里冒泡排序和二分查找分别实现了独立的功能，还能不能进一步改进这个代码呢？请同学们根据教材P155-P156页例程完成函数的封装并上机调试运行。 【设计意图】通过流程图的展示、程序代码的讲解和关键函数的封装，帮助学生理解查找算法解决实际问题的实现过程。 教师：通过“航空公司VIP会员积分查询”的实例学习，同学们已经理解用查找算法解决实际问题的过程了，下面我们来看应用实例。 【学习任务四：】生活中的应用实践 某校高一学期结束，学生进行了“七选三”预选课，选课信息存储在“course.csv”中，如图1所示，前3列分别存储学生的学号、姓名、班号，第4列到第10列分别表示物理、化学、生物、政治、历史、地理和技术的选课情况，其中“1”表示选择，“0”表示未选择。李老师编写了一个查询程序，此程序有以下功能：程序运行后自动从“course.csv”中读取学生信息，按照学号从小到大的顺序将所有学生信息排序，并打印输出。输入一个学生的学号，程序自动查找是否存在该学生，若找到，输出该生的“七选三”科目，如果没有找到，则显示“没有查询到该学号信息!”。查询结果如图2所示。 图 1 图 2 查询程序如下，根据代码注释，将横线处缺失的代码补充完整。 #读入csv中数据保存到列表a中 import csv csvFile=open("course.csv","r") #打开文件 reader=csv.reader(csvFile) a=[] for item in reader: #将每行数据（列表）依次追加到列表a中 a.append(item) csvFile.close() #冒泡排序 for i in range(1,len(a)): for j in range(1,len(a)-i): #从第1条记录开始比较 if _________________: #按照每条记录的第0个元素学号进行升序排列 temp=a[j] a[j]=a[j+1] a[j+1]=temp #打印排序后的学生信息 print('排序后：') for i in range(len(a)): print(a[i]) #二分查找 key=int(input("请输入要查找的学号：")) i=1;j=len(a)-1 #查找范围不包含第一行数据 flag=False #设置查找标记 while i<=j: m=(i+j)//2 #取中间索引 if int(a[m][0])==key: _________________ #查找成功，结束查找 break if ________________: #若查找学号<当前学号，查询左区间 j=m-1 else: i=m+1 #根据查找结果输出学生的选考科目 b=['物理','化学','生物','政治','历史','地理','技术'] if flag==True: #查找成功 print(a[m][1],"同学，您的7选3科目为：") for j in range(3,10): if a[m][j]=='1': print(b[j-3],end=" ") else: print("找不到此学号对应的同学信息！")
教师：将“course.csv”文件和待补充的程序文件分发给学生，分析程序代码，引导学生思考填写划线处代码并上机调试运行。 【设计意图】通过学生学习生活中的“七选三”选课科目查询，帮助学生更好的理解排序查找算法在解决生活问题中的应用，培养学生应用算法解决生活实际问题的思维能力。 总结 教师通过思维导图总结本节课内容 【设计意图】通过思维导图总结本节课内容，更清晰的帮助学生梳理查找算法解决实际问题的过程。 课后练习 在“航空公司VIP会员积分查询”问题中，学生尝试将其中的二分查找改成顺序查找，并上机调试运行。 【设计意图】通过课下动手上机实践，加深对算法解决实际问题的过程理解，体会顺序查找和二分查找的异同点。