張學(xué)欽，李英

摘要：折半查找算法是《數(shù)據(jù)結(jié)構(gòu)》課程的一個(gè)重要算法，講授時(shí)通過(guò)引入“猜價(jià)格”游戲以及形象、直觀的動(dòng)畫演示來(lái)調(diào)動(dòng)學(xué)生學(xué)習(xí)的興趣點(diǎn)和積極性，營(yíng)造良好的學(xué)習(xí)氛圍。對(duì)學(xué)生學(xué)習(xí)滿意度的調(diào)查結(jié)果表明，游戲融入折半查找算法教學(xué)具有事半功倍的效果。

關(guān)鍵詞：折半查找算法；游戲；動(dòng)畫

中圖分類號(hào)：TP3? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）33-0177-04

隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的不斷擴(kuò)大，人們對(duì)數(shù)據(jù)結(jié)構(gòu)的重視程度空前高漲?！稊?shù)據(jù)結(jié)構(gòu)》課程中的排序、查找算法是經(jīng)典的、重點(diǎn)的算法。然而非?？菰?，教師難講，學(xué)生課程也缺乏興趣[1]。如果將教學(xué)與游戲巧妙地結(jié)合，對(duì)折半查找算法的教學(xué)將會(huì)是一個(gè)不錯(cuò)的教學(xué)思路。

1游戲?qū)φ郯氩檎宜惴ń虒W(xué)的適用性分析

1.1 游戲融入教學(xué)可以模擬實(shí)際的場(chǎng)景，使學(xué)生對(duì)知識(shí)的理解更深入

通過(guò)游戲可以將復(fù)雜、枯燥的知識(shí)通過(guò)形象的模擬來(lái)進(jìn)行展示，使學(xué)生對(duì)折半查找算法的印象更深刻、理解更深入，進(jìn)而為后續(xù)的算法實(shí)現(xiàn)環(huán)節(jié)打下良好的基礎(chǔ)。

1.2 開(kāi)拓學(xué)生的創(chuàng)新思維

在計(jì)算機(jī)發(fā)展日新月異的今天，為了滿足 IT 企業(yè)的需求，適應(yīng)市場(chǎng)需要，計(jì)算機(jī)專業(yè)必須開(kāi)拓學(xué)生的創(chuàng)新思維。游戲的引入，可以使整個(gè)教學(xué)過(guò)程趣味性十足，學(xué)生發(fā)揮的想象力可以得到充分地發(fā)揮，進(jìn)而可以開(kāi)拓學(xué)生的創(chuàng)新思維[2]。

2折半查找算法的教學(xué)設(shè)計(jì)

2.1折半查找算法的基本思想

對(duì)已按關(guān)鍵字排序的序列，首先用待查找數(shù)據(jù)與數(shù)列中間元素比較，如果相等，則查找成功；如果不相等，則根據(jù)比較結(jié)果，來(lái)確定后續(xù)查找在哪半邊進(jìn)行，以此類推，直到查找成功，或者找不到待查找數(shù)據(jù)為止[3]。

2.1.1折半查找算法的基本思路

單純文字描述算法思想不夠直觀，我們舉例如下：已知如下 11 個(gè)數(shù)據(jù)元素的數(shù)組（6， 13， 19， 23， 37， 58， 64， 75， 82， 88， 92），現(xiàn)要查找關(guān)鍵字data為 23 和 85的元素。Low：查找區(qū)間的下界， high：查找區(qū)間的上界，mid：查找區(qū)間的中間位置，mid=（low+high）/2。

（1） k=23 的折半查找過(guò)程，如下所示：

① [1，11]，mid=6，23<58， high=mid-1;

② [1，5]，mid=3，23>19，low=mid+1;

③ [4，5]， mid=4，23=23，查找成功;

（2） k=85 的折半查找過(guò)程，如下所示：

① [1，11]，mid=6，58<85，low=mid+1;

② [7，11]，mid=9，82<85，low=mid+1;

