“并查集算法”微課教學(xué)設(shè)計(jì)

王榮芝 于世華

摘要：微課是目前教育教學(xué)改革的一種新型授課方式，具有短、精、活、趣等特征，對(duì)促進(jìn)教師成長(zhǎng)、提高學(xué)生學(xué)業(yè)水平具有重要作用。文章以ACM/ICPC競(jìng)賽培訓(xùn)中“并查集算法”教學(xué)為例，提供一套微課教學(xué)設(shè)計(jì)方案，強(qiáng)調(diào)情境設(shè)置激發(fā)學(xué)習(xí)興趣、設(shè)疑討論引發(fā)思維風(fēng)暴、任務(wù)驅(qū)動(dòng)增強(qiáng)體驗(yàn)成就，幫助學(xué)生從基本知識(shí)到能力培養(yǎng)的快速過(guò)渡，為其他微課教學(xué)提供借鑒。

關(guān)鍵詞：微課；教學(xué)設(shè)計(jì)；ACM/ICPC；算法；并查集

1 背景

微課（micro-iecture，又譯為“微課程”），一般以講授單一知識(shí)點(diǎn)為目標(biāo)，如專門(mén)講授一堂常規(guī)課中的重點(diǎn)、難點(diǎn)或疑點(diǎn)，通常由簡(jiǎn)短的教學(xué)視頻和配套的課程資源組成。微課具有短小精悍、主題突出、靈活多樣、味趣性強(qiáng)、適合自主學(xué)習(xí)等特點(diǎn)。一節(jié)微型課用時(shí)10～25分鐘，要求切入主題快，整體教學(xué)過(guò)程節(jié)奏快而有序，師生互動(dòng)收放自然，課程小結(jié)畫(huà)龍點(diǎn)睛，延伸課堂知識(shí)、研究微課有助于教師在真實(shí)、具體、典型案例化的教與學(xué)情景中實(shí)現(xiàn)教學(xué)觀念、技能、風(fēng)格的模仿、遷移和提升，從而迅速增強(qiáng)教師的課堂教學(xué)水平、促進(jìn)教師的專業(yè)成長(zhǎng)。與此同時(shí)，精心設(shè)計(jì)和實(shí)施的課堂教學(xué)、有針對(duì)性和趣味性的案例、創(chuàng)新性的教學(xué)方法、良好的師生互動(dòng)及完備的教學(xué)資源更有利于激發(fā)學(xué)生的學(xué)習(xí)興趣，提高學(xué)生學(xué)業(yè)水平。就學(xué)校教育而言，微課不僅成為教師和學(xué)生的重要教育資源，也構(gòu)成了學(xué)校教育教學(xué)模式改革的基礎(chǔ)。

2 前期分析

2.1 教學(xué)內(nèi)容分析

ACM/ICPC（國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽）足目前最具影響力和規(guī)模最大的國(guó)際頂級(jí)賽事，足大學(xué)計(jì)算機(jī)教育成果的直接體現(xiàn)，各高校普遍將其作為大學(xué)生程序設(shè)計(jì)能力的體現(xiàn)ACM/ICPC涉及知識(shí)面廣，涵蓋數(shù)學(xué)建模、計(jì)算機(jī)、英語(yǔ)等學(xué)科，對(duì)學(xué)生自主學(xué)習(xí)能力、創(chuàng)新能力、團(tuán)隊(duì)精神以及在競(jìng)爭(zhēng)壓力下進(jìn)行開(kāi)發(fā)活動(dòng)能力的培養(yǎng)有著積極的意義。ACM/ICPC競(jìng)賽培訓(xùn)主要針對(duì)ACM/ICPC參賽隊(duì)員和愛(ài)好者進(jìn)行競(jìng)賽知識(shí)培訓(xùn)，系統(tǒng)介紹計(jì)算機(jī)各類常用算法。培訓(xùn)根據(jù)算法類別以專題方式進(jìn)行，每個(gè)專題介紹該類算法的基本理論、算法實(shí)現(xiàn)及應(yīng)用案例。

