5.4.3查找算法的应用课件-浙教版高中信息技术选修1

5.4.3查找算法的应用实例分析航空公司VIP会员积分查询不少航空公司都会提供优惠的会员服务，当某会员飞行里程累积达到一定数量后，可以使用里程积分兑换奖励机票或奖励升舱等服务。现给定某航空公司部分VIP会员的飞行里程、积分等信息，如下表所示，要求实现根据VIP号码快速查询会员积分的功能。VIP号姓名飞行里程（km）积分600214韩江辉16801519601278蒋志来532178600815李亚东28745436607854王庆生186139605719李燕7493138603532王晓燕6875102600101郑煜明14253236（1）抽象与建模从表中的数据可以看出，每个会员的信息是一条记录，包括VIP号、姓名、飞行里程、积分等数据项。要显示某个会员的积分信息，先得从多条记录中查找到该会员的记录，如下所示：×××××××××××××××××若用a[i]表示该条记录，则该会员的积分可采用以下形式表示：a[i][3](表示该条记录的第4个数据项的值)（2）设计算法与数据结构对表格数据可采用4个一维数组按列或1个一维数组按行来存储。要显示某个会员的积分，先要从多条会员信息的数据中找到该会员。查找可采用顺序查找算法或二分查找算法。从算法的时间复杂度方面考虑，二分查找算法的效率高于顺序查找算法，但若采用二分查找算法，被查找的数据序列必须是有序的，即要按VIP号为关键字进行排序。（3）编写程序假如数据以1个一维数组按行来存储，利用二分查找算法查找，程序如下：importcsv#数据读入csvFile=open(“vip.csv”,”r”)reader=csv.reader(csvFile)a=[]foriteminreader:a.append(item)csvFile.close()#排序defbubble_sort(d):foriinrange(1,len(d)):forjinrange(1,len(d)-i):ifint(d[j][0])>int(d[j+1][0]):temp=d[j]d[j]=d[j+1]d[j+1]=temp#二分查找defbsearch(s,array):i=1j=len(array)-1whilei<=j:m=(i+j)//2ifint(array[m][0])==s:returnmifs<int(array[m][0]):j=m-1else:i=m+1return-1#未找到返回-1bubble_sort(a)key=int(input(‘请输入要查询的VIP号：’))m=bsearch(key,a)ifm!=-1:print(a[m][1],”先生/女士，您的积分为：”,a[m][3])else:print(‘找不到VIP号对应的用户信息！’)当输入VIP编号“600815”时，程序输出“李亚东先生/女士，您的积分为：436”的信息。若将上例中的二分查找改成顺序查找，代码可写成如下形式：importcsv#数据读入csvFile=open(“vip.csv”,”r”)reader=csv.reader(csvFile)a=[]foriteminreader:a.append(item)csvFile.close()defseq_search(item,a):length=len(a)flag=Falseforiinrange(1,length+1):#查找范围不包含第一行数据ifa[i][0]==item:flag=Truebreakifflag==True:returni

else:return-1key=int(input(‘请输入要查询的VIP号：’))m=bsearch(key,a)ifm!=-1:print(a[m][1],“先生/女士，您的积分为：”,a[m][3])else:print(‘找不到VIP号对应的用户信息！’)

练习用二分查找实现开平方根函数squareroot(x,p)。x是被开方的数，假定输入的数都为非负整数，p是误差上限，输出一个浮点数结果。defsquare(x,p):ifx<0:return-1a=0b=xwhilea<=b:m=(a+b)/2ifabs(m**2-x)<p:returnmelifm**2>x:b=m

else:a=mprint(square(2,0.01))print(square(1,0.01))print(square(9,0.01)