張學(xué)欽，李英

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

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

中圖分類號：TP3? ? ? ? ? 文獻標(biāo)識碼：A

文章編號：1009-3044（2022）33-0177-04

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

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

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

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

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

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

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

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

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

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

單純文字描述算法思想不夠直觀，我們舉例如下：已知如下 11 個數(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 的折半查找過程，如下所示：

① [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 的折半查找過程，如下所示：

① [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折半查找算法的實現(xiàn)

算法描述：

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

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

3）運算過程：

a）計算中間值

mid=（low+high）/2；

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

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

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

根據(jù)以上算法的關(guān)鍵點分析，通過C 語言程序?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（"請輸入待查找的數(shù)："）;

scanf（"%d"，&data）;

low=0;

high=10;

while（low<=high）

{

mid=（low+high）/2;

if（data==array[mid]）

{

printf（"查找成功！%d在第%d個位置＼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折半查找算法實現(xiàn)過程中常見問題分析

在算法實現(xiàn)過程中，移動操作環(huán)節(jié)是關(guān)鍵；若 data<array[mid]，high 指向 mid 前一個元素，即high=mid-1；若data>array[mid]，low=mid+1;可是有些同學(xué)容易遺漏移動操作，編寫出如下的程序 [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（"請輸入待查找的數(shù)："）;

scanf（"%d"，&data）;

low=0;

high=10;

while（low<=high）

{

mid=（low+high）/2;

if（data==array[mid]）

{

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

break;

}

else if（data<array[mid]）

high=mid;

else

low=mid;

}

if（low>high）

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

return 0;

}

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

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

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

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

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

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

2.3教材分析

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

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

2.4學(xué)情分析

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

2.5教學(xué)策略

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

2.6教學(xué)方法

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

2.7教學(xué)過程設(shè)計

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

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

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

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

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

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

2.10.1 調(diào)查問卷和測試

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

2.10.2訪談

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

3總結(jié)與展望

3.1 總結(jié)

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

3.2 展望

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

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

參考文獻：

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

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

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

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

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

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

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