“并查集算法”微課教學設計

王榮芝 于世華

摘要：微課是目前教育教學改革的一種新型授課方式，具有短、精、活、趣等特征，對促進教師成長、提高學生學業水平具有重要作用。文章以ACM/ICPC競賽培訓中“并查集算法”教學為例，提供一套微課教學設計方案，強調情境設置激發學習興趣、設疑討論引發思維風暴、任務驅動增強體驗成就，幫助學生從基本知識到能力培養的快速過渡，為其他微課教學提供借鑒。

關鍵詞：微課；教學設計；ACM/ICPC；算法；并查集

1 背景

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

2 前期分析

2.1 教學內容分析

ACM/ICPC（國際大學生程序設計競賽）足目前最具影響力和規模最大的國際頂級賽事，足大學計算機教育成果的直接體現，各高校普遍將其作為大學生程序設計能力的體現ACM/ICPC涉及知識面廣，涵蓋數學建模、計算機、英語等學科，對學生自主學習能力、創新能力、團隊精神以及在競爭壓力下進行開發活動能力的培養有著積極的意義。ACM/ICPC競賽培訓主要針對ACM/ICPC參賽隊員和愛好者進行競賽知識培訓，系統介紹計算機各類常用算法。培訓根據算法類別以專題方式進行，每個專題介紹該類算法的基本理論、算法實現及應用案例。

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

2.2 學習者分析

參加ACM競賽培訓的學員前期學過C/C++及數據結構課程，掌握線性表、樹、圖等結構和基本算法；了解ACM/ICPC競賽模式，對競賽有興趣，有一定的自主學習和探究能力，能夠解決一般性題目，但不具備系統解題技巧。

3 教學目標

3.1 本節（課）教學目標

（1）知識和技能：理解并查集算法的基本思想，掌握3種基本操作的算法實現，學會使用并查集方法解決實際問題。

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

（3）情感態度和價值觀：激發對ACM程序設計的興趣，學會鉆研與思考。

3.2 教學重點及難點

（1）教學重點：并查集的基本思想和算法實現。

突出措施是通過多媒體展示ACM案例；通過對比傳統無向圖解決方式存在的缺陷，引出并查集解題思路和具體實現；使學生體會算法的簡單和靈活。

（2）教學難點：并查集算法的解題應用。

突破措施是總結算法特點和應用范圍，給出基本代碼；除課堂案例外，加入兩個練習及多個課下練習，讓學生進一步應用和鞏固。

4 教學資源、方法及策略

4.1 教學資源

教學環境為多媒體教室，教學課件采用PPT幻燈片；通過生動武俠形象為案例“江湖朋友圈問題”創設情境，如圖1所示；解題過程采用動畫方式，分步演示思路和步驟；程序編寫及測試應用DEV C++軟件；課上及課下練習應用本校“ACM在線自動評測試系統”，課程知識擴展應用網絡課程教學平臺。

4.2 教學方法及策略

（1）情境設置法的教學策略：利用江湖和武俠人物圖片向學生描述“江湖朋友圈問題”創設教學情境，引出問題討論。

（2）問題討論法的教學策略：引導學生思考解決“江湖朋友圈問題”的方法，激發學生的思考，引發學生的思維風暴，讓課堂教學目的更加明確，組織更加高效。

（3）任務驅動法的教學策略：將課上分析案例及課下作業布置為ACM提交任務，讓學生以完成任務為目標，激勵學生應用所學知識。，

5 教學過程設計

教學過程主要包括以下4個環節：①案例導人；②知識講授；③示例練習；④課堂小結，具體過程設計詳見表1。

6 結語

對于ACM程序設計培訓，教師不但要重視讓學生掌握算法的思想和實現，更要注重激發學生的學習興趣，培養和鍛煉學生利用基本算法舉一反三、靈活解決問題的能力。并查集算法是ACM程序設計專題中的一種非常高效、靈活的算法。并查集是若干個不相交集合，能夠實現較快的合并和判斷元素所在集合的操作，應用很多，如求無向圖的連通分量個數、求最小生成樹等問題。

受微課教學時長的限制，課程沒有進一步探討算法優化，將該部分內容安排在網絡課程中由學生自主學習。本次課師生有良好的互動，在20分鐘的微課時間內完成了本節任務，達到了教學目標，學生反饋較好。

總之，在ACM程序設計培訓中引入微課，課堂只講授算法的精髓，將微課視頻和相關學習資源共享給學生，賦予學生極大的擴展空間，有效地培養了學生的自主學習能力和創新能力。與此同時，教師的業務能力也在這種精益求精的微教學循環中不斷提高。