并查集是ACM程序設(shè)計(jì)培訓(xùn)中的一個(gè)專題算法。所謂并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合S={Sl，S2，…，Sn}，每個(gè)集合Si都有一個(gè)特殊元素set[Si]，稱為集合的代表：并查集支持3種操作：①init（x），集合初始化，把元素XI加到集合Si中，每個(gè)集合Si只有一個(gè)元素Xl，并且元素Xl就是集合Si的代表元素；②find（x），查找xi所在集合Si的代表set[Si]；③merge（x，y），合并，把x和y所在的兩個(gè)不同集合合并二相對(duì)其他數(shù)據(jù)結(jié)構(gòu)，并查集編程難度很小，也很靈活，適當(dāng)?shù)膄ind函數(shù)與merge函數(shù)便可以解決很多問(wèn)題，應(yīng)用很廣。并查集算法包括基本算法和多種優(yōu)化算法。在內(nèi)容安排中設(shè)計(jì)ACM生動(dòng)案例引H{并查集的解題思路，使學(xué)生形成初步認(rèn)識(shí)；進(jìn)一步介紹并查集算法及實(shí)現(xiàn)方式，讓學(xué)生體會(huì)算法的精妙之處，對(duì)算法形成認(rèn)同；在此基礎(chǔ)上，使用該算法解決相關(guān)題目使學(xué)生進(jìn)一步鞏固和應(yīng)用算法。

2.2 學(xué)習(xí)者分析

參加ACM競(jìng)賽培訓(xùn)的學(xué)員前期學(xué)過(guò)C/C++及數(shù)據(jù)結(jié)構(gòu)課程，掌握線性表、樹(shù)、圖等結(jié)構(gòu)和基本算法；了解ACM/ICPC競(jìng)賽模式，對(duì)競(jìng)賽有興趣，有一定的自主學(xué)習(xí)和探究能力，能夠解決一般性題目，但不具備系統(tǒng)解題技巧。

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

3.1 本節(jié)（課）教學(xué)目標(biāo)

（1）知識(shí)和技能：理解并查集算法的基本思想，掌握3種基本操作的算法實(shí)現(xiàn)，學(xué)會(huì)使用并查集方法解決實(shí)際問(wèn)題。

（2）過(guò)程和方法：感受并查集算法的解題思路，體會(huì)并查集的解題思路精妙之處。

（3）情感態(tài)度和價(jià)值觀：激發(fā)對(duì)ACM程序設(shè)計(jì)的興趣，學(xué)會(huì)鉆研與思考。

3.2 教學(xué)重點(diǎn)及難點(diǎn)

（1）教學(xué)重點(diǎn)：并查集的基本思想和算法實(shí)現(xiàn)。

突出措施是通過(guò)多媒體展示ACM案例；通過(guò)對(duì)比傳統(tǒng)無(wú)向圖解決方式存在的缺陷，引出并查集解題思路和具體實(shí)現(xiàn)；使學(xué)生體會(huì)算法的簡(jiǎn)單和靈活。

（2）教學(xué)難點(diǎn)：并查集算法的解題應(yīng)用。

突破措施是總結(jié)算法特點(diǎn)和應(yīng)用范圍，給出基本代碼；除課堂案例外，加入兩個(gè)練習(xí)及多個(gè)課下練習(xí)，讓學(xué)生進(jìn)一步應(yīng)用和鞏固。

4 教學(xué)資源、方法及策略

4.1 教學(xué)資源

教學(xué)環(huán)境為多媒體教室，教學(xué)課件采用PPT幻燈片；通過(guò)生動(dòng)武俠形象為案例“江湖朋友圈問(wèn)題”創(chuàng)設(shè)情境，如圖1所示；解題過(guò)程采用動(dòng)畫(huà)方式，分步演示思路和步驟；程序編寫(xiě)及測(cè)試應(yīng)用DEV C++軟件；課上及課下練習(xí)應(yīng)用本?！癆CM在線自動(dòng)評(píng)測(cè)試系統(tǒng)”，課程知識(shí)擴(kuò)展應(yīng)用網(wǎng)絡(luò)課程教學(xué)平臺(tái)。

4.2 教學(xué)方法及策略

（1）情境設(shè)置法的教學(xué)策略：利用江湖和武俠人物圖片向?qū)W生描述“江湖朋友圈問(wèn)題”創(chuàng)設(shè)教學(xué)情境，引出問(wèn)題討論。

（2）問(wèn)題討論法的教學(xué)策略：引導(dǎo)學(xué)生思考解決“江湖朋友圈問(wèn)題”的方法，激發(fā)學(xué)生的思考，引發(fā)學(xué)生的思維風(fēng)暴，讓課堂教學(xué)目的更加明確，組織更加高效。

（3）任務(wù)驅(qū)動(dòng)法的教學(xué)策略：將課上分析案例及課下作業(yè)布置為ACM提交任務(wù)，讓學(xué)生以完成任務(wù)為目標(biāo)，激勵(lì)學(xué)生應(yīng)用所學(xué)知識(shí)。，

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

教學(xué)過(guò)程主要包括以下4個(gè)環(huán)節(jié)：①案例導(dǎo)人；②知識(shí)講授；③示例練習(xí)；④課堂小結(jié)，具體過(guò)程設(shè)計(jì)詳見(jiàn)表1。

6 結(jié)語(yǔ)

對(duì)于ACM程序設(shè)計(jì)培訓(xùn)，教師不但要重視讓學(xué)生掌握算法的思想和實(shí)現(xiàn)，更要注重激發(fā)學(xué)生的學(xué)習(xí)興趣，培養(yǎng)和鍛煉學(xué)生利用基本算法舉一反三、靈活解決問(wèn)題的能力。并查集算法是ACM程序設(shè)計(jì)專題中的一種非常高效、靈活的算法。并查集是若干個(gè)不相交集合，能夠?qū)崿F(xiàn)較快的合并和判斷元素所在集合的操作，應(yīng)用很多，如求無(wú)向圖的連通分量個(gè)數(shù)、求最小生成樹(shù)等問(wèn)題。

受微課教學(xué)時(shí)長(zhǎng)的限制，課程沒(méi)有進(jìn)一步探討算法優(yōu)化，將該部分內(nèi)容安排在網(wǎng)絡(luò)課程中由學(xué)生自主學(xué)習(xí)。本次課師生有良好的互動(dòng)，在20分鐘的微課時(shí)間內(nèi)完成了本節(jié)任務(wù)，達(dá)到了教學(xué)目標(biāo)，學(xué)生反饋較好。

總之，在ACM程序設(shè)計(jì)培訓(xùn)中引入微課，課堂只講授算法的精髓，將微課視頻和相關(guān)學(xué)習(xí)資源共享給學(xué)生，賦予學(xué)生極大的擴(kuò)展空間，有效地培養(yǎng)了學(xué)生的自主學(xué)習(xí)能力和創(chuàng)新能力。與此同時(shí)，教師的業(yè)務(wù)能力也在這種精益求精的微教學(xué)循環(huán)中不斷提高。