基于ACM-ICPC竞赛模式的算法设计与分析教学改革实践

王淼，董星星

1.河南工程学院 计算机学院，河南 郑州 451191； 2.河南理工大学 计算机科学与技术学院，河南 焦作 454000

0 引言

算法是一种具有创造性、逻辑性的思维活动，算法设计与分析是计算机科学与技术、软件工程、物联网工程等专业中一门非常重要的面向设计的课程[1]。该课程包括很多经典算法，比如回溯算法、贪心算法、递归与分治、动态规划、分支界限法等。通过学习算法的设计原理、复杂性分析以及具体实现，培养学生独立思考问题和解决问题的能力，为学生利用算法知识完成期末实训、毕业设计、公司实习以及开发出高效的系统奠定了坚实的基础。该课程的特点是理论性强，比较枯燥，必须通过大量实践才能彻底掌握算法原理，课程内容具有广泛性、综合性、系统性，需要比较扎实的数学基础知识[2-3]。

ACM-ICPC（ACM International Collegiate Programming Contest，ACM-ICPC）是由国际计算机协会（ACM）主办的国际大学生程序设计竞赛，要求每组参赛选手必须在五小时内编写完程序并进行测试和调试，在线提交竞赛题目到指定位置。ACM-ICPC竞赛所涵盖的知识面比较广，需要参赛者在计算机编程、离散数学、计算几何等方面具备一定的功底，并且分析处理问题的能力较强。参加竞赛可以提高选手的逻辑计算能力、团队合作能力、创新能力以及计算机编程能力，通过区域赛和总决赛的角逐，最终挑选出最优秀的程序设计人才[4]。

如何更好地讲授算法设计与分析这门课程，是广大教师所面临的问题，在讲授过程中，笔者发现了教学存在的问题，并尝试做出了改革实践，积累了一些经验。如果教师将算法设计与分析的课程内容与ACM-ICPC竞赛结合起来，通过竞赛题目引导学生分析问题，进而展开课程内容讲解，将有利于调动学生学习的积极性，使得学生深入理解算法原理。

1 算法设计与分析教学存在的问题

1.1 理论与实践脱轨，教学方式单一

在教学方式上，传统的教学重视理论教学，忽略实践教学，教师大多通过PPT讲解课程内容，缺乏创新。算法设计与分析的课堂环节包括课程导入、讲授新知、巩固练习、课堂小结，教师主要利用讲授法完成大部分环节，学生拿着课本听讲，缺少师生之间、生生之间的课堂讨论，容易导致学生注意力不集中，听课效果较差。

除此之外，虽然课程安排包括实验课，但实验课时间短、要求较低，学生对于实验课不够重视，部分学生并未理解算法的设计原理和具体实现，没有按照要求编写程序，而是直接提交实验报告。总体来说，教师的教学方式比较单一，主要是通过PPT展示教学内容，忽略了互动环节，缺乏生动形象的教学方式，并且没有意识到实验课的重要性，一直以同样的方式教学，学生容易注意力分散，学习效果差。

1.2 课程枯燥且难度大，学生缺乏兴趣

在教学内容上，与其他基础课程相比，算法设计与分析课程本身所涉及的知识点难度较大，缺乏生动形象的案例帮助理解，而且需要一定的数学基础。为了后续能够编写程序，课程内容中的很多经典算法需要学生掌握，如果教师花费大量的时间讲授基础知识，学生参与感不强，难免会感觉枯燥，缺少学习算法知识的兴趣。

算法分析需要学生静下心来思考问题，而学生自身分析问题和解决问题的能力不够，使得难以理解算法原理和具体实现。想要真正理解算法设计与分析这门课程，并学会应用算法设计与分析解决实际问题，机械地记忆算法的步骤是远远不够的，需要冷静、努力、认真分析才可以，发现学习算法设计与分析课程的乐趣，慢慢激起学生学习算法的兴趣。

1.3 实验要求过于形式，考核方式不当

在考核方式上，传统的算法设计与分析的课程考核分为期末考核、实验课考核两部分。期末考核包括平时成绩和期末考试试卷成绩。期末考试的试卷内容是课本上的理论知识，平时成绩包括课堂出勤和课堂作业，侧重考察理论知识的掌握情况。实验课考核包括经典算法的程序实现，侧重考查学生操作能力。

看似合理的考核方式实际存在诸多问题。期末考核以期末考试试卷成绩为主，平时成绩作为参考。由于期末考试试卷的成绩所占比重较大，很多学生在考试前几周开始复习考试内容，前期并没有投入学习，只是“为了考试而考试”，失去了考试的真正意义。

实验课考核大多是教师提供题目和参考代码，学生按照参考代码调试程序，运行出结果，将运行结果整理成实验报告提交给老师。对于简单的题目，学生通过参考代码实现，并没有自己思考的过程，而对于复杂的题目，学生无从下手，大部分学生直接网上搜索，下载源程序，失去了锻炼自己的过程。而且实验作业是一个比较简单的实验报告，无法考核学生对于算法原理的具体掌握情况。

2 基于ACM-ICPC竞赛模式的教学改革

2.1 教学内容改革，与竞赛试题结合

ACM-ICPC竞赛题目具有创造性、难度较大、考察范围广、与生活中的实际问题联系紧密。为了解决算法设计与分析的教学内容与实践脱轨、学生缺乏兴趣的问题，针对教学内容进行改革，与竞赛试题相结合。该教学模式着重培养学生分析问题和解决问题的能力，比如在竞赛中无法将实际的问题转化为利用相关算法实现。

