《折半查找算法及程序?qū)崿F(xiàn)教案【教資類別】》由會員分享，可在線閱讀，更多相關(guān)《折半查找算法及程序?qū)崿F(xiàn)教案【教資類別】（8頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

3、（2）教師引導(dǎo)：所以我不希望只有他一個人體驗這種方便，我們教室里還有一大幫人，其實這種什么不止用于查找電話鋪，還可以運用到實際生活中，教室里有這么多人，坦白說，按學校的老方法一個人一個人的數(shù)，對所有老師來說都及其費力，那我們想想，是不是數(shù)數(shù)2368，這樣好點對嗎？。不要小看這種想法，他其實是非常棒的，他能把解決問題的時間縮短一半，因此我們提出了這種算法 2、新課： 首先我們一起來看一看折半查詢算法中的“折半”的含義。 師：何為折半呢？ 生：減半；打一半的折扣。 例如，我手里拿著一根繩子，現(xiàn)在我們來進行折半試驗，首先拿住繩子的兩個端點， 然后從中點的位置進行對折，這樣繩子就縮短為原來

4、長度一半，然后將一半的繩子繼續(xù)執(zhí)行與剛才相同的操作，使得繩子的長度逐漸的縮短，直到繩子長度短得不能再進行折半了。 師：那什么時候就不能再折半了呢？ 生：即繩子的兩個端點合二為一為止。 折半查找算法的思想與繩子折半的過程基本相同。下面我們先通過圖示來看看折半查找算法究竟是什么？ 教學步驟二：分解對分查找算法（5分鐘） 假設(shè)一個從小到大排列的數(shù)據(jù)存放在一個數(shù)組中——Data(10)，而查找數(shù)據(jù)存放在變量x中。如圖1所示，橙色方框的代表的是查詢數(shù)據(jù)x，每個淺蘭色方框代表的是數(shù)組中的每個元素，框內(nèi)顯示的數(shù)據(jù)是每個數(shù)組元素對應(yīng)的下標（序號），整排的淺蘭色方框就可以看成整個數(shù)組，即待查數(shù)據(jù)表（數(shù)

5、組元素表）。 x 0 1 2 3 4 5 6 7 8 9 10 Low High 圖一 第一步：就像抓住繩子的兩端一樣，首先設(shè)立兩個標記Low、High分別來標識查詢區(qū)間的低端和高端，即數(shù)組元素的下標，如圖1所示。 師：對于初始查詢區(qū)間，它們是多少呢？ 生：Low=0 ， High=10 第二步：取區(qū)間的中點標記Mid，如圖2所示。 師：查詢區(qū)間的中點為多少？（這個地方，有的學生可能直接說出下標值，所以要提醒學生讓中點和兩個端點相聯(lián)系，即用端點表示中點） 生：Mid=(Low+High)/2 師：中點位置上的數(shù)據(jù)為什么？(提醒學生數(shù)據(jù)是放在數(shù)組Dat

6、a中的) 生：Data( Mid) 0 1 2 3 4 5 6 7 8 9 10 Mid Low High 第三步：判斷中點位置上的數(shù)據(jù)Data( Mid)與要查找數(shù)x是否相等，如何相等，則找到，并結(jié)束查找；如果不相等，就執(zhí)行第四步。 師：這個判斷語句如何寫呢？ 生：if Data( Mid)=x then print “x找到” 結(jié)束查找 end if 第四步：如果不相等，那么對查詢區(qū)間進行折半操作。 師：那如何折半——是從中點處向左側(cè)折半還是向右側(cè)折半？（這是整個折半查詢進行下去的關(guān)鍵所在，所以一定要讓學生自己學會判斷） 由于待

7、找數(shù)據(jù)表是從小到大排列的，而且區(qū)間中點位置上的數(shù)據(jù)Date(Mid)也知道，所以，通過Data(Mid)與x的比較，看一看，x比Data(Mid)大還是小，就可以判斷出x落在中間數(shù)Data(Mid)的左側(cè)還是右側(cè)，從而判斷出向左還是向右折半。 師：那么，判斷語句如何寫呢？ 生：if Data(Mid)

