资源简介 (共12张PPT)5.4.3 查找算法的应用实例分析航空公司VIP会员积分查询不少航空公司都会提供优惠的会员服务,当某会员飞行里程累积达到一定数量后,可以使用里程积分兑换奖励机票或奖励升舱等服务。现给定某航空公司部分VIP会员的飞行里程、积分等信息,如下表所示,要求实现根据VIP号码快速查询会员积分的功能。VIP号 姓名 飞行里程(km) 积分600214 韩江辉 16801 519601278 蒋志来 5321 78600815 李亚东 28745 436607854 王庆生 1861 39605719 李燕 7493 138603532 王晓燕 6875 102600101 郑煜明 14253 236(1)抽象与建模从表中的数据可以看出,每个会员的信息是一条记录,包括VIP号、姓名、飞行里程、积分等数据项。要显示某个会员的积分信息,先得从多条记录中查找到该会员的记录,如下所示:×××××× ××× ××××× ×××若用a[i]表示该条记录,则该会员的积分可采用以下形式表示:a[i][3](表示该条记录的第4个数据项的值)(2)设计算法与数据结构对表格数据可采用4个一维数组按列或1个一维数组按行来存储。要显示某个会员的积分,先要从多条会员信息的数据中找到该会员。查找可采用顺序查找算法或二分查找算法。从算法的时间复杂度方面考虑,二分查找算法的效率高于顺序查找算法,但若采用二分查找算法,被查找的数据序列必须是有序的,即要按VIP号为关键字进行排序。(3)编写程序假如数据以1个一维数组按行来存储,利用二分查找算法查找,程序如下:import csv#数据读入csvFile=open(“vip.csv”,”r”)reader=csv.reader(csvFile)a=[]for item in reader:a.append(item)csvFile.close()#排序def bubble_sort(d):for i in range(1,len(d)):for j in range(1,len(d)-i):if int(d[j][0])>int(d[j+1][0]):temp=d[j]d[j]=d[j+1]d[j+1]=temp#二分查找def bsearch(s,array):i=1j=len(array)-1while i<=j:m=(i+j)//2if int(array[m][0])==s:return mif sj=m-1else:i=m+1return -1 #未找到返回-1bubble_sort(a)key=int(input(‘请输入要查询的VIP号:’))m=bsearch(key,a)if m!=-1:print(a[m][1],”先生/女士,您的积分为:”,a[m][3])else:print(‘找不到VIP号对应的用户信息!’)当输入VIP编号“600815”时,程序输出“李亚东 先生/女士,您的积分为:436”的信息。若将上例中的二分查找改成顺序查找,代码可写成如下形式:import csv#数据读入csvFile=open(“vip.csv”,”r”)reader=csv.reader(csvFile)a=[ ]for item in reader:a.append(item)csvFile.close()def seq_search(item,a):length=len(a)flag=Falsefor i in range(1,length+1): #查找范围不包含第一行数据if a[i][0]==item:flag=Truebreakif flag==True:return ielse:return -1key=int(input(‘请输入要查询的VIP号:’))m=bsearch(key,a)if m!=-1:print(a[m][1],“先生/女士,您的积分为:”,a[m][3])else:print(‘找不到VIP号对应的用户信息!’)一般地,对于顺序查找平均查找长度ASL=,查找不成功时,比较总次数为n次。对于二分查找而言,考虑n个节点的二分判定树的高度不超过int(),采用二分查找成功时比较次数不超过int() +1。练 习用二分查找实现开平方根函数squareroot(x,p)。x是被开方的数,假定输入的数都为非负整数,p是误差上限,输出一个浮点数结果。def square(x,p):if x<0:return -1a=0b=xwhile a<=b:m=(a+b)/2if abs(m**2-x)return melif m**2>x:b=melse:a=mprint(square(2,0.01))print(square(1,0.01))print(square(9,0.01))print(square(100,0.01))测试结果:1.41406250.996093753.001464843759.999847412109375谢 谢 展开更多...... 收起↑ 资源预览