5.4.2 查找算法的应用-学习任务单 (1)

学习任务单 课程基本信息 课题 5.4.2 查找算法的应用 学习目标 1. 学会根据实际情境，分析问题的具体情况，提炼出对应的数据结构模型，并采用相应的算法。 2. 学会合理组织数据并用查找的基本操作编程解决实际问题。 3. 学会灵活应用，能够对算法模块知识进行迁移归纳，运用新功能解决实例。 课前学习任务 1. 回顾冒泡排序的核心代码。 a=[57,32,46,90,68,25] n=len(a) for i in range(n-1): for j in range(_____): #从前往后升序 if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] print(a) 2. 回顾二分查找的基本思想与方法（选修一P149 二分查找） 3. 回顾二分查找核心代码。 a=[25,32,46,57,68,90] key=int(input("输入查找关键字")) i=0;j=len(a)-1 while i<=j: m=(i+j)//2 if a[m]==key: ____①___ break if____②_____: j=m-1 else: i=m+1 if i>j: print(key,"不在序列a中") else: print(key,"在序列a的第",pos,"位置上") 参考答案： 1. n-i-1 2. ①pos=m ②a[m]>key 课上学习任务 【学习任务一】 航空公司VIP会员积分查询。不少航空公司都会提供优惠的会员服务，当某会员飞行里程累积达到一定数量后，可以使用里程积分兑换奖励机票或奖励升舱等服务。现给定某航空公司VIP会员的飞行里程、积分等信息，如下表所示，要求实现根据VIP号码快速查询会员积分的功能。请编写代码实现。 一、抽象与建模 每个会员的信息是一条记录，从众多的记录中查找到某会员的记录，然后将他的积分显示出来，所以要用_____来实现。 二、数据结构 1.表格数据可以一列一列进行存储，即_____，该表中有4列内容，要用4个一维数组表示，当访问到某条记录时，获取对应的数据项可以通过索引来关联。 2.表格数据的一行就是一条记录，那么可以_____，用一个一维数组a来表示，那么第i行记录就可以表示为_____，对应的4列内容可以表示为a[i][0]到a[i][3]。 三、设计算法 查找可以采用顺序查找和二分查找，从算法的时间复杂度方面考虑，二分查找算法的效率_____顺序查找，但用二分查找前一定要记得数据有序，即要按VIP号进行排序。 四、编写程序 请将下列代码补充完整，并上机调试实现。 #读入数据 import csv csvFile=open("vip.csv","r") reader=csv.reader(csvFile) a=[] for item in reader: _____①_____ csvFile.close() #按VIP号升序排序 def bubble_sort(d): for i in range(1,len(d)): for j in range(1,len(d)-i): if_____②_____: d[j],d[j+1]=d[j+1],d[j] #按VIP号二分查找 def bsearch(s,array): i=1;j=len(array)-1 while i<=j: m=(i+j)//2 if int(array[m][0])==s: return m if_____③_____: j=m-1 else: i=m+1 return -1 #未找到返回-1 _____④_____ key=int(input(‘请输入要查询的VIP号：’)) _____⑤_____ if m!=-1: print(a[m][1],"先生/女士,您的积分为:",a[m][3]) else: print("找不到VIP号对应的用户信息!") 【学习任务二】 实例拓展：航空公司根据会员的积分推出升级服务，现要对积分在[500,800]的会员进行升级，请编程找出积分在此范围的所有会员。 设计算法： 一、采用二分查找来实现。先进行排序，排序的关键字为_____。 二、解决二分查找的几个问题： 1.要进行_____次二分查找？ 2.500(800)在积分中一定存在吗？___,若500不存在，查找的是第一个___500的积分，若800不存在，查找的是最后一个___800的积分。请在下图中分别模拟查找的过程，分别用i,j来表示找到的位置。 3.500(800)的积分会不会存在多个？____，若存在，那么要查找的是___的500和___的800,请在下图中分别模拟查找的过程，分别用i,j来表示找到的位置。 4.归纳2和3两种情况，得出结论。 （1）第一个大于等于500的积分在__位置上，若查找的关键字设为key，可以得到的结论 ... ...