8、間內(nèi)的數(shù)據(jù)就不能再包含它，Low就得比Mid多1，即：Low=Mid+1。 0 1 2 3 4 5 6 7 8 9 10 Low High else 說明x比Data(Mid)小，所以就向左側(cè)折半，如圖4所示，觀察新區(qū)間，發(fā)現(xiàn)低端標記沒有變化，而高端標記變了，同樣道理，新查詢區(qū)間內(nèi)不能包含Mid對應(yīng)的數(shù)據(jù)，所有High比Mid小1，即：High=Mid–1 end if 第五步：重復(fù)執(zhí)行第二、三、四步驟。 師：如果一直沒有找到，那么什么時候不再進行折半查找呢？（提示學生想一想繩子折半的情況） 生：直至Low>High，停止折半查詢。0 1 2 3

9、 4 5 6 7 8 9 10 Low High 教學步驟四：對各種情況進行歸納總結(jié)。 （1）x與data(mid)的大小比較影響i,j的取值的規(guī)律： i的取值規(guī)律：if data(mid)x then high=mid-1 用分支結(jié)構(gòu)實現(xiàn)。 (2)繼續(xù)進行重復(fù)查找的條件： low≤high，用循環(huán)結(jié)構(gòu)實現(xiàn)。 教學步驟五：構(gòu)建對分查找的流程圖 教學步驟六：對分查找算法的初步程序?qū)崿F(xiàn)。 Y Y N 開始 low?1,high?10 計算mid data(mi

10、d)=x? N low?mid+1 high?mid-1 N 繼續(xù)查？ 輸出“未找到” Y 輸出找到的信息 結(jié)束 low≤high mid=(low+high)\2 data(mid)

11、) low = 0: high = 10 Do While low <= high mid = (low + high) \ 2 If data(mid) = x Then Text2.Text = "找到了，是第" & mid & "個" Exit Sub End If If data(mid) < x Then low = mid + 1 Else high = mid - 1 End If Loop Text2.Text = "找不到" End Sub 程序說明：1、獲得要查找的數(shù)據(jù)x的值 x = Val(Text1.Text) 2、i,j賦初值。

12、 low = 1: high = 10 3、求mid的值。mid = (low + high) \ 2 4、分三種情況，（1）如果x=data(mid),則如果 data(mid) = x 那么 Text2.Text = "找到了，在第" + Str(mid) + "個"。 （2）如果x>data(mid),那么low=mid+1 否則 high=mid+1 5、重復(fù)上述的3,4步，直到low超出j(或者理解為low<=high不成立，所以不能用for next,而要用do while語句） 6、如果有找到x,那執(zhí)行第4步（1）步后應(yīng)該輸出找到的位置后退出程序，如果不退出，說明x沒

13、有找到，所以在相應(yīng)位置要輸出“找不到”。 折半查找算法基本思想總結(jié)（2分鐘） 對一有序數(shù)據(jù)表，首先從初始查找區(qū)間開始，取出區(qū)間中點位置上的數(shù)據(jù)與要查詢數(shù)據(jù)進行比較，若相等，則查找成功，并結(jié)束查詢；否則，將當前查找區(qū)間縮小一半。在新的查詢區(qū)間內(nèi)，同樣取出區(qū)間中點位置上的數(shù)據(jù)與要查詢數(shù)據(jù)進行比較，若相等，則查詢成功，并結(jié)束查詢，否則將新的查詢區(qū)間再次縮小一半。然后繼續(xù)采用相同的方法，直到查找數(shù)據(jù)成功或者查詢區(qū)間不能再折半（即查詢失?。橹? 教學步驟七：評價。 評價學生的程序?qū)崿F(xiàn)情況，并討論或?qū)嵺`問題：如果是降序序列，該怎么樣改動程序？如果序列元素不是10個，而是100個或更多呢？ 教學步

14、驟八：總結(jié)提升。 （1）由于對分查找過程中的每次比較都能使得搜索空間減半，對分查找將不會使用超過log2n次比較來找到目標值。 （2）提升對分查找算法的實際意義：同學們可能還沒有意識到二分查找是多么高效，那不妨設(shè)想一下在一個包含一百萬個人名的電話簿中找一個名字，二分查找可以讓你不超過21次就能找到指定的名字。如果你能夠?qū)⑹澜缟纤械娜税凑招彰判颍敲茨憧梢栽?5步以內(nèi)找到任何人。 八、作業(yè)： 1、以下的三組元素序列能采用對分查找法來查找嗎？ (1) 19，33，35，53，56，67，78，99 (2)53，35，67，78，56，99，33，19 (3)99，67，56，45，33，10，9，1，0，-9 2、設(shè)計一個能用對分查找算法思想解決的實際問題。 8 教學d