资源简介

(共12张PPT)
5.4.3 查找算法的应用
实例分析
航空公司VIP会员积分查询
不少航空公司都会提供优惠的会员服务，当某会员飞行里程累积达到一定数
量后，可以使用里程积分兑换奖励机票或奖励升舱等服务。现给定某航空公
司部分VIP会员的飞行里程、积分等信息，如下表所示，要求实现根据VIP号
码快速查询会员积分的功能。
VIP号 姓名 飞行里程（km） 积分
600214 韩江辉 16801 519
601278 蒋志来 5321 78
600815 李亚东 28745 436
607854 王庆生 1861 39
605719 李燕 7493 138
603532 王晓燕 6875 102
600101 郑煜明 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=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if int(array[m][0])==s:
return m
if sj=m-1
else:
i=m+1
return -1 #未找到返回-1
bubble_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=False
for i in range(1,length+1): #查找范围不包含第一行数据
if a[i][0]==item:
flag=True
break
if flag==True:
return i
else:
return -1
key=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 -1
a=0
b=x
while a<=b:
m=(a+b)/2
if abs(m**2-x)return m
elif m**2>x:
b=m
else:
a=m
print(square(2,0.01))
print(square(1,0.01))
print(square(9,0.01))
print(square(100,0.01))
测试结果：1.4140625
0.99609375
3.00146484375
9.999847412109375
谢 谢

展开更多......

收起↑