- 相關(guān)推薦
如何在游戲中學(xué)習(xí)二分查找的算法思想
摘 要：本文的主要內(nèi)容包括：二分查找的算法思想；講解中不易理解、掌握的原因；通過游戲理解算法。通過游戲中學(xué)習(xí)二分查找的算法思想教學(xué)過程，讓學(xué)生參與其中，體驗過程，分析原因，得出結(jié)論。
關(guān)鍵詞：二分查找 游戲理解算法 游戲
一、二分查找的算法思想
在已經(jīng)排好序的數(shù)列中，首先找到中間的記錄，這時可能會出現(xiàn)三種情況之一（假設(shè)按升序排列）。
1)該記錄對應(yīng)字段的值小于查找關(guān)鍵字，此時應(yīng)在前半部分記錄中繼續(xù)查找。
2)該記錄對應(yīng)字段的值大于查找關(guān)鍵字，此時應(yīng)在后半部分記錄中繼續(xù)查找。
3)該記錄對應(yīng)字段的值等于查找關(guān)鍵字，那么就已找到了查找目標(biāo)，查找結(jié)束。
如果出現(xiàn)前兩種情況，則繼續(xù)在前半部分或后半部分內(nèi)進(jìn)行對半查找，直到出現(xiàn)第三種情況為止。如果沿指定方向測試完成所有記錄時仍未出現(xiàn)第三種情況，則表示未找到查找目標(biāo)，查找也結(jié)束。
二、講解中不易理解、掌握的原因
單看這一串算法思想的解釋有些學(xué)生便有些沒有耐心了，更不用說去掌握應(yīng)用了。或者有些人生硬地記住了這些原理卻沒有真正地理解，寫程序時也會漏洞百出的。只有讓學(xué)親身體會了查找的過程，才能理解算法思想，才能想到編程時的條件設(shè)置及注意點。從而真正達(dá)到理解、應(yīng)用的最終目標(biāo)。
三、通過游戲理解算法
游戲過程如下：
第一步：把10名同學(xué)按身高從低到高排成一列，并依次排號為1到10號。并另找一位學(xué)生，稱為X，找一找10人中有無與X同樣身高的。若有則輸出他的號碼。
第二步：讓其它學(xué)生自己想方法去解決這個問題。討論之后學(xué)生得出了這樣一個結(jié)論：把X與這一列中1號到10號的每個人依次比較過去，便有結(jié)論出來了。教師總結(jié)：這種方法叫順序比較法，可以達(dá)到目的，但是程序的復(fù)雜度比較高，比如說有1000人或者有10000人或者更多的話，這種方法就體現(xiàn)不出優(yōu)越性了。如何更快更簡便地得到結(jié)論呢？這時教師引入二分法的思想：從10個中找出中間位置的一位同學(xué)與X 進(jìn)行比較。有三種結(jié)論：1、若相等則表示找到，停止程序。2、若比X高，那么與X等高的得在中間往后的這部分人中找。3、若比X低，那么與X等高的得在中間往前的這部分人中找。在2或3 中又重復(fù)同一過程。
第三步：游戲分進(jìn)行3次
第一次游戲選擇一個學(xué)生X，其身高與九號學(xué)生剛好相同（假設(shè)不知道）游戲過程如下：
1號 2號 3號 4號 5號 6號 7號 8號 9號 10號
隊首：1號
隊尾：10號
找到中位置MID=（1+10）2=5號
因為X>5號所以只能舍棄前半部分，在后半部分找，于是只剩下
6號 7號 8號 9號 10號
隊首：6號
隊尾：10號
找到中間位置：
MID=（6+10）2=8 號
因為X>8號所以只能舍棄前半部分,在后半部分找,于是只剩下
9號 10號
隊首：9號
隊尾：10號
找到中間位置：MID=（9+10）2=9號
因為X=9號,找到。停止尋找。
在這輪游戲中可以發(fā)現(xiàn)從第二次開始每次的隊首都是前一次求得的中間值加1得到的。也可理解為從中間一項往后開始下一次尋找。
第二次游戲：假設(shè)X的身高小于所有隊列中的同學(xué)
1號 2號 3號 4號 5號 6號 7號 8號 9號 10號
隊首：1號
隊尾：10號
找到中位置MID=（1+10）2=5號
因為X<5號所以要舍棄中間往后的部分,在前半部分找,于是剩下:
1號 2號 3號 4號
隊首：1號
隊尾：4號
找到中位置MID=（1+4）2=2號
因為X<2號所以要舍棄中間往后的部分,在前半部分找,于是剩下:
1號
隊首：1號
隊尾：1號
找到中間位置：MID=（1+1）2=1號
因為X<1號,所以要舍棄中間往后的部分,在前半部分找,而前面已無學(xué)生了,也就是說在隊列中找不到與X相同身高的學(xué)生.。若按照前面的方法，可得如下的結(jié)論：
隊首：1號
隊尾：—1號
因為隊列中最小是1號，最大是10號，不存在—1，可見出列了，也可知隊列中沒有與X 身高相同的同學(xué)。
由上可見，從第二次開始，每次隊尾的值都是前一次的中間值減1得到的，而當(dāng)隊尾小于隊首時即可知X不在隊列中。
第三次游戲：假設(shè)X比隊列中的任何一位同學(xué)都要高。
1號 2號 3號 4號 5號 6號 7號 8號 9號 10號
隊首：1號
隊尾：10號
找到中位置MID=（1+10）2=5號
因為X>5號所以要舍棄中間往前的部分,在后半部分找,于是剩下:
6號 7號 8號 9號 10號
隊首：6號
隊尾：10號
找到中位置MID=（6+10）2=8號
因為X>8號所以要舍棄中間往前的部分,在后半部分找,于是剩下:
9號 10號
隊首：9號
隊尾：10號
找到中位置MID=（9+10）2=9號
因為X>9號所以要舍棄中間往前的部分,在后半部分找,于是剩下:
10號
隊首：10號
隊尾：10號
找到中位置MID=（10+10）2=10號
因為X>10號所以要舍棄中間往前的部分,在后半部分找,而后面已無學(xué)生了,也就是說在隊列中找不到與X相同身高的學(xué)生.。若按照前面的方法，可得如下的結(jié)論：
隊首：11號
隊尾： 10號
因為隊列中最小是1號，最大是10號，不存在11號，可見出列了，也可知隊列中沒有與X 身高相同的同學(xué)。
由上可見，從第二次開始，每次隊首的值都是前一次的中間值加1得到的，而當(dāng)隊尾小于隊首時即可知X不在隊列中。
游戲結(jié)束,引導(dǎo)學(xué)生總結(jié):在三次游戲中,反復(fù)做的事情是什么?即：（1）如何找到中間的一位同學(xué)（2）找到后與X進(jìn)行比較。有三種結(jié)果：相等，大于，小于。如何相應(yīng)地去處理。（3）找到何時停止。即可以尋找的條件。通過第二、第三個游戲可以得出結(jié)論：當(dāng)表示頭部的號大于表示尾部的號時，停止尋找，得出找不到的結(jié)論。也就是說當(dāng)頭部號小于尾部號時可以去尋找。
由上面的分析可以得到以下的程序：
CLS
M=1 ：N=10 （由M，N來代表頭部及尾部的號）
DIM A(10) (由10個數(shù)組元素來存放1號到10號的身高)
INPUT X
F=0
DO WHILE M<=N AND F=0
MID = （M+N）2
I F X= A(MID) THEN F=1 ：EXIT DO
IF X<A(MID) THEN N = MID —1
IF X>A（MID） THEN M=MID +1
LOOP
IF F=1 THEN PRINT MID ELSE PRINT “沒找到”
END
四、總結(jié)
通過這樣的教學(xué)過程，讓學(xué)生參與其中，體驗過程，分析原因，得出結(jié)論。這樣的過程有利于學(xué)生深刻體會算法思想，理解程算法思想，從而能觸類旁通，舉一反三。只有學(xué)習(xí)過程不再枯燥無味，才能激發(fā)學(xué)生學(xué)習(xí)的主動性與積極性。才能達(dá)到事半功倍的效果。
【如何在游戲中學(xué)習(xí)二分查找的算法思想】相關(guān)文章：
如何在學(xué)習(xí)中獲得快樂在快樂中獲取知識03-25
如何在教學(xué)中培養(yǎng)和激發(fā)學(xué)生的學(xué)習(xí)興趣11-20
軟件安全中混合加密算法10-05
如何在面試中察言觀色10-09
如何在簡歷中彌補弱項10-01
如何在簡歷中彌補弱點10-09
如何在簡歷中彌補弱項10-26