折半查找算法及程序?qū)崿F(xiàn)教案

1、.折半查找算法及程序?qū)崿F(xiàn)一、教材分析教學(xué)重點(diǎn)：以圖示法方式，演示折半查找算法的基本思想。教學(xué)難點(diǎn)：由折半查找算法的思想到程序代碼編寫(xiě)的轉(zhuǎn)換，尤其是其中關(guān)鍵性語(yǔ)句的編寫(xiě)是教學(xué)中的難點(diǎn)。二、學(xué)情分析學(xué)生應(yīng)該已經(jīng)掌握程序設(shè)計(jì)的基本思想，掌握賦值語(yǔ)句、選擇語(yǔ)句、循環(huán)語(yǔ)句的基本用法和VB基本操作，這節(jié)課學(xué)生可能會(huì)遇到的最大問(wèn)題是：如何歸納總結(jié)對(duì)分查找解決不同情況問(wèn)題的一般規(guī)律，鑒于此，在教學(xué)中要積極引導(dǎo)學(xué)生采取分解動(dòng)作、比較遷移等學(xué)習(xí)策略。三、教學(xué)目標(biāo)知識(shí)與技能：理解對(duì)分查找的概念和特點(diǎn)，通過(guò)分步解析獲取對(duì)分查找的解題結(jié)構(gòu)，初步掌握對(duì)分查找算法的程序?qū)崿F(xiàn)。過(guò)程與方法：通過(guò)分析多種不同的可能情況，逐步歸納

2、對(duì)分查找的基本思想和方法，確定解題步驟。情感態(tài)度與價(jià)值觀：通過(guò)實(shí)踐體驗(yàn)科學(xué)解題的重要性，增強(qiáng)效率意識(shí)和全局觀念，感受對(duì)分查找算法的魅力，養(yǎng)成始終堅(jiān)持、不斷積累才能獲得成功的意志品質(zhì)。四、教學(xué)策略與手段1、教學(xué)線索：游戲引領(lǐng)-提出對(duì)分查找原理- 解析對(duì)分查找的算法特征-實(shí)踐解決問(wèn)題。2、學(xué)習(xí)線索：分解問(wèn)題-歸納問(wèn)題-實(shí)踐提升，在三個(gè)階段的不斷推進(jìn)中明確對(duì)分查找算法，總結(jié)規(guī)律。五、教學(xué)過(guò)程1、新課導(dǎo)入（1）熱身：游戲（2分鐘）找同學(xué)上來(lái)找一本上千頁(yè)電話冊(cè)里面的一個(gè)名字。(課程導(dǎo)入我寫(xiě)的不是很詳細(xì)，自己設(shè)計(jì)哦)（2）教師引導(dǎo)：所以我不希望只有他一個(gè)人體驗(yàn)這種方便，我們教室里還有一大幫人，其實(shí)這種什么

3、不止用于查找電話鋪，還可以運(yùn)用到實(shí)際生活中，教室里有這么多人，坦白說(shuō)，按學(xué)校的老方法一個(gè)人一個(gè)人的數(shù)，對(duì)所有老師來(lái)說(shuō)都及其費(fèi)力，那我們想想，是不是數(shù)數(shù)2368，這樣好點(diǎn)對(duì)嗎？。不要小看這種想法，他其實(shí)是非常棒的，他能把解決問(wèn)題的時(shí)間縮短一半，因此我們提出了這種算法2、新課：首先我們一起來(lái)看一看折半查詢算法中的“折半”的含義。師：何為折半呢？生：減半；打一半的折扣。例如，我手里拿著一根繩子，現(xiàn)在我們來(lái)進(jìn)行折半試驗(yàn)，首先拿住繩子的兩個(gè)端點(diǎn)，然后從中點(diǎn)的位置進(jìn)行對(duì)折，這樣繩子就縮短為原來(lái)長(zhǎng)度一半，然后將一半的繩子繼續(xù)執(zhí)行與剛才相同的操作，使得繩子的長(zhǎng)度逐漸的縮短，直到繩子長(zhǎng)度短得不能再進(jìn)行折半了。師

4、：那什么時(shí)候就不能再折半了呢？生：即繩子的兩個(gè)端點(diǎn)合二為一為止。折半查找算法的思想與繩子折半的過(guò)程基本相同。下面我們先通過(guò)圖示來(lái)看看折半查找算法究竟是什么？教學(xué)步驟二：分解對(duì)分查找算法（5分鐘）假設(shè)一個(gè)從小到大排列的數(shù)據(jù)存放在一個(gè)數(shù)組中Data(10)，而查找數(shù)據(jù)存放在變量x中。如圖1所示，橙色方框的代表的是查詢數(shù)據(jù)x，每個(gè)淺蘭色方框代表的是數(shù)組中的每個(gè)元素，框內(nèi)顯示的數(shù)據(jù)是每個(gè)數(shù)組元素對(duì)應(yīng)的下標(biāo)（序號(hào)），整排的淺蘭色方框就可以看成整個(gè)數(shù)組，即待查數(shù)據(jù)表（數(shù)組元素表）。x012345678910LowHigh圖一第一步：就像抓住繩子的兩端一樣，首先設(shè)立兩個(gè)標(biāo)記Low、High分別來(lái)標(biāo)識(shí)查詢區(qū)間

