“并查集算法”微课教学设计

王荣芝 于世华

摘要：微课是目前教育教学改革的一种新型授课方式，具有短、精、活、趣等特征，对促进教师成长、提高学生学业水平具有重要作用。文章以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程序设计培训中引入微课，课堂只讲授算法的精髓，将微课视频和相关学习资源共享给学生，赋予学生极大的扩展空间，有效地培养了学生的自主学习能力和创新能力。与此同时，教师的业务能力也在这种精益求精的微教学循环中不断提高。