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

1、說(shuō)課人：說(shuō)課人：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é)過(guò)程、教學(xué)過(guò)程教材分析教材分析 第二章 算法實(shí)例 2.4.3對(duì)分查找和第五章5.4查找算法的程序?qū)崿F(xiàn)，課題定為對(duì)分查找算法及程序?qū)崿F(xiàn)，安排兩個(gè)課時(shí)，第一課時(shí)著重是順序查找和對(duì)分查找算法的形成和初步程序?qū)崿F(xiàn)，第二課時(shí)利用對(duì)分查找算法解決一些實(shí)際問(wèn)題的程序?qū)崿F(xiàn)，本教學(xué)設(shè)計(jì)為第一課時(shí)。 從課程標(biāo)準(zhǔn)和學(xué)科教學(xué)指導(dǎo)意見(jiàn)對(duì)本課教學(xué)內(nèi)容的要求來(lái)看，要求學(xué)生能從問(wèn)題出發(fā)，通過(guò)相應(yīng)的科學(xué)步驟形成對(duì)分查找的算法。對(duì)學(xué)生來(lái)說(shuō)，要求通過(guò)這一課時(shí)的學(xué)習(xí)能初步掌握

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

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

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

5、沒(méi)找到,則輸出找不到. 2、構(gòu)建順序查找的流程圖流程圖，把它轉(zhuǎn)化為程序，讓同學(xué)們補(bǔ)充完整整個(gè)程序。 3、對(duì)順序查找進(jìn)行分析，得出順序查找所需的平均查找次數(shù)為（n+1）/2教學(xué)步驟二：分解順序查找算法教學(xué)步驟二：分解順序查找算法實(shí)例實(shí)例教學(xué)步驟三：分解對(duì)分查找算法教學(xué)步驟三：分解對(duì)分查找算法 解釋二分查找的條件和思想解釋二分查找的條件和思想 一、二分查找的先決條件 表中結(jié)點(diǎn)按關(guān)鍵字有序，且順序（一維數(shù)組）存儲(chǔ)。 二、二分法思想：取中，比較 2 2、假設(shè)、假設(shè)：用一個(gè)數(shù)組d（1 to 10）來(lái)存放升序的元素序列，用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 所以可以確定接下來(lái)要找的范圍是前半部分。 比較后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é)步驟四：評(píng)價(jià)。教學(xué)步驟四：評(píng)價(jià)。 評(píng)價(jià)學(xué)生的程序?qū)崿F(xiàn)情況，并討論或?qū)嵺`問(wèn)題：如果是降序序列，該怎么樣改動(dòng)程序？如果序列元素不是11個(gè)，而是10

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

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

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

10、mid-1N繼續(xù)查繼續(xù)查找？找？輸出輸出“未找未找到到”Y輸出找到的輸出找到的信息信息結(jié)束結(jié)束ijmid=(i+j)2d(mid) high Then 沒(méi)有查找到?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