《OI 教育漫谈》系列目录:
OI 教育漫谈(一):为什么学习信息学竞赛
OI 教育漫谈(二):信息学竞赛算法自学指南
OI 教育漫谈(三):如何教好基础算法
序言
2023 春这个寒假,是笔者自从高中毕业以来,首个没有算法竞赛教学任务的假期。笔者在这两个月中做了一些关于未来职业的准备,去广州、佛山吃喝游玩了一番,算是第一次享受了正常大学生之假期。在这大把的空闲时间中,笔者与其他 OI 从业者作了一些有益的讨论,对 OI 教育现状进行了一些反思,想要把这些见解记录下来。故现在开启「OI 教育漫谈」这一连载主题,总结笔者四年来的 OI 教学经验,以期对想要接触算法竞赛、或已经在学习算法竞赛的中小学生及家长,以及在算法教育行业工作的人士,提供一些参考。本系列文章会谈论学习算法竞赛的得失、选手该如何自学算法,以及教师如何教好算法。内容随时更新,欢迎读者来信交流。
笔者在算法竞赛业内也算是个知名讲师——尽管自己这样说显得不太谦虚,但确属事实——教过的学生少说也有五千人次。2018 年暑假,笔者刚刚高中毕业,给自己母校的竞赛生们讲了第一堂(有工资的)课,算是初次踏足这个行业。从那时起,每年寒假、暑假、五一、国庆都在洛谷网校教课,主要是普及组集训;同时也给许多其他机构和学校提供培训。回顾这几年的教学经历,往事历历在目,尤以几次线下培训给笔者留下的印象最深。这部分教学经历在之后「如何教好算法」的篇章详述。
洛谷网校办一次集训之后,往往对学生发送问卷,询问其对课程的看法。历次调查问卷皆显示,笔者是普及组学生最喜爱的教师之一,笔者甚感欣慰。笔者的竞技水平并不强,所获的最高奖项无非提高组一等奖。但笔者的 OI 教学能力,包括表述知识的能力、引领人思考的能力和带人写代码的能力,应该是比较高超的。这亦成为笔者声誉的来源。
在教 OI 的过程中,笔者常常探求几个问题:学生学 OI 是为了什么?学 OI 对他的人生有什么影响?他有没有比学 OI 更好的方法去进行自我发展?本文作为《OI 教育漫谈》系列的第一篇,将会着重讨论这几个问题。
首先,让我们来进行一些个案研究——第一个样本是笔者自己。
笔者的 OI 经历:OI 给人带来了什么?
2012 年,笔者进入长郡双语读初中。信息技术课上,李××老师宣传了一个「编程培训」,让有兴趣的学生去参加,每周一次,以中午午休的时间进行教学。笔者自小便喜欢玩电脑,当然去报了名;第一次课上,笔者打开电脑,按老师的要求登入了「oier2012」这个账户,这便是笔者第一次接触「OI」一词。OI 者,信息学奥林匹克也。那堂课上老师讲了一些故事,教我们使用 Dev-C++,后来便开始教 C 语言编程。从简单的分支、循环编程到二分查找、筛法求质数等算法,学着学着便进了 NOIP 普及组考场,考了个零分(因为文件放错了位置)。以上就是笔者初中时对算法竞赛的浅尝辄止。
一转眼,初中毕业,到了湖南师大附中读高中。如果问当时的我们「为什么学竞赛」,那是相当怪异的——附中理科实验班的学生,高一不学竞赛才是咄咄怪事;「选择学哪项竞赛」才是问题。笔者在夏令营时略微尝试了一点化学竞赛,后来由于对计算机的兴趣更浓厚,故选择了信息学竞赛。
这是影响笔者一生的决定。每回忆至此,笔者深庆幸于当时选择了 OI:这个选择将笔者从黑白颜色的普通高中生的「做题 - 考试循环」生活中抽离出来,放到五彩缤纷的竞赛环境中浸染了两年时间,并塑造了笔者的性格底色。
笔者高中时,正值 OI 的壮年。其时形势一片大好,仿佛谁都可以从 OI 中分一杯羹,以略低的高考成绩进入理想的大学。笔者高一、高二从未认真上哪怕一天的文化课,绝大部分精力投入到了 OI 相关的事情上(现在 OI 日薄西山,当代 OIer 恐难以体验到这种生活)。高一首先快速复习 C++ 语法,然后开始数据结构、动态规划等知识的学习,到了联赛提高组级别便开始以做题训练为主。然而笔者的代码能力很差,天赋亦欠缺,最终没有取得多少成绩,17 年省选后退役,笔者的竞赛生涯以 NOIP 提高组一等奖收场。高考后利用这个奖项参加哈工大自主招生,并进入计算机系。
在竞赛过程中,笔者深度参与了 OIer 社区,在当时 OIer 群体内是小有名气。这也是后续被各个机构邀请讲课的原因。
今天如果要问,OI 给笔者带来了什么?这似乎很难以回答。参与 OI 是一项系统性的活动,OIer 社区是联系极为紧密的情感网络,其对人的影响是全面且深远的——对于人生观成型期的中学生而言尤其如此。如同上文所说,OI 经历可以塑造人的性格。OI 对笔者的影响绝非三言两语可以概括,但笔者试图从千头万绪中找到几条「显性」的点:
- 学习计算机科学,可让人拥有更理性的思维方式。
- 对编程、算法和数据结构的熟练掌握,令笔者在大学本科生活中更加淡定,不必为学习而焦虑。笔者确信自己可以成为同辈中的领先者,事实上也确实如此。
关于前者,笔者有必要作进一步解释。试举一例:假设有新闻报道「某品牌智能手表对着萝卜可以测出心率」,OIer 看了往往觉得这如同太阳东升西落一样不言而喻,但社会大众可能十分惊异并怀疑该品牌手表的可靠性。「未定义的输入可能产生任何输出」,这一理性思维模式如同公理一样刻入了 OIer(或扩大一点说,计算机从业者)的脑海中,这与常人迥异。另举一例:参加过数学竞赛的学生,去做高考的立体几何题,常常认为几何方法是「高贵」的,而建系方法(确定每个点的坐标,利用数值计算求出法向量,再计算出体积等)是「低贱」的。但 OIer 的思维方式与之彻底相反:OIer 会认为建系方法是十分优美的,而且 OIer 还倾向于进一步采用叉积(而非传统数学课上教的列方程)去快速计算法向量。究其原因:计算机工程学的思维方式很强调「把本质相同的现实问题统一成同一个模型,并提出一个通用方法解决此类问题」。这也潜移默化地影响了 OIer 解决问题的路径选择方式。
但笔者必须指出,并非所有的「OIer 思维」都是极好的。笔者前段时间与蔡德仁先生等 OI 教育同好进行过一些讨论,摘录笔者的发言如下(略删改):
OI 坏的地方,在我看来,是使人变得魔怔……我观察到 OIer 对于一些问题的思维方式有些时候难以理解。我考虑了一段时间,可以举一个我认为比较恰当的例子:刚退役不久的 OIer常常持有一个“执念”,或者称“放不下”的特质,即(有意识或无意识地)寻找到某种生活的“支柱”,并在这个支柱下获得认同感。直到时间推移,他可能逐渐发现这个东西对他的精神生活并没有他之前认为的那么重要(慢慢发现它可以不具备支柱地位),最后离开这个支柱。
“执念”这种特质的来源,我认为也许奥林匹克赛事选手或多或少都会有,因为竞赛在当时就是选手的支柱。而 OIer 比其他竞赛选手更方便的社交更加放大了这个特质:OIer 是一个很大的情感网络,当选手被迫离开时常常痛哭流涕,并在高三一年学习文化课的时候怀念自己的 OI 生活,这无形中,我认为,会加深人对“支柱”的依赖感,并在下一次获取到支柱时抓得很紧,很不愿放手(即使他很可能不承认自己有某种精神支柱)。
当然这个例子肯定会挨喷,有 OIer 可以立即声明自己没有这样的特质。应当指出,我并不是说所有 OIer 都有这种特质,但 P(有这种特质 | 该人士是oier) 是高于一般人中有这个特质的概率的。
这个特质究竟是好是坏,我没有结论:可以说这群人很执著,也可以说这群人很魔怔。但我注意到很多 OIer 因为对某种事物的执念,忽略了他本来能发现的很美好的风景。
笔者在本章节写了大段文字,主要想说明的就是:OI 经历对人的影响是复杂深刻的,「是否参与 OI」并不是一项如同「周末是否去公园踏春」一样可以很轻松就做出的决定。当一个人深度参与 OI 之后,他的思维方式将迎来微妙而深层的改变,进而影响到他解决问题的方式、影响到他的交际圈子,并最终影响到许多重要的人生选择。
有得必有失,人从 OI 中得到了好处,必然要在其他地方失去一些东西。笔者犹记退役后回到文化课班级,时值高二末的会考复习,由于某科作业未写,被老师赶出教室,在走廊上仓皇徘徊。笔者高一时的语文老师厉先生路过,见我竟出现在了教学楼内(其时笔者已经未上文化课一年),问及近况,得知我刚刚退役,便露出极高兴的神色,说竞赛生为了专精于竞赛,抛弃了许多高中生应有的珍贵体验和多领域的全面发展机会,乐见我回归文化课。转眼数年倏忽而逝,笔者去年春节前去先生家拜访,讨教教书育人的经验和理念,言谈中颇获益,更感到教师之爱学生,则为之计深远。
学习 OI 的动机之众生相
笔者学习 OI 之动机,初中时是「对计算机感兴趣」,高中时是「比起其他四门竞赛更喜欢 OI」,以及「OI 对升学有帮助」。笔者长期来未能了解其他 OI 选手学习 OI 之动机,尤其是弱省、弱校、自学的选手。机缘巧合,笔者于去年暑假自办了一场夏令营,招收到三十余名学生。这大部分学生刚学会 C++ 编程,由笔者用 14 天时间教授普及组算法和数据结构,领他们踏入算法学习的大门。招生时应付了大量的家长咨询,笔者也趁此机会了解到一些学生为什么要学习 OI——排除掉一些极端个案(如抱着从众心态学习 OI、为了趁机打游戏而学习 OI),大体上可以分为两类:「升学愿景」和「兴趣使然」。
——有一部分人是为了升学。有家长讲,自己孩子是小学生,而有一些优秀的初中可以录取在 OI 中有一点成绩的学生。也有家长希望自己读初中的子女通过学习 OI 进入省内不错的高中。有学生希望拿个提高组奖项,将来用于考大学时参与综合评价等。
——有一部分人是出于兴趣。有学生并未指望自己透过 OI 去升学,只是趁着离高考压力还很远,单纯地想利用这段时间学习编程和算法,家里人也十分支持。这是笔者最期待的学习动机。
许多学生和家长的心态是上述两者之杂糅。一方面,学生自己对计算机技术有兴趣,而这样的兴趣便投射到了中学生能参与的与之最接近的学科竞赛——OI。另一方面,OI 奖项或多或少地可以给小升初、初升高带来优势,这也是许多家长愿意支持子女参与 OI 的重要原因。
数年前,教育部开始打击五大竞赛,省一等奖从 2018 年的可以让山大降一本、哈工大降 60 分、华中科大降 40 分,突然变得几如废纸。对于未来的 OI 升学局势,笔者作悲观判断。国家集训队的保送政策或许会多年保留,但 OIer 想要回到 2018 年那种付出一些不多的努力便可以读大学的状态,是不可能的。现在的 OI 竞争比早年激烈得多,升学名额却少得多。笔者不建议抱着升学的心态学习 OI,除非是在极强省极强校,有冲进省队的潜力,同时文化课水平也不差。
「大浪淘沙,始见真金」。在祛除了 OI 学习的功利性之后,其对人真正的优点(而非升学选拔上的优点)逐渐清晰:锻炼了人的抽象思维能力,让人掌握了一门编程技术,培养自学能力,培养抗压能力……
然而,我们的思考不能止于此步。来考虑一个问题:假设一个初中生想要锻炼上述能力,那参与 OI 是他的最优解吗?在很多年前,笔者也许会回答「是」;但现在,笔者的答案要复杂许多。这便要牵涉到 OI 的发展现状——如今之 OI,是在培养敏锐的思考者,还是做题家?
思考者还是做题家?
笔者把 OI 分为两个层级:「基础级」,即基本 C++ 编程、普及组水平的算法和数据结构;「竞技级」,即提高组往上的知识点和应试技巧。对于基础级的 OI 教育,笔者非常认同它可以直接、大幅度地强化人的思维能力,笔者本人也在从事这方面的工作。但对于竞技级的 OI,笔者认为其尽管锻炼了一些思维能力,但仍没有跳出高考式选拔考试的窠臼。换言之,笔者认为竞技级 OI 是在培养「做题家」。
这当然是笔者的一家之言。事实上,在讨论时,此言一出,便招致了大量高水平 OI 选手的反对。但以下事实是确凿的:OI 中引入了大量的各种数论筛法和反演技巧作为考题,而这类技巧是「专供信息学竞赛」的——很多算法甚至是前一代 OI 选手原创的。这些算法比起我们耳熟能详的二分、Dijkstra 等算法,几乎不具现实意义,对人的启发也有限。我们是否要认同一个人花大量的时间去钻研 OI 出题风向,而不是把精力拿去学习其他领域?
——从竞赛出成绩的角度来讲,是要的。选手对时兴的出题方向钻研得越深,类似题目做得越多,他越可能取得好成绩。然而,一个选手参与 OI,是期盼于做这些事吗?从个人发展的角度来讲,钻进这种洞里是值得的吗?
讲到这里,我们必须谈论「学习 OI」与「学习算法」的割裂。OI 是奥林匹克运动,一个省份只能出几十位 NOIP 提高组一等奖选手;这些选手去参加省选,至多只能有十几个选手可以进队;省队成员去参加 NOI,只有五十人可以进入集训队。OI 的选拔性特质决定了其一定陷入「选手水平提高 → 出题人出偏题难题以考察选手 → 新一代选手的水平进一步提高 → 题目更加怪异」的悲剧循环中。
但是学习算法的过程可以并不如此。学习算法可以不与人竞争,学习者可以因为学到了一些新的算法、把一个问题成功转化为已有模型而怡然自乐。这便是笔者所推崇的心态——一种田园牧歌式的、不汲汲于功名的心态。
当我们把「学习 OI」与「学习算法」剥离开来,立刻就可以发现算法世界的广阔之处。一个人在学习完基础级算法之后,完全可以不再沿着 OI 的道路继续竞技;他可以去学一点离散数学,学一点密码学算法,学点并行算法,甚至去学时下流行的机器学习算法。笔者相信,这样的学习,比起钻进竞技 OI 的笼子里,对人更加有益。
讲到这里,读者应该已经认同,如果一个人说他对 OI 有兴趣,我们应当探查他究竟是对「CCF NOI 系列竞技运动赛事」有兴趣,还是对「学习算法」抱有兴趣。如果一个人的兴趣是前者,那我们当然支持他继续钻研竞技级 OI;但如果他的兴趣是在于学习算法而不是与人竞技,那么,一定会有一条更好的路。
然而,为什么对于现在的中小学生,大众提起学习算法就言必称 OI 呢?这便是我们当前的现实:如今之 OI,掺杂了大量不该由 OI 实现的使命。许多学生并非抱着参与 OI 竞技的目的——他可能单纯地对算法感兴趣,或是对计算机技术感兴趣,但他却只能通过参与 OI 达到这些目的。
如今之 OI 教育掺杂了大量不该 OI 实现的使命
读者可能已经知道,市面上的大量少儿编程机构是利用家长的不懂行进行诈骗。唆使不懂电学的小学生去学习 arduino 嵌入式开发、唆使一元二次方程都解不明白的学生去学习人工智能,是令人目瞪口呆的巨大骗局。与这类机构相比,OI 培训至少像个人样——教的是编程和算法,至少比教机器人好。
今天,如果一个初中生想要入门算法,那么他除了去学习 OI 普及组之外,几乎没有什么其他高效途径。也正因如此,在 OI 初学者及其父母眼里,常常存在着这样一个连等式:「学 OI = 学算法 = 学计算机」。我们前文已经论述了第一个等号不成立,事实上第二个等号也不成立。传统算法只是计算机科学中的一个部分,计算机还存在大量的其他领域值得学习。举个例子,计算机系统和计算机网络就甚为值得学习,而它们常常无需用到竞技级算法知识——拥有基础级算法知识和 C++ 编程能力作底子,已经可以去学习这些领域了。
然而,我们看到,有许多人怀抱的是对计算机的喜爱、对算法的喜爱,进入了 OI 学习。笔者鼓励学生通过学习普及组 OI 来掌握算法,因为普及组 OI 的学习与基础算法的学习是非常重合的。但如果一个人喜欢的是各种算法或计算机技术,那么笔者建议他在学习完普及组 OI 之后就跳出来,不再跟随 OI 参与内卷,而是去探索自己喜欢的计算机领域。
这条路径该如何做到?譬如讲,该如何确认自己已经掌握了基础级别的算法,到了该跳出来的时候?没有老师,该如何去探索计算机的其他领域?这便是我们马上要来讨论的问题。
中小学生学习计算机的较佳路径
笔者没有使用「最佳实践(best practice)」一词,但笔者认为下面的途径至少是较佳的:
- 学习基本的编程语言。笔者建议先学习 Python。
- 利用已学会的语言做一些无关算法的有趣工作,例如用 Python 写一点爬虫、搭建一个网站;用 C++ 写一个字符界面的游戏等。这个过程可以帮助学生熟练掌握编程技术,并巩固兴趣。
- 学习 OI 普及组算法。按照 CCF 入门级大纲进行学习,过程中要做大量算法题目。至于该如何学习普及组算法,这个问题将在后续的「如何自学算法」文章中详述。即使是有老师教的学生,也可以参考该文。
- 学习一门新的编程语言(笔者建议 javascript),并探索计算机的其他领域。后文详述。
如何确定自己已经学习完了基础算法,可以进入「探索计算机的其他领域」阶段?我们可以列一个清单出来,看选手有没有掌握以下内容:
- (C++ 编程)能流畅地编写逻辑不复杂的程序、能熟练使用 vector、map、stack、queue 等 STL 容器
- (暴力算法)枚举元组、枚举排列、枚举组合
- (基础算法)二分、贪心、基础动态规划
- (数学)初等数论、初等组合数学、初等解析几何
- (数据结构)栈、队列、链表、堆、线段树
- (图论)图和树的定义、搜索(BFS、DFS、迭代加深搜索)、Dijkstra 单源最短路算法、Kruskal 最小生成树算法
应当指出,「看过教材」绝不等于「掌握了知识」。算法是需要去实现的,选手应当能很轻松地写出对应的模板题目,才能说自己掌握了该项算法。
如何自学计算机的其他领域?一个刚学完 OI 普及组的选手,对于计算机科学的全景很可能没有多少认知。笔者在这里推荐选手去读一本书,即《深入理解计算机系统(原书第3版)》,简称 CSAPP。这本书被誉为计算机领域的圣经之一,写得深入浅出,并延伸到了计算机科学的方方面面。阅读这本书不是一件轻松的工作,需要大量的精力投入,其中「处理器体系结构」可以略去不读。另一本值得推荐的书是《计算机网络:自顶向下方法》,这本书比 CSAPP 易读很多,能让人对复杂系统有更好的理解能力。
做完了这些事之后,选手应该接触到了计算机科学的很多门类,大约也找到了自己感兴趣的方向。计算机科学无分贵贱,写网站是好的,研究机器学习是好的,研究编译原理也是好的,给 Minecraft 写 mod 也是极好的。笔者只希望,选手在阅读本文之后,能跳出 OI 的框架去看待算法学习或计算机学习,并把自己的精力直接拿到喜欢的方向上去。
(2024 年 9 月 19 日更新)
本文写于 2023 年初。一年多以来,OI 的形势似乎发生了一些变化,这里刊登蔡德仁先生(也是一位 OI 教育者,对现代 OI 教育体系贡献颇多)今天对本文的评论:
某种程度上,这个文章可能有点过时。比如学 OI 一个非常大的动机:文化课坐牢太痛苦了,OI 坐牢没那么苦。文中是不是没提到。
另外,OI 现在正在减少技巧。现在 NOI 和联省没有“大量的各种数论筛法和反演技巧”之类的东西了。
我还是挺支持最后几段论述的,但是可能“学习算法”得换成“学习计算机科学技术”。要是学习算法可能还真的不适合普及组结束,哪怕不想竞争奥赛。如果是专门对算法感兴趣的建议学完 NOIP,然后搞熟悉 OI 高水平退役大学生的联系方式再走。
要是有意向搞算法科研的话,除非家里有条件提前读顶尖大学,建议 OI 一条道打到黑。因为我还真没见过其它更好的中学培养手段……总之我的意思是说,如果你中学就非常有志于花至少小半辈子搞算法科研(或者其他需要算法的科研),并且你的现实条件允许你花很多时间提前学科研基础,培养那些顶尖大学正经科研大一到研二想给算法科研培养的能力,那么你如果适合搞科研,多半在学了一两年之后就有不少提升。而且你在这个基础上学 OI 大概率 1500h 就能达到强省大部分选手学 3500h 的水平。所以我建议你真要条件这么好直接再打个 OI 拿牌。根据几个例子估算的,不一定非常科学。反过来,如果你的现实条件不允许你花很多时间提前学科研基础,那其实没有这个现实选择摆在你脸上。
欢迎读者来信交流,笔者邮箱是 ruanxingzhi@gmail.com 。