資源簡介

學習任務單
課程基本信息
課題 5.4.2 查找算法的應用
學習目標
1. 學會根據實際情境，分析問題的具體情況，提煉出對應的數據結構模型，并采用相應的算法。 2. 學會合理組織數據并用查找的基本操作編程解決實際問題。 3. 學會靈活應用，能夠對算法模塊知識進行遷移歸納，運用新功能解決實例。
課前學習任務
1. 回顧冒泡排序的核心代碼。 a=[57,32,46,90,68,25] n=len(a) for i in range(n-1): for j in range(_____): #從前往后升序 if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] print(a) 2. 回顧二分查找的基本思想與方法（選修一P149 二分查找）
3. 回顧二分查找核心代碼。 a=[25,32,46,57,68,90] key=int(input("輸入查找關鍵字")) i=0;j=len(a)-1 while i<=j: m=(i+j)//2 if a[m]==key: ____①___ break if____②_____: j=m-1 else: i=m+1 if i>j: print(key,"不在序列a中") else: print(key,"在序列a的第",pos,"位置上") 參考答案： 1. n-i-1 2. ①pos=m ②a[m]>key
課上學習任務
【學習任務一】
航空公司VIP會員積分查詢。不少航空公司都會提供優惠的會員服務，當某會員飛行里程累積達到一定數量后，可以使用里程積分兌換獎勵機票或獎勵升艙等服務。現給定某航空公司VIP會員的飛行里程、積分等信息，如下表所示，要求實現根據VIP號碼快速查詢會員積分的功能。請編寫代碼實現。 一、抽象與建模 每個會員的信息是一條記錄，從眾多的記錄中查找到某會員的記錄，然后將他的積分顯示出來，所以要用________來實現。 二、數據結構 1.表格數據可以一列一列進行存儲，即________，該表中有4列內容，要用4個一維數組表示，當訪問到某條記錄時，獲取對應的數據項可以通過索引來關聯。 2.表格數據的一行就是一條記錄，那么可以________，用一個一維數組a來表示，那么第i行記錄就可以表示為_____，對應的4列內容可以表示為a[i][0]到a[i][3]。 三、設計算法 查找可以采用順序查找和二分查找，從算法的時間復雜度方面考慮，二分查找算法的效率______順序查找，但用二分查找前一定要記得數據有序，即要按VIP號進行排序。 四、編寫程序 請將下列代碼補充完整，并上機調試實現。 #讀入數據 import csv csvFile=open("vip.csv","r") reader=csv.reader(csvFile) a=[] for item in reader: _______①______ csvFile.close() #按VIP號升序排序 def bubble_sort(d): for i in range(1,len(d)): for j in range(1,len(d)-i): if__________②_________: d[j],d[j+1]=d[j+1],d[j] #按VIP號二分查找 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______③______: j=m-1 else: i=m+1 return -1 #未找到返回-1 ______④______ key=int(input(‘請輸入要查詢的VIP號：’)) _______⑤_______ if m!=-1: print(a[m][1],"先生/女士,您的積分為:",a[m][3]) else: print("找不到VIP號對應的用戶信息!")
【學習任務二】
實例拓展：航空公司根據會員的積分推出升級服務，現要對積分在[500,800]的會員進行升級，請編程找出積分在此范圍的所有會員。 設計算法： 一、采用二分查找來實現。先進行排序，排序的關鍵字為______。 二、解決二分查找的幾個問題： 1.要進行_____次二分查找？ 2.500(800)在積分中一定存在嗎？___,若500不存在，查找的是第一個___500的積分，若800不存在，查找的是最后一個___800的積分。請在下圖中分別模擬查找的過程，分別用i,j來表示找到的位置。 3.500(800)的積分會不會存在多個？____，若存在，那么要查找的是___的500和___的800,請在下圖中分別模擬查找的過程，分別用i,j來表示找到的位置。 4.歸納2和3兩種情況，得出結論。 （1）第一個大于等于500的積分在__位置上，若查找的關鍵字設為key，可以得到的結論是：j位置上的數___key ___i位置上的數。 （2）最后一個小于等于800的積分在__位置上，若查找的關鍵字設為key，可以得到的結論是：j位置上的數___key ___i位置上的數。 編寫程序: 請將下列代碼補充完整，并上機調試實現。 #讀入數據 import csv csvFile=open("vip.csv","r") reader=csv.reader(csvFile) a=[] for item in reader: a.append(item) csvFile.close() #按積分升序排序 def bubble_sort1(d): for i in range(1,len(d)): for j in range(1,len(d)-i): if__________①_________: d[j],d[j+1]=d[j+1],d[j] #按積分相等往左查找 def bsearchz(s,array): i=1;j=len(array)-1 while i<=j: m=(i+j)//2 if______②______: j=m-1 else: i=m+1 return i #按積分相等往右查找 def bsearchy(s,array): i=1;j=len(array)-1 while i<=j: m=(i+j)//2 if sint(d[j+1][0]) ③s二、1. 2 2.不一定 大于 小于 3.可能存在 最左邊 最右邊 4.(1) i < <= (2)j <= < 編寫程序： int(d[j][3])>int(d[j+1][3]) ②s<=int(array[m][3]) ③j ④p=bsearchz(key1,a)⑤q=bsearchy(key2,a)⑥in range(p,q+1)

展開更多......

收起↑