資源簡介

教學(xué)設(shè)計(jì)
課程基本信息
課題 5.4 數(shù) 據(jù) 查 找 ——查找算法的應(yīng)用
教學(xué)目標(biāo)
1.通過查找應(yīng)用回顧，引導(dǎo)學(xué)生能對給定的文件中的數(shù)據(jù)進(jìn)行抽象并建立模型。 2.引導(dǎo)學(xué)生能合理選用數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)查找算法。 3.引導(dǎo)學(xué)生能用Python語言編寫具體的查找程序。 4.引導(dǎo)學(xué)生能自覺對學(xué)習(xí)生活具體問題抽象建模、設(shè)計(jì)算法并編寫程序及調(diào)試程序。
指向的核心素養(yǎng)
●信息意識：學(xué)生能夠結(jié)合實(shí)例對給定的文件中的數(shù)據(jù)進(jìn)行抽象并建立模型，有意識地選擇恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)表達(dá)數(shù)據(jù)比較。 ●計(jì)算思維：能夠從數(shù)據(jù)結(jié)構(gòu)的視角審視基于數(shù)組、鏈表的程序，解釋程序中數(shù)據(jù)的組織形式，描述數(shù)據(jù)的邏輯結(jié)構(gòu)及其操作，評判其中數(shù)據(jù)結(jié)構(gòu)運(yùn)用的合理性；能夠針對限定條件的實(shí)際問題進(jìn)行數(shù)據(jù)抽象，運(yùn)用數(shù)據(jù)結(jié)構(gòu)合理組織、存儲(chǔ)數(shù)據(jù)，選擇合適的算法（查找、迭代等）編程實(shí)現(xiàn)、解決問題。 ●數(shù)字化學(xué)習(xí)與創(chuàng)新：要使學(xué)生較為熟練地運(yùn)用查找解決生活中的真實(shí)問題，并在此過程中自主或協(xié)作探究；能夠評估常見的數(shù)字化資源與工具對學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的價(jià)值，根據(jù)需要合理選擇 ●信息社會(huì)責(zé)任：能夠分析數(shù)據(jù)與社會(huì)各領(lǐng)域間的關(guān)系，自覺遵守相應(yīng)的倫理道德和法律法規(guī)。
教學(xué)內(nèi)容
教學(xué)重點(diǎn)： 1.二分查找的算法思想。
2.能熟練用自然語言、流程圖與Python語言來描述查找排序。
教學(xué)難點(diǎn)： Python語言描述變式二分查找。
教學(xué)過程
情景引入 平時(shí)在Excel查找信息，并體驗(yàn)vip號碼的excel查找 航空公司VIP會(huì)員積分查詢部分?jǐn)?shù)據(jù)（Excel數(shù)據(jù)） 抽象與建模
問題：從表中的數(shù)據(jù)可以看出，每個(gè)會(huì)員的信息是一條記錄，包括VIP號、姓名、飛行里程、積分等數(shù)據(jù)項(xiàng)。 實(shí)踐體驗(yàn)：Excel表格中，對記錄快速查詢會(huì)員積分，查找應(yīng)當(dāng)如何進(jìn)行？ 設(shè)計(jì)算法與數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)組織形式有兩種： 方法一是采用4個(gè)一維數(shù)組按列存儲(chǔ)，即每個(gè)數(shù)組分別存儲(chǔ)每個(gè)用戶的VIP號、姓名、飛行里程（KM） 、積分等，如定義a數(shù)組存儲(chǔ)表中每個(gè)用戶的VIP號，其對應(yīng)的值為[“600214”,” 601278 ” ,” 600815 ” ,” 607854” , ” 605719” ……];
定義b數(shù)組存儲(chǔ)表中姓名；
定義c數(shù)組存儲(chǔ)表中飛行里程（KM）；
定義d數(shù)組存儲(chǔ)表中積分信息。 方法二是采用1個(gè)一維數(shù)組按行存儲(chǔ)，每個(gè)數(shù)組元素對應(yīng)某個(gè)國家的一條記錄信息，如a[1]為[600214，韓江輝，16801 ，519]對應(yīng)第一條記錄的相關(guān)信息。 數(shù)據(jù)查找算法有兩種：
查找可采用順序查找算法或二分查找算法, 對數(shù)據(jù)進(jìn)行一次查找，采用順序查找算法。 對數(shù)據(jù)重復(fù)查找，二分查找算法的效率高于順序查找算法， 但二分查找提前：被查找的數(shù)據(jù)序列必須是有序，即在查找VIP號前要按VIP號為關(guān)鍵字進(jìn)行排序。 (三）編寫程序并調(diào)試
算法一:順序查找 程序1： #數(shù)據(jù)讀入 import csv #導(dǎo)入csv模塊 csvFile = open("vip.csv", "r") #打開vip.csv數(shù)據(jù)文件 reader = csv.reader(csvFile) )#建立一個(gè)讀入數(shù)據(jù)的對象reader a = [] #定義空列表a for item in reader: #每一行為a列表一個(gè)元素 a.append(item) #csv通過這種樣式讀入的數(shù)據(jù)為字符串 csvFile.close() #關(guān)閉vip.csv數(shù)據(jù)文件 for i in range(len(a)): #輸出VIP表信息 print(a[i]) key=input('請輸入要查詢的VIP號：') #輸入要查詢的VIP號：key為字符串 #順序查找 f=False #設(shè)置沒查找標(biāo)記 for i in range(1,len(a)): #查詢范圍不包含第一行數(shù)據(jù) if a[i][0]==key: #逐一比較 m=i #記錄找到了的位置 f=True #標(biāo)記查找成功 break #結(jié)束查找 if f==True: #標(biāo)記查找成功，輸出信息 print(a[m][1],"先生/女士，',您的積分為：",a[m][3]) else: #查找不成功，輸出信息 print('找不到VIP號對應(yīng)的用戶信息！') 程序2： #數(shù)據(jù)讀入 import csv #導(dǎo)入csv模塊 csvFile = open("vip.csv", "r") #打開vip.csv數(shù)據(jù)文件 reader = csv.reader(csvFile) #建立一個(gè)讀入數(shù)據(jù)的對象reader a = [] #定義空列表a for item in reader: #每一行為a列表一個(gè)元素,此元素為字符串 a.append(item) #csv通過這種樣式讀入的數(shù)據(jù)為字符串 csvFile.close() #關(guān)閉vip.csv數(shù)據(jù)文件 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 #設(shè)置沒查找標(biāo)記 for i in range(1,len(a)): #查詢范圍不包含第一行數(shù)據(jù) if a[i][0] ==key: #逐一比較 f=True #標(biāo)記查找成功 m=i #記錄找到了的位置 break #結(jié)束查找 return f #返回f f=seq_search(a,key) if f==True: #標(biāo)記查找成功，輸出信息 print(a[m][1],"先生/女士，',您的積分為：",a[m][3]) else: #查找不成功，輸出信息 print('找不到VIP號對應(yīng)的用戶信息！') 觀看運(yùn)行程序 算法二:二分查找 程序1：
import csv #導(dǎo)入csv模塊 #數(shù)據(jù)讀入 csvFile = open("vip.csv", "r") #打開vip.csv數(shù)據(jù)文件 reader = csv.reader(csvFile)#建立一個(gè)讀入數(shù)據(jù)的對象reader a = [] #定義空列表a for item in reader:#每一行為a列表一個(gè)元素,此元素為字符串 a.append(item) #csv通過這種樣式讀入的數(shù)據(jù)為字符串 csvFile.close() #關(guān)閉vip.csv數(shù)據(jù)文件 #冒泡排序 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 #查找范圍不包含第一行數(shù)據(jù)，左端點(diǎn)初值1 j = len(a)-1 #右端點(diǎn)初值為最后一個(gè)元素索引值 f=False #設(shè)置查找標(biāo)記 while i <= j: m = (i+j) //2 #確定中點(diǎn) if int(a[m][0]) ==key:#key與中點(diǎn)VIP號相等 f=True #標(biāo)記查找成功 break #結(jié)束查找 if key < int(a[m][0]): #key<中點(diǎn)VIP號 j = m-1 #到左半?yún)^(qū)間找 else: #key>中點(diǎn)VIP號 i = m+1 #到右邊區(qū)間找 if f==True: #標(biāo)記查找成功，輸出信息 print(a[m][1],"先生/女士,您的積分為：",a[m][3]) else: print('找不到VIP號對應(yīng)的用戶信息！') 程序2：
import csv #導(dǎo)入csv模塊 #數(shù)據(jù)讀入 csvFile = open("vip.csv", "r") #打開vip.csv數(shù)據(jù)文件 reader = csv.reader(csvFile)#建立一個(gè)讀入數(shù)據(jù)的對象reader a = [] #定義空列表a for item in reader:#每一行為a列表一個(gè)元素,此元素為字符串 a.append(item) #csv通過這種樣式讀入的數(shù)據(jù)為字符串 csvFile.close() #關(guān)閉vip.csv數(shù)據(jù)文件 #冒泡排序函數(shù) 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] #二分查找函數(shù) def bsearch(s,array): i = 1 #查找范圍不包含第一行數(shù)據(jù)，左端點(diǎn)初值1 j = len(array)-1#右端點(diǎn)初值為最后一個(gè)元素索引值 f=False #設(shè)置查找標(biāo)記 while i <= j: m = (i+j) //2 #確定中點(diǎn) if int(array[m][0]) ==s:#key與中點(diǎn)VIP號相等 return m #找到就結(jié)束查找，返回中點(diǎn)m if s < int(array[m][0]):#key<中點(diǎn)VIP號 j = m-1 #到左邊區(qū)間找 else: #key>中點(diǎn)VIP號 i = m + 1 #到右邊區(qū)間找 return -1 #未找到返回-1 #主程序 bubble_sort(a) #調(diào)用冒泡排序 print('排序后:') for i in range(len(a)):#輸出排序后的VIP表信息 print(a[i]) key=int(input('請輸入要查詢的VIP號：')) m=bsearch(key,a) #調(diào)用二分查找函數(shù) if m !=-1: #標(biāo)記查找成功，輸出信息 print(a[m][1],"先生/女士，',您的積分為：",a[m][3]) else: #未找到 print('找不到VIP號對應(yīng)的用戶信息！') 觀看運(yùn)行程序 學(xué)習(xí)生活中的應(yīng)用實(shí)踐： 校園一卡通號碼查詢。某校共n名學(xué)生，嚴(yán)老師編寫了一個(gè)校園一卡通號碼查詢程序，輸入號碼就能查詢該號碼所屬的班級和學(xué)生姓名。如右圖所示所有學(xué)生數(shù)據(jù)存儲(chǔ)在“校園一卡通.csv”表格中，該表格分別保存了本校所有學(xué)生的號碼、所在班級和姓名的信息，號碼的編碼規(guī)則為入學(xué)年份+班級加身份證號后三位。第i個(gè)學(xué)生的號碼保存在第1列中，對應(yīng)的班級和姓名保存在第2列和第3列中。輸入號碼，電腦開始查找該號碼的信息，如果找到對應(yīng)的信息，就顯示所屬班級和姓名，如果沒有找到，則顯示“沒有查詢到該號碼信息!”。（以填空形式說明） 相應(yīng)程序如下，請?jiān)诔绦騽澗€①②③處填入相應(yīng)的代碼，把程序補(bǔ)充完整。 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("沒有該號碼信息！")
10

展開更多......

收起↑