结合OJ及竞赛的算法设计与分析课程教学实践

时慧琨

摘要：针对算法设计与分析课程教学中教学以讲授为主、学生缺乏实践机会及实践脱离应用实际的问题，从在线测试（OJ）系统建设、实践团队组织、教学活动开展和竞赛组织参与等方面，详细阐述了在教学过程中结合OJ以及竞赛开展课程教学的实践模式，激发学生学习主动性，引导培养学生分析问题，解决问题能力及团队合作能力，提高教学效果。

关键词：算法设计与分析;OJ;教学实践

中图分类号：G642        文獻标识码：A

文章编号：1009-3044（2021）10-0149-03

Abstract：In the teaching of algorithm design and analysis course， there are some problems such as too many theoretical teaching， lack of practical opportunities and practice divorced from real application， etc. This paper elaborates on the practical mode of combining online judge（OJ）system and competitions in the teaching process from several aspects include OJ system construction， practice team organization， teaching activities development and competition organization participation. Practices proved these measures can stimulate students' learning initiative， guide and cultivate students' ability of analyzing， problem solving and team working， so as to improve the teaching effect.

Keywords：AlgorithmDesignandAnalysis;OJ;teaching practice

1算法设计与分析课程

算法设计与分析课程是高校计算机专业学生的一门专业必修课，该课程主要学习算法设计和算法分析的基本理论及方法。通过课程的学习，掌握算法设计的一般技术，能够对给定的问题进行分析，建立数学模型，设计解决问题的算法，并进而将其转换为程序。学生同时也要能够从时间和空间角度对算法的性能进行分析，选择合适的算法设计方法以高效的方式解决问题，培养学生分析问题、解决问题的能力及编程实践能力和创新能力。

算法设计与分析课程直接以用计算机技术解决实际问题为教学目标。利用计算机技术解决问题和其他解决问题的方法不同，在解决问题时并不是针对数据实例直接处理，而是要分析问题的本质特性，建立问题求解模型，设计问题求解的步骤或算法，并开发程序，程序由计算机执行并得到结果。开发的程序要求能够对问题的各种输入都得到正确的结果，并且程序通过重复执行和复制传播，从而成倍的提高生产效率。这样一种解决问题方法的实现要求学生具备更高的分析、概括和抽象思维能力，同时也要求学生具备较高的设计能力和软件开发能力。算法设计与分析课程就是一门综合培养这些能力的课程，课程的教学效果对学生的培养质量有直接的影响。目前社会上对计算机专业学生的需求和学生的实际能力存在一定的脱节，部分就是因为学生分析问题，解决问题能力的缺乏。因此，在算法课程的教学中，研究如何提高培养质量，提高学生的分析能力、实践能力和创新能力非常重要。

2程序设计竞赛及OJ系统

程序设计类竞赛中最早、最有名的是ACM-ICPC（ACM国际大学生程序设计竞赛），竞赛历史最早可以追溯到1970年，是一项旨在展示大学生创新能力、团队精神、分析、解决问题以及编程能力的年度竞赛。2018年，来自全球6大洲，111个国家，3098所大学的5万多名选手参加了比赛。这一比赛采用3人团队合作利用一台计算机解题的比赛机制，自出现以来，在国际上获得了广泛的影响，国内也出现了采用类似机制的各类程序设计比赛，例如CCPC中国大学生程序设计竞赛以及各省教育厅组织的程序设计竞赛等。另一方面，因特网上出现了各类的Online Judge系统（OJ），这是一种模拟ICPC机制的在线判题系统。常见的OJ系统包括POJ、ZOJ、HDOJ、Vijos、USACO等。一些OJ系统的源码，例如HUSTOJ等也在因特网上公开，自主开发的难度也不大，这也大大促进了OJ系统的普及，为广大师生的编程练习提供了绝佳的平台。

3 结合OJ及竞赛的算法设计与分析课程教学措施

OJ作为一个在线测试及实践平台，内部包含大量练习，可以提供给学生内容和难度各异的练习机会。学生可以在OJ系统中针对每一个任务进行分析和编程，并提交代码，OJ系统用内置的数据进行验证，并返回“通过”或者错误的原因。目前，国内外的各种OJ系统主要用于学生练习和比赛，并没有和教学紧密联系。如何结合OJ系统以及程序设计竞赛，提高学生学习的积极性和主动性，提高算法设计与分析课程教学的效果，在如下几个方面给出建议，供大家参考：

3.1 OJ系统的建设

目前已有的各种OJ系统主要是针对竞赛及较高水平学生学习需求设立，在题目编排、难度划分上并不适合用于教学，缺乏层次性和教学的针对性。为此，我们在公开的OJ系统的基础上，将算法设计与分析以及相关的高级语言程序设计、数据结构等课程的例题和课后习题加入OJ系统中，学生在学习完相应内容后，可以直接在OJ系统中开展练习，由OJ系统进行判定[1]。为了方便大家学习，提供测试数据下载的功能，方便学生进行检查分析。通过这些练习，为学生掌握课程教学内容提供了实践机会。同时，将一些竞赛材料中的试题及竞赛题也输入到系统中，以满足学生进一步学习及竞赛练习的需求。除此之外，为部分学生开放权限，鼓励学生在题库中添加内容，在添加内容时可以指定题目相关的知识点及难度等信息，方便学生在教学过程中根据自己的需要进行选择。同时，也鼓励学生注册国内外其他OJ平台账号，并在平台上开展练习及交流。