③ [10，11]，mid=10，88>85，high=mid-1;

④ [10，9]low>high，查找失??；

2.1.2折半查找算法的實(shí)現(xiàn)

算法描述：

1）輸入：待查找關(guān)鍵字data；

2）輸出：若匹配成功，輸出滿足條件的數(shù)據(jù)元素下標(biāo)；否則；輸出“查找失敗”；

3）運(yùn)算過(guò)程：

a）計(jì)算中間值

mid=（low+high）/2；

b）移動(dòng)操作：若 data<array[mid]，high 指向 mid 前一個(gè)元素，即high=mid-1；若data>array[mid]，low=mid+1；

c）循環(huán)條件：low<=high；

d）結(jié)束條件：data=arrray[mid]或low>high；

根據(jù)以上算法的關(guān)鍵點(diǎn)分析，通過(guò)C 語(yǔ)言程序?qū)崿F(xiàn)折半查找算法：

#include<stdio.h>

int main（）

{

int array[11]={5，13，19，21，37，56，64，75，80，88，92}，low，high，mid，data;

printf（"請(qǐng)輸入待查找的數(shù)："）;

scanf（"%d"，&data）;

low=0;

high=10;

while（low<=high）

{

mid=（low+high）/2;

if（data==array[mid]）

{

printf（"查找成功！%d在第%d個(gè)位置＼n"，data，mid+1）;

break;

}

else if（data<array[mid]）

high=mid-1;

else

low=mid+1;

}

if（low>high）

printf（"查找失?。。躰"）;

return 0;

}

2.1.3折半查找算法實(shí)現(xiàn)過(guò)程中常見(jiàn)問(wèn)題分析

在算法實(shí)現(xiàn)過(guò)程中，移動(dòng)操作環(huán)節(jié)是關(guān)鍵；若 data<array[mid]，high 指向 mid 前一個(gè)元素，即high=mid-1；若data>array[mid]，low=mid+1;可是有些同學(xué)容易遺漏移動(dòng)操作，編寫出如下的程序 [5]：

#include<stdio.h>

int main（）

{

int array[11]={5，13，19，21，37，56，64，75，80，88，92}，low，high，mid，data;

printf（"請(qǐng)輸入待查找的數(shù)："）;

scanf（"%d"，&data）;

low=0;

high=10;

while（low<=high）

{

mid=（low+high）/2;

if（data==array[mid]）

{

printf（"查找成功！%d在第%d個(gè)位置＼n"，data，mid+1）;

break;

}

else if（data<array[mid]）

high=mid;

else

low=mid;

}

if（low>high）

printf（"查找失?。。躰"）;

return 0;

}

若按上面程序執(zhí)行，會(huì)產(chǎn)生兩個(gè)問(wèn)題：一是當(dāng)待查找關(guān)鍵字 data 不存在時(shí)，low<=high 永遠(yuǎn)成立，查找過(guò)程將永不停歇；其二是若查找關(guān)鍵字 data=6或者data=92，查找過(guò)程則陷入死循環(huán)，又無(wú)法找到正確的位置，這就需要教師們?cè)诮虒W(xué)過(guò)程中反復(fù)強(qiáng)調(diào)移動(dòng)操作的重要性。

2.2 教學(xué)目標(biāo)

知識(shí)目標(biāo)：掌握可以實(shí)現(xiàn)折半查找的兩個(gè)前提以及折半查找的基本思想；

能力目標(biāo)：具備一定的邏輯思維能力和從具體問(wèn)題中提煉出算法的能力；

操作性目標(biāo)： 能通過(guò)計(jì)算機(jī)語(yǔ)言編寫程序?qū)崿F(xiàn)折半查找算法；

情感目標(biāo)： 提升學(xué)生參與意識(shí)，培養(yǎng)學(xué)生自主探索問(wèn)題的能力，讓學(xué)生在自主探究的過(guò)程中深刻感受算法思想在解決實(shí)際問(wèn)題時(shí)的重要性和魅力，以激發(fā)學(xué)生的學(xué)習(xí)熱情。

