資源簡(jiǎn)介

教學(xué)設(shè)計(jì)
課程基本信息
課題 查找算法的應(yīng)用
教學(xué)目標(biāo)
1. 學(xué)會(huì)對(duì)具體問(wèn)題進(jìn)行抽象建模，能根據(jù)問(wèn)題的特點(diǎn)選擇合適的數(shù)據(jù)結(jié)構(gòu)并設(shè)計(jì)算法。 2. 理解并掌握查找算法的實(shí)現(xiàn)過(guò)程，體會(huì)查找算法在生活中的應(yīng)用。 3. 學(xué)會(huì)使用查找算法解決現(xiàn)實(shí)生活、學(xué)習(xí)中遇到的問(wèn)題。 4.通過(guò)計(jì)算機(jī)編程解決實(shí)際問(wèn)題的過(guò)程實(shí)踐，逐步形成問(wèn)題建模能力和分析解決問(wèn)題的能力。
教學(xué)內(nèi)容
教學(xué)重點(diǎn)： 對(duì)具體問(wèn)題的抽象建模。 根據(jù)數(shù)據(jù)特征選擇數(shù)據(jù)結(jié)構(gòu)。 查找算法的設(shè)計(jì)實(shí)現(xiàn)。 教學(xué)難點(diǎn)： 1. 查找算法的設(shè)計(jì)實(shí)現(xiàn)。
教學(xué)過(guò)程
新課導(dǎo)入 教師：在生活中，我們經(jīng)常需要用查找搜尋某個(gè)對(duì)象，然后對(duì)其進(jìn)行相應(yīng)操作，例如在學(xué)生七選三選課信息表中根據(jù)學(xué)號(hào)查找某位同學(xué)的選擇科目；如何實(shí)現(xiàn)快速查詢(xún)呢？我們以“航空公司VIP會(huì)員積分查詢(xún)”為例共同探討。 不少航空公司都會(huì)提供優(yōu)惠的會(huì)員服務(wù)，當(dāng)某會(huì)員飛行里程累計(jì)達(dá)到一定數(shù)量后，可以使用里程積分兌換獎(jiǎng)勵(lì)機(jī)票或獎(jiǎng)勵(lì)升艙等服務(wù)。現(xiàn)給定某航空公司部分VIP會(huì)員的飛行里程、積分等信息，如表1所示，要求實(shí)現(xiàn)根據(jù)VIP號(hào)碼快速查詢(xún)會(huì)員積分的功能。 表 1 某航空公司的部分會(huì)員信息表 VIP號(hào)姓名飛行里程（km）積分600214韓江輝16801519601278蔣志來(lái)532178600815李亞?wèn)|28745436607854王慶生186139605719李燕7493138603532王曉燕6875102600101鄭煜明14253236600087蔡佳寧112703958
表1信息存儲(chǔ)在excel表格中，如何實(shí)現(xiàn)根據(jù)VIP號(hào)碼快速查詢(xún)會(huì)員的積分呢？請(qǐng)同學(xué)們思考。 【設(shè)計(jì)意圖】通過(guò)引入生活中的數(shù)據(jù)分析實(shí)例，引導(dǎo)學(xué)生思考根據(jù)VIP號(hào)碼查找并顯示某個(gè)會(huì)員的積分的過(guò)程。 新授知識(shí) 【學(xué)習(xí)任務(wù)一：】抽象與建模 問(wèn)題：如表1中數(shù)據(jù)所示，每個(gè)會(huì)員的信息是一條記錄，記錄中包含VIP號(hào)碼、姓名、飛行里程、積分?jǐn)?shù)據(jù)項(xiàng)。根據(jù)剛剛的思考，快速根據(jù)VIP號(hào)碼找到對(duì)應(yīng)會(huì)員的積分，查找應(yīng)如何進(jìn)行呢？ 教師總結(jié)：要想顯示某個(gè)會(huì)員的積分信息，需要找到此會(huì)員在表中的記錄，例如要查找VIP號(hào)為600087的會(huì)員積分，需要找到如下所示的記錄； 600087蔡佳寧112703958
【設(shè)計(jì)意圖】引導(dǎo)學(xué)生思考復(fù)雜數(shù)據(jù)查找的規(guī)律。 【學(xué)習(xí)任務(wù)二：】設(shè)計(jì)算法與數(shù)據(jù)結(jié)構(gòu) 問(wèn)題：在Python中如何實(shí)現(xiàn)根據(jù)VIP號(hào)碼找到對(duì)應(yīng)會(huì)員的記錄呢？首先，我們需要考慮用何種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)會(huì)員信息，其次，我們要考慮用哪種算法實(shí)現(xiàn)查找功能。 數(shù)據(jù)結(jié)構(gòu)：對(duì)于每個(gè)會(huì)員，需要保存其完整的一條記錄信息，查找之前需要將所有會(huì)員的信息進(jìn)行存儲(chǔ)，這里可以選取數(shù)組結(jié)構(gòu)來(lái)實(shí)現(xiàn)。此時(shí)可以用兩種方案進(jìn)行儲(chǔ)存： 一：采用4個(gè)一維數(shù)組按列存儲(chǔ)，即每個(gè)數(shù)組分別存儲(chǔ)每個(gè)會(huì)員的VIP號(hào)、姓名、飛行里程(km)和積分，如定義a數(shù)組存儲(chǔ)表中8位會(huì)員的VIP號(hào)，其對(duì)應(yīng)值為 [600214,601278,600815,607854,605719,603532,600101,600087]; 二：采用1個(gè)一維數(shù)組按行存儲(chǔ)，每個(gè)數(shù)組元素對(duì)應(yīng)某位會(huì)員的記錄信息，例如用a數(shù)組存儲(chǔ)，a[i]表示某條記錄，a[i][3]則表示此條記錄的第3個(gè)數(shù)據(jù)項(xiàng)，即為此條記錄的積分。 設(shè)計(jì)算法：要顯示某個(gè)會(huì)員的積分，先要從多條會(huì)員信息的數(shù)據(jù)中找到該會(huì)員。查找可采用順序查找算法或二分查找算法，要實(shí)現(xiàn)快速查詢(xún)，哪種算法的效率更高？請(qǐng)同學(xué)們根據(jù)查找算法的比較(見(jiàn)表2)思考。 表 2 查找算法的比較 教師總結(jié)：根據(jù)表2內(nèi)容，進(jìn)行多次查找時(shí)二分查找的算法效率優(yōu)于順序查找，但二分查找需要被查序列必須是有序的，因此要按VIP號(hào)為關(guān)鍵字對(duì)會(huì)員記錄進(jìn)行排序。排序時(shí)要實(shí)現(xiàn)記錄的兩兩交換，因此采用1個(gè)一維數(shù)組按行存儲(chǔ)處理起來(lái)更方便快捷。 【設(shè)計(jì)意圖】引導(dǎo)學(xué)生思考用何種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)方便后續(xù)處理，引導(dǎo)學(xué)生比較不同查找算法的效率及使用要求。 【學(xué)習(xí)任務(wù)三：】編寫(xiě)程序并上機(jī)調(diào)試 教師：確定用1維數(shù)組存儲(chǔ)數(shù)據(jù)二分查找進(jìn)行查找后，我們來(lái)看一下根據(jù)vip號(hào)碼查找會(huì)員積分的流程圖，這里會(huì)員的記錄信息存儲(chǔ)在”vip.csv”文件中，首先需要讀取文件中數(shù)據(jù)保存到數(shù)組a中，然后按照vip號(hào)碼對(duì)數(shù)組a中每個(gè)記錄進(jìn)行冒泡排序，接著輸出排好序的會(huì)員記錄信息，最后對(duì)輸入查詢(xún)的vip號(hào)碼進(jìn)行二分查找并輸出查找結(jié)果。 教師將“vip.csv”文件和程序文件分發(fā)給學(xué)生，鼓勵(lì)學(xué)有余力的同學(xué)獨(dú)立實(shí)現(xiàn)冒泡排序和二分查找算法并實(shí)現(xiàn)上機(jī)調(diào)試。 教師：經(jīng)過(guò)編程實(shí)踐，不斷地調(diào)試運(yùn)行，同學(xué)們有沒(méi)有更加理解查找算法解決問(wèn)題的過(guò)程？教師講解程序代碼的執(zhí)行過(guò)程。 教師總結(jié)：這里冒泡排序和二分查找分別實(shí)現(xiàn)了獨(dú)立的功能，還能不能進(jìn)一步改進(jìn)這個(gè)代碼呢？請(qǐng)同學(xué)們根據(jù)教材P155-P156頁(yè)例程完成函數(shù)的封裝并上機(jī)調(diào)試運(yùn)行。 【設(shè)計(jì)意圖】通過(guò)流程圖的展示、程序代碼的講解和關(guān)鍵函數(shù)的封裝，幫助學(xué)生理解查找算法解決實(shí)際問(wèn)題的實(shí)現(xiàn)過(guò)程。 教師：通過(guò)“航空公司VIP會(huì)員積分查詢(xún)”的實(shí)例學(xué)習(xí)，同學(xué)們已經(jīng)理解用查找算法解決實(shí)際問(wèn)題的過(guò)程了，下面我們來(lái)看應(yīng)用實(shí)例。 【學(xué)習(xí)任務(wù)四：】生活中的應(yīng)用實(shí)踐 某校高一學(xué)期結(jié)束，學(xué)生進(jìn)行了“七選三”預(yù)選課，選課信息存儲(chǔ)在“course.csv”中，如圖1所示，前3列分別存儲(chǔ)學(xué)生的學(xué)號(hào)、姓名、班號(hào)，第4列到第10列分別表示物理、化學(xué)、生物、政治、歷史、地理和技術(shù)的選課情況，其中“1”表示選擇，“0”表示未選擇。李老師編寫(xiě)了一個(gè)查詢(xún)程序，此程序有以下功能：程序運(yùn)行后自動(dòng)從“course.csv”中讀取學(xué)生信息，按照學(xué)號(hào)從小到大的順序?qū)⑺袑W(xué)生信息排序，并打印輸出。輸入一個(gè)學(xué)生的學(xué)號(hào)，程序自動(dòng)查找是否存在該學(xué)生，若找到，輸出該生的“七選三”科目，如果沒(méi)有找到，則顯示“沒(méi)有查詢(xún)到該學(xué)號(hào)信息!”。查詢(xún)結(jié)果如圖2所示。 圖 1 圖 2 查詢(xún)程序如下，根據(jù)代碼注釋?zhuān)瑢M線處缺失的代碼補(bǔ)充完整。 #讀入csv中數(shù)據(jù)保存到列表a中 import csv csvFile=open("course.csv","r") #打開(kāi)文件 reader=csv.reader(csvFile) a=[] for item in reader: #將每行數(shù)據(jù)（列表）依次追加到列表a中 a.append(item) csvFile.close() #冒泡排序 for i in range(1,len(a)): for j in range(1,len(a)-i): #從第1條記錄開(kāi)始比較 if _________________: #按照每條記錄的第0個(gè)元素學(xué)號(hào)進(jìn)行升序排列 temp=a[j] a[j]=a[j+1] a[j+1]=temp #打印排序后的學(xué)生信息 print('排序后：') for i in range(len(a)): print(a[i]) #二分查找 key=int(input("請(qǐng)輸入要查找的學(xué)號(hào)：")) i=1;j=len(a)-1 #查找范圍不包含第一行數(shù)據(jù) flag=False #設(shè)置查找標(biāo)記 while i<=j: m=(i+j)//2 #取中間索引 if int(a[m][0])==key: _________________ #查找成功，結(jié)束查找 break if ________________: #若查找學(xué)號(hào)<當(dāng)前學(xué)號(hào)，查詢(xún)左區(qū)間 j=m-1 else: i=m+1 #根據(jù)查找結(jié)果輸出學(xué)生的選考科目 b=['物理','化學(xué)','生物','政治','歷史','地理','技術(shù)'] if flag==True: #查找成功 print(a[m][1],"同學(xué)，您的7選3科目為：") for j in range(3,10): if a[m][j]=='1': print(b[j-3],end=" ") else: print("找不到此學(xué)號(hào)對(duì)應(yīng)的同學(xué)信息！")
教師：將“course.csv”文件和待補(bǔ)充的程序文件分發(fā)給學(xué)生，分析程序代碼，引導(dǎo)學(xué)生思考填寫(xiě)劃線處代碼并上機(jī)調(diào)試運(yùn)行。 【設(shè)計(jì)意圖】通過(guò)學(xué)生學(xué)習(xí)生活中的“七選三”選課科目查詢(xún)，幫助學(xué)生更好的理解排序查找算法在解決生活問(wèn)題中的應(yīng)用，培養(yǎng)學(xué)生應(yīng)用算法解決生活實(shí)際問(wèn)題的思維能力。 總結(jié) 教師通過(guò)思維導(dǎo)圖總結(jié)本節(jié)課內(nèi)容 【設(shè)計(jì)意圖】通過(guò)思維導(dǎo)圖總結(jié)本節(jié)課內(nèi)容，更清晰的幫助學(xué)生梳理查找算法解決實(shí)際問(wèn)題的過(guò)程。 課后練習(xí) 在“航空公司VIP會(huì)員積分查詢(xún)”問(wèn)題中，學(xué)生嘗試將其中的二分查找改成順序查找，并上機(jī)調(diào)試運(yùn)行。 【設(shè)計(jì)意圖】通過(guò)課下動(dòng)手上機(jī)實(shí)踐，加深對(duì)算法解決實(shí)際問(wèn)題的過(guò)程理解，體會(huì)順序查找和二分查找的異同點(diǎn)。

展開(kāi)更多......

收起↑