資源簡介

(共22張PPT)
5.4 數 據 查 找
——查找算法的應用
冊 別：選擇性必修1
學 科：高中信息技術（浙教版）
學習目標：
能對給定的文件中的數據進行抽象并建立模型。
能合理選用數據結構，設計查找算法。
能用Python語言編寫具體的查找程序。
能自覺對學習生活具體問題抽象建模、設計算法并編寫程序及調試程序。
閱讀教材P141-144，可根據個性學習暫停或加速播放課程。
查找應用：
想一想：
航空公司VIP會員積分查詢部分數據（Excel數據）
VIP號 姓名 飛行里程（KM） 積分
600214 韓江輝 16801 519
601278 蔣志來 5321 78
600815 李亞東 28745 436
607854 王慶生 1861 39
605719 李燕 7493 138
603532 王曉燕 6875 102
600101 鄭煜明 14253 236
600087 蔡佳寧 112703 958
（一）抽象與建模
問題：從表中的數據可以看出，每個會員的信息是一條記錄，包括VIP號、姓名、飛行里程、積分等數據項。
實踐體驗：Excel表格中，對記錄快速查詢會員積分，查找應當如何進行？
VIP號 姓名 飛行里程（KM） 積分
600214 韓江輝 16801 519
601278 蔣志來 5321 78
600815 李亞東 28745 436
607854 王慶生 1861 39
605719 李燕 7493 138
603532 王曉燕 6875 102
600101 鄭煜明 14253 236
600087 蔡佳寧 112703 958
（二）設計算法與數據結構
：
請思考：
數據組織形式有兩種，哪種更適合？
數據查找算法有兩種，哪種更方便？
（二）設計算法與數據結構
數據組織形式有兩種，哪種更方便？
方法一是采用4個一維數組按列存儲，即每個數組分別存儲每個用戶的VIP號、姓名、飛行里程（KM） 、積分等，如定義a數組存儲表中每個用戶的VIP號，其對應的值為[“600214”,” 601278 ” ,” 600815 ” ,” 607854” , ” 605719” ……];
定義b數組存儲表中姓名；
定義c數組存儲表中飛行里程（KM）；
定義d數組存儲表中積分信息。
a b c d
VIP號 姓名 飛行里程（KM） 積分
600214 韓江輝 16801 519
601278 蔣志來 5321 78
600815 李亞東 28745 436
607854 王慶生 1861 39
605719 李燕 7493 138
603532 王曉燕 6875 102
600101 鄭煜明 14253 236
600087 蔡佳寧 112703 958
b[0]
b[1]
b[2]
b[3]
b[4]
b[5]
b[6]
b[7]
c[0]
c[1]
c[2]
c[3]
c[4]
c[5]
c[6]
c[7]
d[0]
d[1]
d[2]
d[3]
d[4]
d[5]
d[6]
d[7]
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
（二）設計算法與數據結構
數據組織形式有兩種，哪種更方便？
方法二是采用1個一維數組按行存儲，每個數組元素對應某個國家的一條記錄信息，如a[1]為[600214，韓江輝，16801 ，519]對應第一條記錄的相關信息。
VIP號為索引值[0]的元素
積分為索引值[3]的元素
VIP號 姓名 飛行里程（KM） 積分
600214 韓江輝 16801 519
601278 蔣志來 5321 78
600815 李亞東 28745 436
607854 王慶生 1861 39
605719 李燕 7493 138
603532 王曉燕 6875 102
600101 鄭煜明 14253 236
600087 蔡佳寧 112703 958
a[i][0] a[i][1] a[i][2] a[i][3]
a[1][0] a[1][1] a[1][2] a[1][3]
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
（二）設計算法與數據結構
：
請思考：數據查找算法有兩種，哪種更方便？
查找可采用順序查找算法或二分查找算法，
對數據進行一次查找，采用順序查找算法。
對數據重復查找，二分查找算法的效率高于順序查找算法，
但二分查找提前：被查找的數據序列必須是有序，即在查找VIP號前要按VIP號為關鍵字進行排序。
(三）編寫程序并調試
#數據讀入
import csv #導入csv模塊
csvFile = open("vip.csv", "r") #打開vip.csv數據文件
reader = csv.reader(csvFile) )#建立一個讀入數據的對象reader
a = [] #定義空列表a
for item in reader: #每一行為a列表一個元素
a.append(item) #csv通過這種樣式讀入的數據為字符串
csvFile.close() #關閉vip.csv數據文件
for i in range(len(a)): #輸出VIP表信息
print(a[i])
key=input('請輸入要查詢的VIP號：') #輸入要查詢的VIP號：key為字符串
#順序查找
f=False #設置沒查找標記
for i in range(1,len(a)): #查詢范圍不包含第一行數據
if a[i][0]==key: #逐一比較
m=i #記錄找到了的位置
f=True #標記查找成功
break #結束查找
if f==True: #標記查找成功，輸出信息
print(a[m][1],"先生/女士，',您的積分為：",a[m][3])
else: #查找不成功，輸出信息
print('找不到VIP號對應的用戶信息！')
（算法一:順序查找）
待查詢文件在vip.csv中
VIP號 姓名 飛行里程（KM） 積分
600214 韓江輝 16801 519
601278 蔣志來 5321 78
600815 李亞東 28745 436
607854 王慶生 1861 39
VIP號 姓名 飛行里程（KM） 積分
(三）編寫程序并調試
#數據讀入
import csv #導入csv模塊
csvFile = open("vip.csv", "r") #打開vip.csv數據文件
reader = csv.reader(csvFile) )#建立一個讀入數據的對象reader
a = [] #定義空列表a
for item in reader: #每一行為a列表一個元素,此元素為字符串
a.append(item) #csv通過這種樣式讀入的數據為字符串
csvFile.close() #關閉vip.csv數據文件
for i in range(len(a)): #輸出VIP表信息
print(a[i])
key=input('請輸入要查詢的VIP號：') #輸入要查詢的VIP號：key為字符串
#順序查找
f=False #設置沒查找標記
for i in range(1,len(a)): #查詢范圍不包含第1行數據
if a[i][0]==key: #逐一比較
m=i #記錄找到了的位置
f=True #標記查找成功
break #結束查找
if f==True: #標記查找成功，輸出信息
print(a[m][1],"先生/女士，',您的積分為：",a[m][3])
else: #查找不成功，輸出信息
print('找不到VIP號對應的用戶信息！')
（算法一:順序查找）
#數據讀入
import csv #導入csv模塊
csvFile = open("vip.csv", "r") #打開vip.csv數據文件
reader = csv.reader(csvFile) #建立一個讀入數據的對象reader
a = [] #定義空列表a
for item in reader: #每一行為a列表一個元素,此元素為字符串
a.append(item) #csv通過這種樣式讀入的數據為字符串
csvFile.close() #關閉vip.csv數據文件
for i in range(len(a)): #輸出VIP表信息
print(a[i])
key=input('請輸入要查詢的VIP號：') #輸入要查詢的VIP號：key為字符
#順序查找
def seq_search(a,key):
global m #定義全局變量m
f=False #設置沒查找標記
for i in range(1,len(a)): #查詢范圍不包含第一行數據
if a[i][0] ==key: #逐一比較
f=True #標記查找成功
m=i #記錄找到了的位置
break #結束查找
return f #返回f
f=seq_search(a,key)
if f==True: #標記查找成功，輸出信息
print(a[m][1],"先生/女士，',您的積分為：",a[m][3])
else: #查找不成功，輸出信息
print('找不到VIP號對應的用戶信息！')
(三）編寫程序并調試
（算法一:順序查找）
#數據讀入
import csv #導入csv模塊
csvFile = open("vip.csv", "r") #打開vip.csv數據文件
reader = csv.reader(csvFile) #建立一個讀入數據的對象reader
a = [] #定義空列表a
for item in reader: #每一行為a列表一個元素,此元素為字符串
a.append(item) #csv通過這種樣式讀入的數據為字符串
csvFile.close() #關閉vip.csv數據文件
for i in range(len(a)): #輸出VIP表信息
print(a[i])
key=input('請輸入要查詢的VIP號：') #輸入要查詢的VIP號：key為字符
#順序查找
def seq_search(a,key):
global m #定義全局變量m
f=False #設置沒查找標記
for i in range(1,len(a)): #查詢范圍不包含第一行數據
if a[i][0] ==key: #逐一比較
f=True #標記查找成功
m=i #記錄找到了的位置
break #結束查找
return f #返回f
f=seq_search(a,key)
if f==True: #標記查找成功，輸出信息
print(a[m][1],"先生/女士，',您的積分為：",a[m][3])
else: #查找不成功，輸出信息
print('找不到VIP號對應的用戶信息！')
(三）編寫程序并調試（算法二:二分查找）
import csv #導入csv模塊
#數據讀入
csvFile = open("vip.csv", "r") #打開vip.csv數據文件
reader = csv.reader(csvFile)#建立一個讀入數據的對象reader
a = [] #定義空列表a
for item in reader:#每一行為a列表一個元素,此元素為字符串
a.append(item) #csv通過這種樣式讀入的數據為字符串
csvFile.close() #關閉vip.csv數據文件
#冒泡排序
for i in range(1,len(a)):
for j in range(1,len(a)-i):
if int(a[j][0])>int(a[j+1][0]): #升序排序
a[j],a[j+1]=a[j+1],a[j]
print('排序后:')
for i in range(len(a)):#輸出排序后的VIP表信息
print(a[i])
key=int(input('請輸入要查詢的VIP號：'))
#二分查找
i = 1 #查找范圍不包含第一行數據，左端點初值1
j = len(a)-1 #右端點初值為最后一個元素索引值
f=False #設置查找標記
while i <= j:
m = (i+j) //2 #確定中點
if int(a[m][0]) ==key:#key與中點VIP號相等
f=True #標記查找成功
break #結束查找
if key < int(a[m][0]): #key<中點VIP號
j = m-1 #到左半區間找
else: #key>中點VIP號
i = m+1 #到右邊區間找
if f==True: #標記查找成功，輸出信息
print(a[m][1],"先生/女士,您的積分為：",a[m][3])
else:
print('找不到VIP號對應的用戶信息！')
(三）編寫程序并調試（算法二:二分查找）
import csv #導入csv模塊
#數據讀入
csvFile = open("vip.csv", "r") #打開vip.csv數據文件
reader = csv.reader(csvFile)#建立一個讀入數據的對象reader
a = [] #定義空列表a
for item in reader:#每一行為a列表一個元素,此元素為字符串
a.append(item) #csv通過這種樣式讀入的數據為字符串
csvFile.close() #關閉vip.csv數據文件
#冒泡排序
for i in range(1,len(a)):
for j in range(1,len(a)-i):
if int(a[j][0])>int(a[j+1][0]): #升序排序
a[j],a[j+1]=a[j+1],a[j]
print('排序后:')
for i in range(len(a)):#輸出排序后的VIP表信息
print(a[i])
key=int(input('請輸入要查詢的VIP號：'))
#二分查找
i = 1 #查找范圍不包含第一行數據，左端點初值1
j = len(a)-1 #右端點初值為最后一個元素索引值
f=False #設置查找標記
while i <= j:
m = (i+j) //2 #確定中點
if int(a[m][0]) ==key:#key與中點VIP號相等
f=True #標記查找成功
break #結束查找
if key < int(a[m][0]): #key<中點VIP號
j = m-1 #到左半區間找
else: #key>中點VIP號
i = m+1 #到右邊區間找
if f==True: #標記查找成功，輸出信息
print(a[m][1],"先生/女士,您的積分為：",a[m][3])
else:
print('找不到VIP號對應的用戶信息！')
(三）編寫程序并調試（算法二:二分查找）
import csv #導入csv模塊
#數據讀入
csvFile = open("vip.csv", "r") #打開vip.csv數據文件
reader = csv.reader(csvFile)#建立一個讀入數據的對象reader
a = [] #定義空列表a
for item in reader:#每一行為a列表一個元素,此元素為字符串
a.append(item) #csv通過這種樣式讀入的數據為字符串
csvFile.close() #關閉vip.csv數據文件
#冒泡排序函數
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]):#升序排序
d[j],d[j+1]=d[j+1],d[j]
#二分查找函數
def bsearch(s,array):
i = 1 #查找范圍不包含第一行數據，左端點初值1
j = len(array)-1#右端點初值為最后一個元素索引值
f=False #設置查找標記
while i <= j:
m = (i+j) //2 #確定中點
if int(array[m][0]) ==s:#s與中點VIP號相等
return m #找到就結束查找，返回中點m
if s < int(array[m][0]):#s<中點VIP號
j = m-1 #到左邊區間找
else: #s>中點VIP號
i = m + 1 #到右邊區間找
return -1 #未找到返回-1
#主程序
bubble_sort(a) #調用冒泡排序
print('排序后:')
for i in range(len(a)):#輸出排序后的VIP表信息
print(a[i])
key=int(input('請輸入要查詢的VIP號：'))
m=bsearch(key,a) #調用二分查找函數
if m !=-1: #標記查找成功，輸出信息
print(a[m][1],"先生/女士，',您的積分為：",a[m][3])
else: #未找到
print('找不到VIP號對應的用戶信息！')
(三）編寫程序并調試（算法二:二分查找）
import csv #導入csv模塊
#數據讀入
csvFile = open("vip.csv", "r") #打開vip.csv數據文件
reader = csv.reader(csvFile)#建立一個讀入數據的對象reader
a = [] #定義空列表a
for item in reader:#每一行為a列表一個元素,此元素為字符串
a.append(item) #csv通過這種樣式讀入的數據為字符串
csvFile.close() #關閉vip.csv數據文件
#冒泡排序函數
def bsort(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]):#升序排序
d[j],d[j+1]=d[j+1],d[j]
#二分查找函數
def bsearch(s,array):
i = 1 #查找范圍不包含第一行數據，左端點初值1
j = len(array)-1#右端點初值為最后一個元素索引值
f=False #設置查找標記
while i <= j:
m = (i+j) //2 #確定中點
if int(array[m][0]) ==s:#s與中點VIP號相等
return m #找到就結束查找，返回中點m
if s < int(array[m][0]):#s<中點VIP號
j = m-1 #到左邊區間找
else: #s>中點VIP號
i = m + 1 #到右邊區間找
return -1 #未找到返回-1
#主程序
bsort(a) #調用冒泡排序
print('排序后:')
for i in range(len(a)):#輸出排序后的VIP表信息
print(a[i])
key=int(input('請輸入要查詢的VIP號：'))
m=bsearch(key,a) #調用二分查找函數
if m !=-1: #標記查找成功，輸出信息
print(a[m][1],"先生/女士，',您的積分為：",a[m][3])
else: #未找到
print('找不到VIP號對應的用戶信息！')
學習生活中的應用實踐：
校園一卡通號碼查詢。某校共n名學生，嚴老師編寫了一個校園一卡通號碼查詢程序，輸入號碼就能查詢該號碼所屬的班級和學生姓名。如右圖所示所有學生數據存儲在“校園一卡通.csv”表格中，該表格分別保存了本校所有學生的號碼、所在班級和姓名的信息，號碼的編碼規則為入學年份+班級加身份證號后三位。第i個學生的號碼保存在第1列中，對應的班級和姓名保存在第2列和第3列中。輸入號碼，電腦開始查找該號碼的信息，如果找到對應的信息，就顯示所屬班級和姓名，如果沒有找到，則顯示“沒有查詢到該號碼信息!”。
學習生活中的應用實踐：
相應程序如下，請在程序劃線①②③處填入相應的代碼，把程序補充完整。
import csv
flie1=open('校園一卡通.csv','r')
reader=csv.reader(flie1)
st=[]
for it in reader:
①
flie1.close()
# 冒泡排序
for i in range(1,len(st)-1):
for j in range(len(st)-1,i,-1):
if ② :
st[j],st[j-1]=st[j-1],st[j]
for i in range(len(st)):
print(st[i])
# 二分查找
key=input(‘請輸入需要查找的卡號：')
i=1;j=len(st)-1
while i<=j:
m=(i+j)//2
if ③ :
i=m+1
else:
j=m-1
if st[i][0]==key:
print(st[0])
print(st[i])
else:
print("沒有該號碼信息！")
st.append(it)
st[j][0]st[m][0]讀取csv文件數據
st[m][0]>=key
課堂小結
抽象與建模
編寫程序并調試
查找算法的應用
設計算法與數據結構
學習評價
對自己的表現進行客觀的評價，并思考后續完善的方向。（3=優秀，2=一般，1=仍需加油）
評分項 自我評價
能對vip.csv文件中的數據進行抽象并建立模型 3 2 1
能對vip.csv數據選用合適的數據結構，設計查找算法 3 2 1
能用Python語言編寫具體的查找程序。 3 2 1
能自覺對學習生活具體問題抽象建模、設計算法并編寫程序及調試程序，如：查找姓名、查找校園卡號等實際應用。 3 2 1
課后作業：
2.用二分查找實現開平方根函數squareroot(x,p)。x是被開方的數，假定輸入的數都為非負數整數，p是誤差上限，輸出一個浮點數結果。程序代碼如下，請在劃線處填入合適的代碼。
def ① :
if x<0:
return -1
a=0
b=x
while a<=b:
②
if abs(m**2-x)return m
elif m**2>x:
③
else:
a=m
print(square(2,0.01))
print(square(1,0.01))
print(square(9,0.01))
print(square(100,0.01))
1.D
2.①square(x,p) ②m=(a+b)/2
③b=m
1.已知輸入a[0]至a[7]的值依次為“88,79,62,55,46,31,20,1”,查找某key值的程序段如下：
i=0;j=7;n=0
key=int(input())
while i<=j:
m=(i+j)//2
if key==a[m]:
break
elif key>a[m]:
j=m-1;n-=1
else:
i=m+1;n+=1
print(n)
當輸入不同的key值，運行該程序后，輸出的不同結果共有：
A.5種 B.6種
C.7種 D.8種
課后作業：
3.某超市商品銷售表結構如下圖所示，為了模擬超市銷售系統的部分功能，某程序具有功能如下：
1)程序運行后自動從shangpin.xlsx表中讀取商品信息，
2)并按照“商品編號”從小到大的順序將所有商品信息排序。
3)用戶輸入一個商品編號 ，程序自動查找是否存在該商品，若找到該商品，將該商品的銷量加1，并返回“操作已成功”的提示信息，若找不到該商品，則提示“不存在該商品”的提示信息。
程序代碼如下，請在劃線處填入合適的代碼。
import pandas as pd
def check(x,y):
i=x
j=y
flag=False
while ① :
m=(i+j)//2
if int(a[m][0])==key:
flag=True
elif int(a[m][0])>key:
j=m-1
else:
②
if flag:
a[m][3]=int(a[m][3])+1
return flag
if __name__=='__main__':
df=pd.read_excel('shangpin.xlsx') #讀取文件
a=df.values.tolist() #將Excel表中的數據轉換成列表
#排序
n=len(a)
for i in range(1,n):
for j in range(n-i):
if int(a[j][0])>int(a[j+1][0]):
a[j],a[j+1]= a[j+1],a[j]
key=int(input("請輸入商品編號："))
if ③ :
df=pd.DataFrame(a,columns=['商品編號','商品名稱','單價','銷售量'])
④ #存入shangpin2.xlsx文件中
print("恭喜，操作已完成！")
else:
print("對不起，不存在該商品，請重新輸入！")
①i<=j and not flag
②i=m+1
③check(0,n-1)
④df.to_excel("shangpin2.xlsx",index=False)

展開更多......

收起↑