2.3教材分析

教學(xué)重點(diǎn)：折半查找算法的基本思想；

教學(xué)難點(diǎn)：由折半查找算法思想到程序代碼的轉(zhuǎn)換。

2.4學(xué)情分析

學(xué)習(xí)對(duì)象是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院大一新生，同學(xué)們對(duì)數(shù)組的相關(guān)知識(shí)和順序查找算法已經(jīng)有一定的認(rèn)識(shí)。但由于剛接觸編程，對(duì)編程積極性不夠高，基礎(chǔ)相對(duì)欠缺，加上折半查找算法邏輯性比較強(qiáng)。所以在教學(xué)過(guò)程中應(yīng)盡量想辦法調(diào)動(dòng)學(xué)生學(xué)習(xí)的興趣點(diǎn)和積極性。

2.5教學(xué)策略

首先，寓教于樂(lè)，通過(guò)精心設(shè)計(jì)的“猜價(jià)格”游戲來(lái)調(diào)動(dòng)學(xué)生的學(xué)習(xí)積極性和興趣點(diǎn)，啟發(fā)學(xué)生去探索游戲背后的科學(xué)原理；另外，通過(guò)算法動(dòng)畫的展示，將游戲環(huán)節(jié)中的猜價(jià)格方法進(jìn)一步提升到算法原理中，可以激發(fā)學(xué)生學(xué)習(xí)編程的熱情，也可以為后續(xù)的算法實(shí)現(xiàn)環(huán)節(jié)打下良好的基礎(chǔ)。

2.6教學(xué)方法

本課采用游戲體驗(yàn)法、動(dòng)畫直觀演示法和啟發(fā)式教學(xué)法三種方法相結(jié)合的方式來(lái)完成。

2.7教學(xué)過(guò)程設(shè)計(jì)

首先，通過(guò)對(duì)前一節(jié)順序查找內(nèi)容的回顧，總結(jié)出順序查找的優(yōu)缺點(diǎn)；然后，通過(guò)一個(gè)“猜價(jià)格”游戲暖場(chǎng)，引導(dǎo)學(xué)生去探索游戲背后的科學(xué)原理，進(jìn)而導(dǎo)入新課；接下來(lái)結(jié)合一個(gè)具體的案例，配合動(dòng)畫詳細(xì)講解折半查找的基本原理。然后，提煉出折半查找算法，繪制出折半查找算法的流程圖，并設(shè)計(jì)出動(dòng)畫效果，使流程圖當(dāng)中的每一步都有與之對(duì)應(yīng)的代碼同步出現(xiàn)。相信，通過(guò)這種方法來(lái)完成算法實(shí)現(xiàn)這一環(huán)節(jié)的講解，可以讓同學(xué)們更清晰、更透徹地理解算法代碼，并且可以激發(fā)學(xué)生對(duì)編程的熱情和信心。隨后，對(duì)本節(jié)課的內(nèi)容進(jìn)行總結(jié)，提醒學(xué)生本節(jié)課應(yīng)該注意的關(guān)鍵點(diǎn)。再通過(guò)一道思考題，讓學(xué)生更深刻地去感受折半查找在實(shí)際生活的用途和高效性，最后，布置作業(yè)讓學(xué)生對(duì)本節(jié)課的知識(shí)進(jìn)行鞏固。

2.8多媒體課件設(shè)計(jì)的重要性

老師們進(jìn)行教學(xué)設(shè)計(jì)時(shí)，往往都會(huì)對(duì)知識(shí)導(dǎo)入、教學(xué)目標(biāo)（包含知識(shí)目標(biāo)、能力目標(biāo)、情感目標(biāo)、操作目標(biāo)等）、教學(xué)重點(diǎn)與難點(diǎn)、教學(xué)策略等方面耗費(fèi)大量的時(shí)間與精力，卻忽略多媒體課件的設(shè)計(jì)，然而課件的色彩搭配、動(dòng)畫效果、視頻等往往會(huì)給學(xué)生帶來(lái)一場(chǎng)非常震撼的視覺(jué)盛宴，進(jìn)而吸引學(xué)生的注意力，使教學(xué)效果事半功倍。

