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