课堂的导入环节以竞赛题目的形式呈现，让学生分组讨论题目，发现自己疑惑的知识，然后教师针对学生提出的问题进行解答，并展开新知识的讲解。这样将有利于激发学生的学习兴趣，培养学生的团队协作能力。

除此之外，课堂的巩固练习和布置作业环节同样与ACM-ICPC竞赛题目结合，利用ACMICPC竞赛变式题考查学生对于知识的具体掌握情况。ACM-ICPC竞赛变式题的题型分为基础型和挑战型，基础题型主要涉及排序、递归、分治法、动态规划、贪心算法、分支界限法等基础知识，锻炼学生的基础编程能力；挑战题型主要涉及算法的综合应用，可以适当设置ACM-ICPC竞赛真题，培养学生的凝聚力和创造力。总体来说，通过教学内容和竞赛试题的结合，引导学生深入思考，培养学生的创新思维，从而达到改善教学效果的目的。

2.2 教学方式改革，重视互动式教学

传统的教学方式以教师讲授为主，学生往往被动学习，教学效果不佳。为了增强课堂的互动性，尝试引入“对分课堂”模式进行教学，“对分课堂”是一种传统课堂与自主课堂的融合，其核心理念是将课堂时间一分为二，一半时间留给教师讲授知识，另一半时间留给学生自主讨论学习，重视互动式教学[5]。学生吸收了课堂知识以后，了解到自己不理解的知识点，带着问题进行讨论，这样达到的效果是比较好的，不仅可以提高教学质量，也加深了学生对于知识点的理解。

课堂的新授环节从分析问题入手，教师讲授算法的实现原理，学生带着问题讨论，最终利用ACM-ICPC竞赛变式题考查学生对于知识的具体掌握情况。这样的课堂教学不仅仅强调了算法理论知识的学习，更重要的是让学生掌握算法的具体实现。总体来说，通过互动式教学，增强教学过程中的师生互动、生生互动，贯彻了“以人为主”的教学理念。

2.3 考核方式改革，多方面综合考察

考核作为教学过程中的一个检验环节，科学的评价方式对促进学生的学习具有重要的导向作用[6-7]。传统的考核方式包括期末考核、实验课考核。期末考核以期末考试试卷成绩为主，平时成绩作为参考，过于强调结果而忽略学习过程，实验课考核存在同样的问题，学生在平时学习比较松懈，这样的考核方式无法反映出学生对于这门课程的真实掌握情况。

考核方式应当重视教学过程的考核，比如：课前预习、课堂回答问题、课后作业题、实践考核等，多方面综合考察。具体来说，算法设计与分析课程考核分为理论考核和实践考核两部分。理论考核包括平时出勤、课堂回答问题、课后作业以及期末考试。平时出勤是指学生每节课按时上课的次数，课堂回答问题是指学生个人回答问题次数和小组回答问题次数的累加，侧重考查学生上课的积极性。课后作业是ACM-ICPC竞赛题，激发学生的学习兴趣。期末考试侧重考查学生分析问题解决问题的能力；实践考核是在传统实验课考核的基础上增加了ACM-ICPC竞赛题目的练习，以课堂巩固和布置作业的形式呈现，通过自动判题平台加强训练，综合考查学生的实践能力。其中，理论考核和实践考核各占50%，解决了传统教学存在的理论与实践脱钩的问题，丰富了考核方式，不再以单一化的教学方式进行授课。通过这样全方位的考核，提高学生编程实践能力，督促学生边实践边学习，锻炼自己解决实际问题的能力。

2.4 加强经典算法的综合分析

算法设计与分析课程有很多经典问题，可以采用不同的算法实现。教师在讲解过程中，对各算法的复杂度进行分析比较，总结各算法的优缺点，重点是分析算法之间的联系，图1展示了分治法、动态规划法、贪心法之间的联系，使得学生可以理解典型算法的核心思想。通过这些经典问题的综合分析，引导学生深入思考问题，培养学生的逻辑分析能力和独立思考能力。

图1 经典算法之间的联系

综上所述，教学改革后的教学流程分为课前准备、课堂学习、课程考核三大部分如图2所示。课前准备是指课前预习，完成预习内容。课堂学习包括导入、讲授新知、巩固练习、课堂小结、布置作业五大环节。课堂的导入环节以竞赛题目的形式呈现，学生分组讨论题目，教师借此引入新课；随后，利用“对分课堂”模式进行讲授新知，前一半时间，教师讲授新课，后一半时间，学生带着问题进行讨论，增强师生互动、生生互动；巩固练习环节和布置作业环节仍以ACM-ICPC竞赛变式题（基础题型、挑战题型）考查学生的掌握情况；课堂小结环节加强经典算法的综合分析，重点是讲明算法之间的联系。课程考核包括理论考核（50%）和实践考核（50%），理论考核是指平时出勤、课堂回答问题、课后作业以及期末考试，实践考核是指实验课和ACM-ICPC竞赛试题的练习。

图2 教学改革后的教学流程示意图

3 结语

基于ACM-ICPC竞赛模式的算法设计与分析教学改革实践，指出了传统教学存在的一些问题，比如理论与实践脱钩、课程枯燥且难度大、考核方式不当等问题，在传统教学的基础上，进行了教学改革。把算法设计与分析相关知识以竞赛题目的形式呈现，激发学生的学习兴趣。引入“对分课堂”模式，充分体现了学生的主导地位，增强了师生之间、生生之间的互动性。通过理论考核和实践考核相结合，激励学生边学习边实践，弥补了传统教学的不足。通过算法设计与分析教学改革实践，锻炼了学生分析问题解决问题的能力，整体改善了教学效果。