2.9 《折半查找算法》教學(xué)設(shè)計(jì)的依據(jù)

由于學(xué)生的基礎(chǔ)不同，理解問(wèn)題的能力也參差不齊，《數(shù)據(jù)結(jié)構(gòu)》課程內(nèi)容又非?？菰?，要想提高學(xué)生學(xué)習(xí)的積極性與主動(dòng)性，就必須改變過(guò)去以教師為中心“滿堂灌”的教學(xué)模式。針對(duì)《數(shù)據(jù)結(jié)構(gòu)》課程的特點(diǎn)，考慮到學(xué)習(xí)對(duì)象是大一新生，缺乏足夠的編程熱情、好奇心強(qiáng)、活潑、愛(ài)玩等實(shí)際情況，結(jié)合折半查找算法的教學(xué)目標(biāo)，決定采用游戲體驗(yàn)法、動(dòng)畫直觀演示法和啟發(fā)式教學(xué)法三種方法相結(jié)合的方式來(lái)完成折半查找算法的教學(xué)。首先，通過(guò)游戲暖場(chǎng)可以讓學(xué)生積極參與到課堂中來(lái)，以最大限度地激發(fā)學(xué)生的學(xué)習(xí)熱情。接著，運(yùn)用啟發(fā)式教學(xué)引入本節(jié)課的主題——折半查找。然后，結(jié)合一個(gè)具體的實(shí)例配合形象、直觀的動(dòng)畫展示出折半查找算法的基本思想及其實(shí)現(xiàn)的詳細(xì)過(guò)程，將游戲環(huán)節(jié)中的“猜價(jià)格”方法進(jìn)一步融合到折半查找算法原理中，一定可以激發(fā)學(xué)生學(xué)習(xí)的熱情和信心。

2.10 教學(xué)效果調(diào)查

2.10.1 調(diào)查問(wèn)卷和測(cè)試

為了調(diào)查此教學(xué)設(shè)計(jì)的效果，老師通過(guò)在問(wèn)卷星上發(fā)布問(wèn)卷，讓學(xué)生填寫自己對(duì)這一節(jié)課的感受和各項(xiàng)教學(xué)目標(biāo)達(dá)成度，并對(duì)老師的教學(xué)方法提出相應(yīng)的意見(jiàn)和建議。 通過(guò)問(wèn)卷星平臺(tái)反饋結(jié)果可以看出，90% 以上的學(xué)生認(rèn)為本次課堂注意力高度集中，學(xué)習(xí)興趣濃厚，對(duì)用折半查找算法實(shí)現(xiàn)課后作業(yè)非常有信心。隨后，對(duì)學(xué)生進(jìn)行折半查找算法知識(shí)的測(cè)試。結(jié)果證實(shí)， 85%以上的學(xué)生成績(jī)達(dá)到優(yōu)秀。調(diào)查結(jié)果表明，游戲融入本節(jié)課的教學(xué)，收到了良好的教學(xué)效果。

2.10.2訪談

問(wèn)卷調(diào)查和測(cè)試完成后，選取成績(jī)相對(duì)較好和成績(jī)相對(duì)較差的學(xué)生進(jìn)行訪談，以更好地改進(jìn)教學(xué)。調(diào)查結(jié)果出乎意料，好多同學(xué)把沒(méi)布置的課后習(xí)題也編程實(shí)現(xiàn)了，還有相當(dāng)一部分學(xué)生已經(jīng)開(kāi)始迫不及待地學(xué)習(xí)其他查找、排序算法。充分說(shuō)明引入游戲來(lái)講授折半查找算法能充分調(diào)動(dòng)學(xué)生的學(xué)習(xí)興趣和編程熱情，能提高學(xué)生的學(xué)習(xí)主動(dòng)性。