5、的低端和高端，即數(shù)組元素的下標(biāo)，如圖1所示。師：對(duì)于初始查詢區(qū)間，它們是多少呢？生：Low=0 ， High=10第二步：取區(qū)間的中點(diǎn)標(biāo)記Mid，如圖2所示。師：查詢區(qū)間的中點(diǎn)為多少？（這個(gè)地方，有的學(xué)生可能直接說(shuō)出下標(biāo)值，所以要提醒學(xué)生讓中點(diǎn)和兩個(gè)端點(diǎn)相聯(lián)系，即用端點(diǎn)表示中點(diǎn)）生：Mid=(Low+High)/2師：中點(diǎn)位置上的數(shù)據(jù)為什么？(提醒學(xué)生數(shù)據(jù)是放在數(shù)組Data中的) 生：Data( Mid) 012345678910MidLowHigh第三步：判斷中點(diǎn)位置上的數(shù)據(jù)Data( Mid)與要查找數(shù)x是否相等，如何相等，則找到，并結(jié)束查找；如果不相等，就執(zhí)行第四步。師：這個(gè)判斷語(yǔ)句如何

6、寫(xiě)呢？生：if Data( Mid)=x thenprint “x找到”結(jié)束查找end if第四步：如果不相等，那么對(duì)查詢區(qū)間進(jìn)行折半操作。師：那如何折半是從中點(diǎn)處向左側(cè)折半還是向右側(cè)折半？（這是整個(gè)折半查詢進(jìn)行下去的關(guān)鍵所在，所以一定要讓學(xué)生自己學(xué)會(huì)判斷）由于待找數(shù)據(jù)表是從小到大排列的，而且區(qū)間中點(diǎn)位置上的數(shù)據(jù)Date(Mid)也知道，所以，通過(guò)Data(Mid)與x的比較，看一看，x比Data(Mid)大還是小，就可以判斷出x落在中間數(shù)Data(Mid)的左側(cè)還是右側(cè)，從而判斷出向左還是向右折半。師：那么，判斷語(yǔ)句如何寫(xiě)呢？生：if Data(Mid)High，停止折半查詢。0123456

7、78910LowHigh教學(xué)步驟四：對(duì)各種情況進(jìn)行歸納總結(jié)。（1）x與data(mid)的大小比較影響i,j的取值的規(guī)律：i的取值規(guī)律：if data(mid)x then high=mid-1用分支結(jié)構(gòu)實(shí)現(xiàn)。(2)繼續(xù)進(jìn)行重復(fù)查找的條件： lowhigh，用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)。教學(xué)步驟五：構(gòu)建對(duì)分查找的流程圖教學(xué)步驟六：對(duì)分查找算法的初步程序?qū)崿F(xiàn)。YYN開(kāi)始low1,high10計(jì)算middata(mid)=x?Nlowmid+1highmid-1N繼續(xù)查？輸出“未找到”Y輸出找到的信息結(jié)束lowhighmid=(low+high)2 data(mid)x?教師事先設(shè)計(jì)好Vb窗體，學(xué)生只需要在相應(yīng)

8、的程序體輸入代表算法思想的關(guān)鍵語(yǔ)句。附主要程序體：Private Sub Command2_Click()Dim x As Integer, mid As Integer, low As Integer, high As Integerx = Val(Text1.Text)low = 0: high = 10Do While low = highmid = (low + high) 2If data(mid) = x ThenText2.Text = 找到了，是第 & mid & 個(gè)Exit SubEnd IfIf data(mid) data(mid),那么low=mid+1 否則 high

9、=mid+15、重復(fù)上述的3,4步，直到low超出j(或者理解為low=high不成立，所以不能用for next,而要用do while語(yǔ)句）6、如果有找到x,那執(zhí)行第4步（1）步后應(yīng)該輸出找到的位置后退出程序，如果不退出，說(shuō)明x沒(méi)有找到，所以在相應(yīng)位置要輸出“找不到”。折半查找算法基本思想總結(jié)（2分鐘）對(duì)一有序數(shù)據(jù)表，首先從初始查找區(qū)間開(kāi)始，取出區(qū)間中點(diǎn)位置上的數(shù)據(jù)與要查詢數(shù)據(jù)進(jìn)行比較，若相等，則查找成功，并結(jié)束查詢；否則，將當(dāng)前查找區(qū)間縮小一半。在新的查詢區(qū)間內(nèi)，同樣取出區(qū)間中點(diǎn)位置上的數(shù)據(jù)與要查詢數(shù)據(jù)進(jìn)行比較，若相等，則查詢成功，并結(jié)束查詢，否則將新的查詢區(qū)間再次縮小一半。然后繼續(xù)采用相同的方法，直到查找數(shù)據(jù)成功或者查詢區(qū)間不能再折半（即查詢失敗）為止教學(xué)步驟七：評(píng)價(jià)。評(píng)價(jià)學(xué)生的程序?qū)崿F(xiàn)情況，并討論或?qū)嵺`問(wèn)題：如果是降序序列，該怎么樣改動(dòng)程序？如果序列元素不是10個(gè)，而是100個(gè)或更多呢？教學(xué)步驟八：總結(jié)提升。（1）由于對(duì)分查找過(guò)程中的每次比較都能使得搜索空間減半，對(duì)分查找將不會(huì)使用超過(guò)log2n次比較來(lái)找到目標(biāo)值。（2）提升對(duì)分查找算法的實(shí)際意義：同學(xué)們可能還沒(méi)有意識(shí)到二分查找是多么高效，那不妨設(shè)想一下在一個(gè)包含一百萬(wàn)個(gè)人名的電話簿中找一個(gè)名字，二分查找可以讓你不超過(guò)21次就能找到指定的名字。如果你能夠?qū)⑹澜缟纤械娜税凑招彰?/p>