資源簡介

教學設計
課程基本信息
課題 數據查找
教學目標
1.通過具體實例理解查找的概念和基本方法。 2.掌握順序查找的算法思想，熟悉順序查找算法的代碼框架。 3.理解并掌握對分查找的算法思想，熟悉對分查找算法的代碼框架。 4.理解并掌握順序查找與對分查找算法的使用條件和優缺點。
教學內容
教學重點： 1.順序查找算法思想及程序實現。
2.對分查找算法思想及程序實現。 3.順序查找、對分查找算法優缺點。
教學難點： 1.對分查找算法查找過程。
2.對分查找算法基本框架及程序實現。
教學過程
【創設情境】 在亂序撲克牌中尋找“紅桃5”，講一講你的尋找方法？ 學生回答：在亂序撲克牌中，一張一張依次尋找，直到找到為止。 二、【探究學習】 查找的定義 查找（Search）又稱檢索，是計算機根據所給條件查找出滿足條件的對象，即在存儲的一批數據內尋找出一個特定的數據，或者確定在該批數據內是否存在這樣的數據。 常用查找算法：順序查找、對分查找。 順序查找算法基本思想 順序查找又稱線性查找，從順序表的一端開始，依次將每個元素的關鍵字與給定值key（查找鍵）進行比較。若某個元素的關鍵字等于key，則表明查找成功；若所有元素都比較完畢仍找不到，則表明查找失敗。 ”亂序撲克牌查找“——順序查找自然語言描述： 問題描述：在不考慮撲克牌花色的情況下，僅在A到K,13張撲克牌中尋找指定的牌。撲克牌2～ 10 為數字本身,A 為 1 ,J 為 11 ,Q 為 12 ,K 為 13，變量Key存儲要查找的牌。 第一步：將代表13張撲克牌對應的數字存儲于數組d中， 要查找的撲克牌對應數字儲于變量key中。 第二步：依次將d數組中元素與key進行比較。 第三：若數組中某個數與key相等則查找成功,若所有元素比較完畢仍找不到，則查找失敗。 提問：上述算法過程是必修1中學習過的什么算法？ 回答：枚舉算法。 ”亂序撲克牌查找“——順序查找過程演示： 問題： 若將上述問題規模擴大，在n張牌中尋找，則最理想情況是查找_____1__次？最差的情況需要查找____n____次？平均查找次數：___(n+1)/2_____。 平均查找次數：假設將數組中n個數據查找一次所使用的查找次數之和（1+2+3+4+......+n-1+n）再除以數據總個數n。平均查找次數為：(n+1)/2。 6、順序查找算法程序實現： 算法框架：枚舉算法框架（循環結構，循環體內使用分支結構） #key中存儲要查找的數，待查找數據存儲在d數組中。 for i in range（0,n,1）： #遍歷數組索引 if d[i]==key： #如果查找成功，輸出索引位置，并結束查找。 print(i) break else: #全部查找完畢沒找到，輸出“沒找到！” print(“沒找到！”) 順序查找算法小結 三、【創設情境】：在新的撲克牌（ 新撲克牌按照A到K有序排列）中尋找”紅桃5“，除了順序查找有沒有更高效的查找算法？（參考選擇性必修1《數據與數據結構》第4章中的“猜數字游戲”的方法。） 回答：可以使用對分查找方法。 【探究學習對分查找】 1、對分查找算法思想： 首先將查找的數與有序數組內，處于中間位置的數據比較，如果中間位置上的數與查找的數不同，則根據數組的有序性，確定應該在數組的前半部分，還是后半部分繼續查找。在新確定的范圍內，繼續按上述方法，直到獲得最終結果。 2、新撲克牌查找“——對分查找自然語言描述： 問題描述：在不考慮撲克牌花色的情況下，僅在A到K,13張升序排列的撲克牌中尋找指定的牌。撲克牌2～ 10 為數字本身,A 為 1 ,J 為 11 ,Q 為 12 ,K 為 13，變量Key存儲要查找的牌。 第一步：將13張撲克牌對應的數字（升序）存儲于數組d中， 要查找的撲克牌對應數字儲于變量key中。 第二步： 依次將d數組查找區間中間位置的數mid與key進行比較。 第三步： 若mid與key相等則查找成功結束查找,若key大于mid下一次查找區間為右半部分，反之為左半部分。重復第二三兩個步驟直到區間元素個數為零，即查找失敗。 3、”13張升序排列撲克牌“——對分查找過程演示： 4、“13張升序排列撲克牌”——對分查找流程圖描述 5、對分查找程序實現 key=int(input())；f=False；i=0 #所有數據（升序）存儲在數組d中 j= len(d)-1 while i<=j : mid= (i+j)//2 if d[mid]==key: f=True break if d[mid]>key: j=mid-1 else: i=mid+1 if f==True: print("查找成功！下標為"+str(mid)) else: print("沒有找到！") 6、二叉排序樹的定義、對分查找最多查找次數 （1）13張撲克牌對分查找我們可以用一棵二叉樹來表示。 （2）二叉排序樹： ①若左子樹不為空，則左子樹的值均小于它的根節點的值. ②若右子樹不為空，則右子樹的值均大于它的根節點的值 ③它的左右子樹也分別為二叉排序樹。 （3）假設對分查找數據規模為n最多查找次數？ 二叉樹的高度為:int(log2n), 最多查找次數為二叉數高度加1：int(log2n)+1. 順序查找、對分查找對比總結 課堂總結（本節課的主要內容） 查找的定義。 順序查找算法思想及程序實現。 對分查找算法思想及程序實現。 兩種算法的優缺點。
備注：教學設計應至少含教學目標、教學內容、教學過程等三個部分，如有其它內容，可自行補充增加。

展開更多......

收起↑