3總結(jié)與展望

3.1 總結(jié)

游戲教學(xué)要求任課教師要時(shí)刻牢記游戲不以玩樂(lè)為目的，游戲規(guī)則的設(shè)計(jì)要緊緊圍繞教學(xué)目標(biāo)和內(nèi)容，規(guī)則要能精準(zhǔn)地傳達(dá)給學(xué)生。教學(xué)設(shè)計(jì)往往都會(huì)包含知識(shí)回顧與導(dǎo)入、教學(xué)目標(biāo)（包含知識(shí)目標(biāo)、能力目標(biāo)、情感目標(biāo)、操作目標(biāo)等）、教學(xué)重點(diǎn)與難點(diǎn)、教學(xué)策略、板書、教態(tài)、課件、作業(yè)等方面[1]。 優(yōu)秀的教學(xué)設(shè)計(jì)可以讓學(xué)生體會(huì)到學(xué)習(xí)的快樂(lè)，能激發(fā)學(xué)生學(xué)習(xí)的熱情，進(jìn)而能夠取得良好的教學(xué)效果。

3.2 展望

本次教學(xué)設(shè)計(jì)僅選擇了《數(shù)據(jù)結(jié)構(gòu)》課程中的折半查找算法，并且僅僅是針對(duì)計(jì)算機(jī)軟件工程專業(yè)大一新生進(jìn)行實(shí)驗(yàn)教學(xué)，課程內(nèi)容和學(xué)習(xí)對(duì)象都不夠全面。以后的教學(xué)中，力爭(zhēng)早日讓游戲教學(xué)貫穿到《數(shù)據(jù)結(jié)構(gòu)》課程各個(gè)章節(jié)中，并且盡可能多地在其他學(xué)習(xí)對(duì)象中開(kāi)展，讓研究結(jié)果更有普遍性意義。

在以后的教學(xué)設(shè)計(jì)中，還要盡可能多地融合課程思政元素，在培養(yǎng)學(xué)生專業(yè)能力的同時(shí)，關(guān)注學(xué)生身心健康發(fā)展，實(shí)現(xiàn)育人的理想效果。另外，還要采用線上線下混合式教學(xué)模式，讓學(xué)生真正變?yōu)閷W(xué)習(xí)的主體，融合傳統(tǒng)課堂教學(xué)與在線學(xué)習(xí)的優(yōu)勢(shì)，以獲得最佳的教學(xué)效果和學(xué)習(xí)效果[6]。

參考文獻(xiàn)：

[1] 王曉燕，李亞.游戲在教學(xué)中的應(yīng)用——《停止等待協(xié)議》的教學(xué)設(shè)計(jì)[J].南陽(yáng)師范學(xué)院學(xué)報(bào)，2015，14（12）：69-72.

[2] 李明，馬平.游戲設(shè)計(jì)在人機(jī)工程學(xué)課堂教學(xué)中的應(yīng)用[J].黑龍江科技信息，2012（29）：172，69.

[3] 嚴(yán)蔚敏，李冬梅，吳偉民.數(shù)據(jù)結(jié)構(gòu)：C語(yǔ)言版[M].2版.北京：人民郵電出版社，2022.

[4] 何麗莉，白洪濤.折半查找算法實(shí)例教學(xué)及問(wèn)題分析[J].教育現(xiàn)代化，2016，3（16）：68-70.

[5] 呂國(guó)光，張燕.關(guān)于游戲教學(xué)的若干研究[J].韶關(guān)學(xué)院學(xué)報(bào)，2011，32（3）：130-134.

[6] 胡鈺，耿植林，普運(yùn)偉，等.以問(wèn)題為導(dǎo)引的線上線下混合式教學(xué)模式探究[J].計(jì)算機(jī)教育，2022（2）：73-78.

【通聯(lián)編輯：朱寶貴】