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

1、說課人：說課人：XXXXXX1 1、教材分析、教材分析2 2、教學(xué)目標(biāo)、教學(xué)目標(biāo) 3 3、教學(xué)重點(diǎn)與難點(diǎn)、教學(xué)重點(diǎn)與難點(diǎn) 4 4、教學(xué)方法、教學(xué)方法5 5、教學(xué)過程、教學(xué)過程教材分析教材分析 第二章 算法實例 2.4.3對分查找和第五章5.4查找算法的程序?qū)崿F(xiàn)，課題定為對分查找算法及程序?qū)崿F(xiàn)，安排兩個課時，第一課時著重是順序查找和對分查找算法的形成和初步程序?qū)崿F(xiàn)，第二課時利用對分查找算法解決一些實際問題的程序?qū)崿F(xiàn)，本教學(xué)設(shè)計為第一課時。 從課程標(biāo)準(zhǔn)和學(xué)科教學(xué)指導(dǎo)意見對本課教學(xué)內(nèi)容的要求來看，要求學(xué)生能從問題出發(fā)，通過相應(yīng)的科學(xué)步驟形成對分查找的算法。對學(xué)生來說，要求通過這一課時的學(xué)習(xí)能初步掌握

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

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

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

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

6、素的下標(biāo)。 以查找鍵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，在左子表中繼續(xù) 進(jìn)行二分查找； 若r（mid）key，則在右子表中繼續(xù)進(jìn)行二分查找。構(gòu)建二分查找的流程圖流程圖二分查找方法的初步程序?qū)崿F(xiàn)教學(xué)步驟四：評價。教學(xué)步驟四：評價。 評價學(xué)生的程序?qū)崿F(xiàn)情況，并討論或?qū)嵺`問題：如果是降序序列，該怎么樣改動程序？如果序列元素不是11個，而是10

7、0個或更多呢？教學(xué)步驟五：總結(jié)提升。教學(xué)步驟五：總結(jié)提升。 （1）由于二分查找過程中的每次比較都能使得搜索空間減半，二分查找將不會使用超過log2n次比較來找到目標(biāo)值。 （2）提升二分查找算法的實際意義：同學(xué)們可能還沒有意識到二分查找是多么高效，那不妨設(shè)想一下在一個包含一百萬個人名的電話簿中找一個名字，二分查找可以讓你不超過21次就能找到指定的名字。如果你能夠?qū)⑹澜缟纤械娜税凑招彰判?，那么你可以?5步以內(nèi)找到任何人。下一頁頁展示一件物品，讓一個學(xué)生來猜這個展示一件物品，讓一個學(xué)生來猜這個物品的價格，給出提示：在物品的價格，給出提示：在1到到50之內(nèi)，之內(nèi)，我將根據(jù)這個學(xué)生猜出的價格提示我

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

9、n Text3.Text = 在數(shù)組的第 + Str(i) + 個位置 Exit Do End IfLoopIf i = n + 1 Then Text3.Text = 在數(shù)組中沒有找到 + Str(Key)End IfEnd Subd(i) = Keyi=i+1以n來表示數(shù)組中元素個數(shù)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繼續(xù)查繼續(xù)查找？找？輸出輸出“未找未找到到”Y輸出找到的輸出找到的信息信息結(jié)束結(jié)束ijmid=(i+j)2d(mid) high Then 沒有查找到?jīng)]有查找到 index = -1 Exit Sub End If mid = (low + high) 2 取查找區(qū)間的中點(diǎn)取查找區(qū)間的中點(diǎn) If Key = a(mid) Then 查找到，返回下標(biāo)查找到，返回下標(biāo) index = mid Exit Sub ElseIf Key a(mid) Then 查找區(qū)間在上半部分查找區(qū)間在上半部分 high = mid - 1 Else low = mid + 1 查找區(qū)間在下半部分查找區(qū)間

11、在下半部分 End If Call birSearch(a, low, high, Key, index) 遞歸調(diào)用查找函數(shù)遞歸調(diào)用查找函數(shù) End Sub調(diào)用方法：調(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), UBou