資源簡介

(共34張PPT)
5.4.2 查找算法的應用
1.老師請身高在165到170的同學排練舞蹈
2.到超市購買水筆
3.乘公交車刷卡付錢
查找算法 基本算法 操作基礎
生活實例
VIP號 姓名 飛行里程（km）
積分
600214 韓江輝 16801
519
601278 蔣志來 5321
78
600815 李亞東 28745
436
…… …… ……
……
603692 趙新星 5321
78
600087 蔡佳寧 112703
958
不少航空公司都會提供優惠的會員服務，當某會員飛行里程累積達到一定數量 后，可以使用里程積分兌換獎勵機票或獎勵升艙等服務。現給定某航空公司VIP會 員的飛行里程、積分等信息，如下表所示，要求實現根據VIP號碼快速查詢會員積
實例分析 航空公司VIP會員積分查詢
分的功能。
1.抽象與建模
記錄 查找
1.按列存儲 四個一維數組
vip xm lc jf
2.數據結構
jf[2]
xm
vip
[2]
[2]
[2]
lc
2.按行存儲 一個一維數組 a
a[i]
a[2][0] a[2][1] a[2][2] a[2][3]
2.數據結構
順序查找 查找效率低
二分查找 → 查找效率高
數據按VIP號有序
3.設計算法
查找算法
import csv
csvFile=open(" csv","r") reader=csv.reader(csvFile)
a=[]
for item in reader:
_____
csvFile
__
按行存儲的一維數組a 二分查找算法
"vip.csv"
1 讀入數據
類型：字符串
4.編寫程序
a.append(item)
vip.
a[1]
a[0]
2 按VIP號排序
#冒泡排序
def bubble_sort(d):
for i in range(1,len(d)):
for j in range(1,len(d)-i):
d[j], d[j+1]=d[j+1],d[j]
int(d[j][0])>int(d[j+1][0]):
4.編寫程序
if
j=m-1
else:
i=m+1
return -1 #未找到返回-1
if int(array[m][0])==s:
return m
if sj=len(array)-1 while i<=j:
m=(i+j)//2
3 按VIP號查找
#二分查找
):
bsearch(s,array
4.編寫程序
i=1
def
key=int(input(‘請輸入要查詢的VIP號： ’)) m=bsearch(key,a)
if m!=-1:
print(a[m][1],"先生/女士, 您的積分為:",a[m][3]) else:
print("找不到VIP號對應的用戶信息!")
解決問題的關鍵在于分析問題設計算法
#讀入數據存入數組a中 #代碼見P9
def bubble_sort(d):
#代碼見P10
def bsearch(s,array):
#代碼見P11
bubble_sort(a)
_______________
4 調用輸出
4.編寫程序
VIP號 姓名 飛行里程（km）
積分
600214 韓江輝 16801
519
601278 蔣志來 5321
78
600815 李亞東 28745
436
…… …… ……
……
603692 趙新星 5321
78
600087 蔡佳寧 112703
958
實例拓展 航空公司積分升級服 務
航空公司根據會員的積分推出升級服務，現
要對積分在[500,800]的會員進行升級，請編程找 出積分在此范圍的所有會員。
查找積分在[500,800]的會員
二分查找
排序關鍵字： 積分
設計算法
排序
1.要進行幾次二分查找？ 兩次二 分查找
2.500(800)在積分中一定存在嗎？ 可能不存在 >500
i m j
200370 430 560 585 610 790 820 932 968
0 1 2 3 4 5 6 7 8 9
查找積分在[500,800]的會員
設計算法
200370 430 560 585 610 790 820 932 968 i m j
200370 430 560 585 610 790 820 932 968
0 1 2 3 4 5 6 7 8 9
1.要進行幾次二分查找？ 兩次二 分查找
2.500(800)在積分中一定存在嗎？ 可能不存在 >500
j im
查找積分在[500,800]的會員
0 1 2 3 4 5 6 7 8 9
設計算法
1.要進行幾次二分查找？ 兩次二 分查找
2.500(800)在積分中一定存在嗎？ 可能不存在 >500
j i
200370 430 585 790 820 932 968
0 1 2 3 4 5 6 7 8 9
200370 430 585 790 820 932 968
0 1 2 3 4 5 6 7 8 9
j i
560
查找積分在[500,800]的會員
設計算法
610
610
560
m
1.要進行幾次二分查找？ 兩次二 分查找
2.500(800)在積分中一定存在嗎？ 可能不存在 >500
3.500(800)的積分會不會存在多個？ 可能存在 找最左500和最右800 i m j
200470 500 500 500 500 500 650 730 968
0 1 2 3 4 5 6 7 8 9
查找積分在[500,800]的會員
設計算法
1.要進行幾次二分查找？ 兩次二分查找
2.500(800)在積分中一定存在嗎？ 可能不存在 >500
200470 630 760 800 800 800 800 800 968
0 1 2 3 4 5 6 7 8 9
j im
可能存在 找最左500和最右800
3.500(800)的積分會不會存在多個？
200470 500 500 500 500 500 650 730 968
查找積分在[500,800]的會員
0 1 2 3 4 5 6 7 8 9
設計算法
m
i
j
1.要進行幾次二分查找？ 兩次二分查找
2.500(800)在積分中一定存在嗎？ 可能不存在 >500
3.500(800)的積分會不會存在多個？ 可能存在 找最左500和最右800
j i
500
- oj i
200470 630 760 800 800 800 800 800 968
0 1 2 3 4 5 6 7 8 9
200470 500 500 500 650 730 968
查找積分在[500,800]的會員
0 1 2 3 4 5 6 7 8 9
設計算法
500
m
200470 500 500 500 500 500 650 730 968
200370 430 560 585 610 790 820 932 968
查找積分在[500,800]的會員
j位置數1.積分大于等于500
j i
設計算法
i
j
j位置數<=keyj i
200370 430 560 585 610 790 820 932 968
200470 630 760 800 800 800 800 800 968
查找積分在[500,800]的會員
2.積分小于等于800
設計算法
j
i
1 按積分排序
#冒泡排序
def bubble_sort1(d):
for i in range(1,len(d)):
for j in range(1,len(d)-i):
(d[j+1][0]):
int(d[j][0])>int
d[j], d[j+1]=d[j+1],d[j]
4.編寫程序
if
1 按積分排序
#冒泡排序
def bubble_sort1(d):
for i in range(1,len(d)):
for j in range(1,len(d)-i):
(d[j+1][3]):
int(d[j][3])>int
d[j], d[j+1]=d[j+1],d[j]
4.編寫程序
if
def bsearchz(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
200470 500 500 500 500 500 650 730 968
j位置數200370 430 560 585 610 790 820 932 968
2 按積分相等往左查找
j i
i
j
def bsearchz(s,array):
i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if sj=m-1
else:
i=m+1
return -1
200470 500 500 500 500 500 650 730 968
j位置數200370 430 560 585 610 790 820 932 968
2 按積分相等往左查找
j i
i
j
def bsearchz(s,array):
i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if sj=m-1
else:
i=m+1
return -1
200470 500 500 500 500 500 650 730 968
j位置數200370 430 560 585 610 790 820 932 968
2 按積分相等往左查找
j i
i
j
def bsearchz(s,array):
i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if s<=int(array[m][ 3]):
j=m-1
else:
i=m+1
return -1
200470 500 500 500 500 500 650 730 968
j位置數200370 430 560 585 610 790 820 932 968
2 按積分相等往左查找
j i
i
j
def bsearchz(s,array):
i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if s<=int(array[m][ 3]):
j=m-1
else:
i=m+1
return i
200470 500 500 500 500 500 650 730 968
j位置數200370 430 560 585 610 790 820 932 968
2 按積分相等往左查找
j i
i
j
def bsearchz(s,array):
i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if s<=int(array[m][3]):
j=m-1
else:
i=m+1
return □i
200470 500 500 500 500 500 650 730 968
j位置數200370 430 560 585 610 790 820 932 968
2 按積分相等往左查找
j i
i
j
def bsearchy(s,array): i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if s<=int(array[m][3]):
j=m-1
else:
i=m+1
return i
200470 630 760 800 800 800 800 800 968
j位置數<=key200370 430 560 585 610 790 820 932 968
3 按積分相等往右查找
j
j
i
i
def bsearchy(s,array): i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if sj=m-1
else:
i=m+1
return i
200470 630 760 800 800 800 800 800 968
j位置數<=key200370 430 560 585 610 790 820 932 968
3 按積分相等往右查找
j
j
i
i
def bsearchy(s,array): i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if sj=m-1
else:
i=m+1
return j
200470 630 760 800 800 800 800 800 968
j位置數<=key200370 430 560 585 610 790 820 932 968
3 按積分相等往右查找
j
j
i
i
bubble_sort1(a) #按積分排序
key1=int(input("請輸入要查詢的積分最小值:") key2=int(input("請輸入要查詢的積分最大值:")
p=bsearchz(key1,a)
q=bsearchy(key2,a)
print("積分在",key1,"至",key2,"的用戶有:")
for i in range(p,q+1):
print(a[i][1])
3 主程序
#讀入數據存入數組a中 #代碼見P9
def bubble_sort(d):
#代碼見P23
def bsearchz (s,array):
#代碼見P25
def bsearchz (s,array):
#代碼見P26 ★
遷移改變 歸納功能
關鍵要看清找到后繼續往哪邊查找
找到后繼續往左邊找 j位置數找到后繼續往右邊找 j位置數<=key算法思想關鍵點在于查找范圍的不斷縮小， 效率比較高，但要按查找關鍵字先排序
◆找到不退出
◆二分查找
課堂小結

展開更多......

收起↑