第8課《快速定位查找算法》ppt課件 信息技術(shù)九下.ppt

1、查找算法設(shè)計,說課人：XXX,目錄,教材分析,第二章 算法實例 2.4.3對分查找和第五章5.4查找算法的程序?qū)崿F(xiàn)，課題定為對分查找算法及程序?qū)崿F(xiàn)，安排兩個課時，第一課時著重是順序查找和對分查找算法的形成和初步程序?qū)崿F(xiàn)，第二課時利用對分查找算法解決一些實際問題的程序?qū)崿F(xiàn)，本教學設(shè)計為第一課時。 從課程標準和學科教學指導(dǎo)意見對本課教學內(nèi)容的要求來看，要求學生能從問題出發(fā)，通過相應(yīng)的科學步驟形成對分查找的算法。對學生來說，要求通過這一課時的學習能初步掌握或了解對分查找的前提條件、解決問題的對象，明確對分查找算法結(jié)構(gòu)和對分查找的意義。,教學目標,知識和能力：通過實例使學生理解對分查找的特點及設(shè)計思想

2、，并學會用對分查找來解決一些實際問題。重視知識的遷移，會將對分查找運用到學習的其它地方，提高學生解決問題的能力。 過程和方法：由小游戲引入，通過實例的漸進學習，學生分組合作交流討論，理解對分查找的方法。 情感態(tài)度和價值觀：激發(fā)學生學習興趣和主動思維，并能初步利用這一方法解決一些同類型的實際生活問題。,教學重點與難點,教學重點： 初步掌握順序查找和對分查找算法的特點。 教學難點： 能理解對分查找算法的設(shè)計思想。,教學方法,圖示法，在對算法進行講解時給出流程 圖。 提問法：讓同學們補充程序設(shè)計。,教學過程,1、新課導(dǎo)入 （1）熱身：游戲 展示一件物品，讓一個學生來猜這個物品的價格，給出提示：在1到

3、50之內(nèi)，我將根據(jù)這個學生猜出的價格提示“高了”或是“低了”。 （2）討論： 你覺得怎么樣猜可以猜的快一點呢？有什么技巧嗎？你從這個游戲當中得到什么啟示？ （3）教師引導(dǎo)： 這個世界不是缺少問題，而是缺少發(fā)現(xiàn)，其實在這個游戲的背后，含有一個非常經(jīng)典的算法。相信通過這節(jié)課的學習就會找到更快的方法來猜出數(shù)字了！,學車問答 學車問題 開車問題 學車怎么辦？駕校大全 中國駕校報名 考試 理論學習 地址 介紹英格駕考 駕考單機版軟件車類小游戲 學車小游戲大全,2、新課：,教學步驟一：解釋查找的概念和查找的方法有順序查找和二分查找 查找的概念 一種數(shù)據(jù)查詢的技術(shù) 在數(shù)組變量中存儲的一批數(shù)據(jù)中找出一個特定的

4、數(shù)據(jù). 查找的分類：順序查找和二分查找,1、 通過圖示得出算法的描述： 取得要找的元素值key 從數(shù)組的第i個位置開始找(i開始等于1) 如果d(i)=key ,則輸出i,并退出循環(huán) 否則i指向下一個位置,繼續(xù)找 如果找到數(shù)組末尾還沒找到,則輸出找不到. 2、構(gòu)建順序查找的流程圖，把它轉(zhuǎn)化為程序，讓同學們補充完整整個程序。 3、對順序查找進行分析，得出順序查找所需的平均查找次數(shù)為（n+1）/2,教學步驟二：分解順序查找算法,教學步驟三：分解對分查找算法,解釋二分查找的條件和思想 一、二分查找的先決條件 表中結(jié)點按關(guān)鍵字有序，且順序（一維數(shù)組）存儲。 二、二分法思想：取中，比較,2、假設(shè)：用一個

5、數(shù)組d（1 to 10）來存放升序的元素序列，用low表示查找范圍的起始位置的下標，high表示終止位置的下標,mid表示中間位置元素的下標。 以查找鍵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 所以可以確定接下來要找的范圍是后半部分。 比較后：low=mid+1 第三次比較： 范圍d(4)d(5)， mid=d(4+5)2)=21,d(mid)=Key ，找到了。,

6、對二分查找方法進行歸納總結(jié),（1）求有序表的中間位置mid （2）若r（mid）=key，查找成功； 若r（mid）key，在左子表中繼續(xù) 進行二分查找； 若r（mid）key，則在右子表中繼續(xù)進行二分查找。 構(gòu)建二分查找的流程圖 二分查找方法的初步程序?qū)崿F(xiàn),教學步驟四：評價。,評價學生的程序?qū)崿F(xiàn)情況，并討論或?qū)嵺`問題：如果是降序序列，該怎么樣改動程序？如果序列元素不是11個，而是100個或更多呢？,教學步驟五：總結(jié)提升。,（1）由于二分查找過程中的每次比較都能使得搜索空間減半，二分查找將不會使用超過log2n次比較來找到目標值。 （2）提升二分查找算法的實際意義：同學們可能還沒有意識到二分查

7、找是多么高效，那不妨設(shè)想一下在一個包含一百萬個人名的電話簿中找一個名字，二分查找可以讓你不超過21次就能找到指定的名字。如果你能夠?qū)⑹澜缟纤械娜税凑招彰判?，那么你可以?5步以內(nèi)找到任何人。,猜數(shù)字：,展示一件物品，讓一個學生來猜這個物品的價格，給出提示：在1到50之內(nèi)，我將根據(jù)這個學生猜出的價格提示“高了”或是“低了”。,29,討論：你覺得怎么樣猜可以猜的快一點呢？有什么技巧嗎？,順序查找,輸入查找的元素值key=32,此時d(i)=key,數(shù)組中的第3個位置,如果輸入查找的元素值key=22,此時i等于5,超過數(shù)組中元素個數(shù),找不到,轉(zhuǎn)化成程序,Private Sub Command3

8、_Click() Key = Val(Text2.Text) i = 1 Do While If Then Text3.Text = 在數(shù)組的第 + Str(i) + 個位置 Exit Do End If Loop If i = n + 1 Then Text3.Text = 在數(shù)組中沒有找到 + Str(Key) End If End Sub,d(i) = Key,i=i+1,以n來表示數(shù)組中元素個數(shù),i= n,順序查找,在第i個位置找到,找到了就退出循環(huán),或者if in then,5 13 19 21 37 56 64 75 80 88 92,5 13 19 21 37,21 37,21,

9、d(mid)key?,Private Sub birSearch(a(), ByVal low%, ByVal high%, ByVal Key, index%) Dim mid As Integer If low high Then 沒有查找到 index = -1 Exit Sub End If mid = (low + high) 2 取查找區(qū)間的中點 If Key = a(mid) Then 查找到，返回下標 index = mid Exit Sub ElseIf Key a(mid) Then 查找區(qū)間在上半部分 high = mid - 1 Else low = mid + 1 查

10、找區(qū)間在下半部分 End If Call birSearch(a, low, high, Key, index) 遞歸調(diào)用查找函數(shù) End Sub,調(diào)用方法： 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), UBound(a), 21, ind) P