1、說課人：說課人：XXXXXX1 1、教材分析、教材分析2 2、教學目標、教學目標 3 3、教學重點與難點、教學重點與難點 4 4、教學方法、教學方法5 5、教學過程、教學過程教材分析教材分析 第二章 算法實例 2.4.3對分查找和第五章5.4查找算法的程序實現，課題定為對分查找算法及程序實現，安排兩個課時，第一課時著重是順序查找和對分查找算法的形成和初步程序實現，第二課時利用對分查找算法解決一些實際問題的程序實現，本教學設計為第一課時。 從課程標準和學科教學指導意見對本課教學內容的要求來看，要求學生能從問題出發，通過相應的科學步驟形成對分查找的算法。對學生來說，要求通過這一課時的學習能初步掌握

2、或了解對分查找的前提條件、解決問題的對象，明確對分查找算法結構和對分查找的意義。教學目標教學目標 知識和能力：通過實例使學生理解對分查找的特點及設計思想，并學會用對分查找來解決一些實際問題。重視知識的遷移，會將對分查找運用到學習的其它地方，提高學生解決問題的能力。 過程和方法：由小游戲引入，通過實例的漸進學習，學生分組合作交流討論，理解對分查找的方法。 情感態度和價值觀：激發學生學習興趣和主動思維，并能初步利用這一方法解決一些同類型的實際生活問題。教學重點與難點教學重點與難點 教學重點：教學重點： 初步掌握順序查找和對分查找算法的特點。 教學難點：教學難點： 能理解對分查找算法的設計思想。教學

3、方法教學方法 圖示法，在對算法進行講解時給出流程 圖。 提問法：讓同學們補充程序設計。 教學過程教學過程 1 1、新課導入、新課導入 （1）熱身）熱身：游戲 展示一件物品，讓一個學生來猜這個物品的價格，給出提示：在1到50之內，我將根據這個學生猜出的價格提示“高了”或是“低了”。 （2）討論：）討論： 你覺得怎么樣猜可以猜的快一點呢？有什么技巧嗎？你從這個游戲當中得到什么啟示？ （3）教師引導：）教師引導： 這個世界不是缺少問題，而是缺少發現，其實在這個游戲的背后，含有一個非常經典的算法。相信通過這節課的學習就會找到更快的方法來猜出數字了！實例實例學車問答 http:/ 學車問題 開車問題 學

4、車怎么辦？駕校大全 http:/ 中國駕校報名 考試 理論學習 地址 介紹英格駕考 http:/ 駕考單機版軟件車類小游戲 http:/ 學車小游戲大全2 2、新課：、新課： 教學步驟一：解釋查找的概念和查找的方法有教學步驟一：解釋查找的概念和查找的方法有順序查找和二分查找順序查找和二分查找 查找的概念 一種數據查詢的技術 在數組變量中存儲的一批數據中找出一個特定的數據. 查找的分類：順序查找和二分查找 1、 通過圖示得出算法的描述： 取得要找的元素值key 從數組的第i個位置開始找(i開始等于1) 如果d(i)=key ,則輸出i,并退出循環 否則i指向下一個位置,繼續找 如果找到數組末尾還

5、沒找到,則輸出找不到. 2、構建順序查找的流程圖流程圖，把它轉化為程序，讓同學們補充完整整個程序。 3、對順序查找進行分析，得出順序查找所需的平均查找次數為（n+1）/2教學步驟二：分解順序查找算法教學步驟二：分解順序查找算法實例實例教學步驟三：分解對分查找算法教學步驟三：分解對分查找算法 解釋二分查找的條件和思想解釋二分查找的條件和思想 一、二分查找的先決條件 表中結點按關鍵字有序，且順序（一維數組）存儲。 二、二分法思想：取中，比較 2 2、假設、假設：用一個數組d（1 to 10）來存放升序的元素序列，用low表示查找范圍的起始位置的下標，high表示終止位置的下標,mid表示中間位置元

6、素的下標。 以查找鍵KEY=21為例分析 第一次比較：第一次比較： 范圍d(1)d(11),mid=d(1+11)2)=56, d(mid)Key 所以可以確定接下來要找的范圍是前半部分。 比較后high=mid-1 第二次比較：第二次比較： 范圍d(1)d(5),mid=d(1+5)2)=19,d(mid)key，在左子表中繼續 進行二分查找； 若r（mid）key，則在右子表中繼續進行二分查找。構建二分查找的流程圖流程圖二分查找方法的初步程序實現教學步驟四：評價。教學步驟四：評價。 評價學生的程序實現情況，并討論或實踐問題：如果是降序序列，該怎么樣改動程序？如果序列元素不是11個，而是10

7、0個或更多呢？教學步驟五：總結提升。教學步驟五：總結提升。 （1）由于二分查找過程中的每次比較都能使得搜索空間減半，二分查找將不會使用超過log2n次比較來找到目標值。 （2）提升二分查找算法的實際意義：同學們可能還沒有意識到二分查找是多么高效，那不妨設想一下在一個包含一百萬個人名的電話簿中找一個名字，二分查找可以讓你不超過21次就能找到指定的名字。如果你能夠將世界上所有的人按照姓名排序，那么你可以在35步以內找到任何人。下一頁頁展示一件物品，讓一個學生來猜這個展示一件物品，讓一個學生來猜這個物品的價格，給出提示：在物品的價格，給出提示：在1到到50之內，之內，我將根據這個學生猜出的價格提示我

8、將根據這個學生猜出的價格提示“高了高了”或是或是“低了低了”。 29討論：你覺得怎么樣猜可以猜的快一點呢？有什么技巧嗎？返回27363218d (1) d (2) d (3) d (4) 輸入查找的元素值輸入查找的元素值key=32i=1i=2i=3此時d(i)=key,數組中的第3個位置如果輸入查找的元素值key=22i=1i=2i=3i=4i=527363218d (1) d (2) d (3) d (4) 此時i等于5,超過數組中元素個數,找不到返回Private Sub Command3_Click() Key = Val(Text2.Text)i = 1Do While If The

9、n Text3.Text = 在數組的第 + Str(i) + 個位置 Exit Do End IfLoopIf i = n + 1 Then Text3.Text = 在數組中沒有找到 + Str(Key)End IfEnd Subd(i) = Keyi=i+1以n來表示數組中元素個數i= n開始i=1in thenif in then返回5 13 19 21 37 56 64 75 80 88 92lowmidhigh5 13 19 21 37lowhigh21 37lowhighmidmid21返回YYN開開始始i1,j10計算計算midd(mid)=key?Ni= =mid+1J= =

10、mid-1N繼續查繼續查找？找？輸出輸出“未找未找到到”Y輸出找到的輸出找到的信息信息結束結束ijmid=(i+j)2d(mid) high Then 沒有查找到沒有查找到 index = -1 Exit Sub End If mid = (low + high) 2 取查找區間的中點取查找區間的中點 If Key = a(mid) Then 查找到，返回下標查找到，返回下標 index = mid Exit Sub ElseIf Key a(mid) Then 查找區間在上半部分查找區間在上半部分 high = mid - 1 Else low = mid + 1 查找區間在下半部分查找區間

11、在下半部分 End If Call birSearch(a, low, high, Key, index) 遞歸調用查找函數遞歸調用查找函數 End Sub調用方法：調用方法： Private Sub Command1_Click() Dim a(11) a(1) = 5: a(2) = 13: a(3) = 19: a(4) = 21: a(5) = 37 a(6) = 56: a(7) = 64: a(8) = 75: a(9) = 80: a(10) = 88: a(11) = 92 Dim ind As Integer Call birSearch(a, LBound(a), UBou