《OI 教育漫谈》系列目录:
OI 教育漫谈(一):为什么学习信息学竞赛
OI 教育漫谈(二):信息学竞赛算法自学指南
OI 教育漫谈(三):如何教好基础算法


序言:教好算法不等于带好竞赛

  本文是《OI 教育漫谈》系列的第三篇,也是最后一篇。文中将会介绍笔者几年教学积累的经验,主要面向 OI 从业者(特别是直接给初学者教授算法的讲师)。OIer 也可以阅读本文,并比对文中的方法与自己接受到的培训之异同,并相应地调整自己的训练模式。

  在最开头,笔者需要强调:如同第一篇文章所述的「学习算法」与「学习 OI」之割裂,「教好算法」与「带好 OI 竞赛」亦是割裂的。一个优秀的算法教师未必能带好 OI。第一方面,OI 竞赛生的水平往往远超自己的教练,教练是「巧妇难为无米之炊」——即使他拥有优秀的教学能力,也没有什么东西可以教给自己学生的了,只能依靠他们自学。第二方面,OI 是(不太纯粹的)奥林匹克运动,教练想要带出竞赛成绩,场外功夫比教好算法更重要。我们举个最简单的例子——一个教练如果拥有慧眼识人的筛选能力,经过五分钟的面试,即能判定一个三年级小学生是否有潜力在高一时进入省队:那他带出成绩将会容易得多。归根结底,「算法讲师」的工作目标是让每个学生学好算法;「OI 教练」的工作目标是让自己所带的大量学生中有几个人拿奖。这两个身份的工作目标是不一致的。

  本文只打算讨论「算法讲师」的工作——即如何给学生教好算法。编写本文之前,笔者查阅了这几年洛谷网校的学员问卷,统计到学员对笔者的赞赏主要针对以下几个方面:

  • 「讲解知识简明易懂,当场就能听明白」
  • 「讲课节奏恰当」
  • 「课件制作精美」
  • 「当堂写代码、注重代码习惯」
  • 「幽默感」

  接下来,笔者将会沿着这些特征,详细解释如何教好一堂 OI 课。

引导学生自己发明出要教的算法

  先提出一个问题,再引导学生一步步解决这个问题,最终让学生自己发明出要教的算法:以上是笔者之教学宗旨。这显然并非笔者原创,大量英文教科书都是这个路子;不过笔者贯彻这个方针十分坚决,故常常产出一些高质量的课程。这样做的好处是:学生对课堂参与度高;从一开始就知道主要任务,容易抓住本质;算法是学生自己发明出来的,学生在快要忘记的时候,只要略微回忆这个发明过程,立刻就能回想起各种细节。

  许多教程完全没有参考这个方案,OI Wiki 这类「维基百科式」教材尤甚。学生在利用这类教材学习时,最容易出现的问题就是抓不到主线,容易忽略重点;且理论性介绍多的情况下,学生读了后面忘了前面。此外,读这样的「维基百科式」教材,学生常常以「死记硬背」的形式记忆算法,过几个月他就该忘记了。

  普及组级别的算法,都可以想办法引导学生自己发明出来,无一例外。接下来笔者将结合几个实例,说说该如何在实践中应用这套方法。不过此前我们先看一个反例,这个反例是在教「模意义下的乘法逆元」时出现的。

……现在我们来讲乘法逆元。考虑一个集合 $G$ 和一个运算 $\oplus$,称 $(G, \oplus)$ 为一个群,当且仅当它满足以下特质:
- 封闭性:如果 $a$ 和 $b$ 属于 $G$,则 $ a\oplus b $ 也属于 $G$
- 结合律:对 $G$ 中的任意元素 $a,b,c$ , $ a\oplus(b\oplus c) = (a\oplus b)\oplus c $
- 存在单位元:$G$中存在一个元素 $ e $ ,使得对于 $ G $ 中的任意元素 $ a $ ,有 $ a\oplus e= e \oplus  a = a $
- 存在逆元:对于 $ G $ 中的任意元素 $ a $ , $ G $ 中一定存在一个元素 $ b $ ,使得 $ a\oplus b = b \oplus  a =  e $

如果一个群还满足交换律 $a\oplus b = b\oplus a$,则称其为阿贝尔群。
【反复讲解群的这几条性质,并带领学生判断 $(\mathbb{Z}, +), (\mathbb{N}, *)$ 等是否为群】

$(\mathbb Z_p, \times)$ 是一个群,所以可以通过乘以逆元的方式来完成除法。接下来我们学习逆元的求法,先说费马小定理……

  这样的讲解方式,毫无征兆地引入「群」的概念,学生在课程的前十几分钟内都没有领悟到群对当天课题之帮助。此外,对于第一次接触群论的学生而言,这样空洞的定义是不容易立刻理解的,教师往往需要多次重复讲解。这是典型的「维基百科式」教程,虽说字数浓缩了,但教学效率低,最终效果反而差。

  有趣的是,国内各个大学的自编数学教材,常常采用这种讲解方式。学生读这种教材,可以称为「啃书本」,即书本上的知识需要硬啃才能慢慢理解。这与《Introduction to Linear Algebra》等经典美式教材形成鲜明对比。

  来看一个更好的教学方案。笔者 2018 年高中毕业的那个暑假,给初中生讲课,采用了以下说法:

……以上,我们教完了模意义下加法、乘法的性质。为什么我迟迟不讲模意义下的除法呢?
模意义下的除法当然是存在的,例如在模 $10$ 意义下,$6 / 3 = 2$ 显然没问题。然而,$5 / 3$ 就出了麻烦——除不尽,但我们模 $10$ 意义下一共只有 $0\sim 9$ 这十个数,没有 $5/3$ 这个分数。

那么,我们要不要干脆宣布 $5/3$ 在模意义下不存在(或者说「没有意义」)呢?
大家来考虑 $(5/3)*12$,尽管最开始出现了分数(这是不被允许的),但是后来乘上 $12$,结果仍然是正整数,因此这个式子在模意义下应该是合法的。

这就出了一个问题:$5/3$ 不合法,但是这个结果乘上 $12$ 之后,又重新合法了。我们也许可以尝试找另一种方法去表示 $5/3$ 这个分数。

我们需要一种方法来「记账」。核心观点是:执行「除以 $x$」的时候,我们试着乘上另一个数(记账);等到日后重新乘上 $x$ 的时候,我们就能把数变回来,得到正确结果。
在有理数下,这是行得通的,我们执行「除以 $x$」,完全可以用「乘以 $1/x$」来代替。也就是说,对于有理数而言,这“用于记账的数”显然是 $1/x$;在模意义下是多少?我们又如何找到这个数?

先来看一个例子。
现在要计算 $5\div 3\times 12 \pmod{11}$,假如我们将「除以 $3$」视为「乘以 $4$」,于是答案是:$$5\times 4\times 12 \equiv 9 \pmod {11}$$另一方面,$5\div 3\times 12  =20$,$20 \bmod 11 = 9$。它们吻合了——把「除以 $3$」视为「乘以 $4$」可以给出正确的最终结果。

你可能怀疑这是一个偶然。让我来给出另一个例子。
现在计算 $3\div 7\times 56  \pmod{13}$,我们将「除以 $7$」视为「乘以 $2$」,于是答案是:$$3\times 2 \times 56 \equiv 11 \pmod {13}$$事实上,$3\div 7 \times 56 = 24$,$24\bmod 13 = 11$。它们又吻合了。

说到这里,你应该已经认同,模意义下跟有理数下一样,存在「记账的数」,乘以这个数就相当于做了除法。
对于一个模数 $p$ 和一个除数 $x$,往往能找到一个特殊的数。乘上这个特殊的数,就可以起到除以 $x$ 的效果。这个特殊的数,我们称为「模意义下的乘法逆元」。
上面两个例子中,$4$ 是 $3$ 在模 $11$ 意义下的逆元;$2$ 是 $7$ 在模 $13$ 意义下的逆元。

我们该如何寻找 $x$ 在模 $p$ 意义下的逆元?
类比有理数下的逆元。$x$ 的逆元就是 $1/x$,你发现一个数乘以它的逆元得到 $1$。那么你可以做些推测——
【等待学生找到性质】
模 $p$ 意义下 $x$ 的逆元 $\text{inv}(x, p)$,应该就是乘以 $x$ 之后得到 $1$ 的那个数。

我们的猜测是正确的。假设 $x$ 的逆元是 $v$,那么 $n \div x \times x$ 会被处理成 $n \times v \times x$,又因为 $v\times x \equiv 1$,于是 $n \times v \times x$ 正好等于 $n$。如果一个数乘以自己的逆元不等于 $1$ 的话,前面这条性质就没办法成立。

那么现在,请大家做个练习:寻找在模 $13$ 意义下 $5$ 的逆元。
【等待学生枚举出结果】

我们发现 $5\times 8 \bmod{13} = 1$,所以答案是 $8$。模 $13$ 意义下,「除以 $5$」就可以用「乘以 $8$」代替。
刚刚同学们通过枚举,找到了 $5$ 的逆元。不过,对于质数模数,我们有很快的方法去寻找 $x$ 的逆元。下面来学习费马小定理……

  选择不引入「群」的概念,是因为受众是初中生,他们目前是普及组水平,在较长一段时间内只会使用到模意义下的乘法逆元,无需接触其他群的逆元。另外,在课程中需要引导学生自己发现「一个数乘以其逆元应当等于 $1$」这条关键性质。

  我们再举另一个例子,这次我们引导学生自己发明序列分块。例子取自 2022 年笔者办的夏令营的第一课,不少学生在此时没有任何算法/数据结构基础,笔者以序列分块为例,向学员解释「什么是数据结构」。

大家来看这样一个问题:班上有 $100$ 位同学,学号为 $1\sim 100$。每位同学有语文考试成绩。
接下来要面临 $m$ 次询问,每次询问给出两个整数 $l,r$,问学号在 $[l, r]$ 区间的同学的分数之和。
如何解决这个问题?

来想一种最朴素的办法。每次询问,拿到查询区间 $l, r$,我们直接去数组里求和。
最坏情况下,每次询问都是问 $[1, 100]$ 同学的成绩 sum。那我们要执行大约 100 次加法。
有没有优化方法?提示:我们可以预先计算一些同学的成绩之和,记录在纸上。
【等学生说出「把连续的学生成绩之和记录下来」,例如记录 $1\sim 50$ 的同学成绩 sum】

现在我们来考虑这样一种记录方案——我们预先计算出以下 10 个值:
- $[1, 10]$ 同学的 sum
- $[11, 20]$ 同学的 sum
- ……
- $[91, 100]$ 同学的 sum

那么,当面临查询 $[37, 72]$ 时,我们如何利用以上信息来加速?
【等待学生说出最速求法】

想要计算 $[37, 72]$的sum,我们有 $$\begin{aligned}        sum = {}& w[37] + w[38] + w[39] + w[40] \\\\ &+ w[41\sim 50] + w[51\sim 60] + w[61\sim 70] \\\\ &+ w[71] + w[72]    \end{aligned}$$ 只需要把 4 个零散数、3个整块、2个零散数加起来。这比之前的直接求和快得多。

那么,现在同学们想一个问题:最坏情况下,我们要把多少个数加起来?
【等待学生说出正确答案】

最坏情况下,查询 $[2, 99]$。有 9 + 9 个零散值、8个整块需要相加。这比起朴素方法是一个很大的改进。

接下来,做一个思考题:如果共有 $10000$ 个学生,我们应该如何安排分块大小?
【等待掌握了均值不等式的学生说出正确答案。如果迟迟没有正确解,那么分块大小 100 也是可以接受的】

最后,来看看该如何修改一个学生的成绩。不仅要在数组里面改成绩,草稿纸上的预计算结果似乎也要修改。
【学生说减去原来的值、加上新的值】

好的,到目前为止,我们发明了「序列分块」这个数据结构。大家已经看到,数据结构是「组织数据的方法」,常常可以起到加速的作用……

  来看最后一个简单的例子,我们引导学生自己发明快速排序。

假设操场上一群人站在您面前,您需要把他们按照身高排序。
您可以这样做:
1. 随便选一个人,称为「哨兵」。
2. 比他矮的人站他左边去。
3. 比他高的人站他右边去。
4. 把他左边、右边的人分别排序。

显然,前三件事做完以后,这个人已经站在了正确的位置上。第 4 步是递归进行的。干完了之后,整个队伍也就有序了。这就是快速排序的核心思想。

举个例子。假设我们要排序 $[3,2,5,4,8,7,6,1]$:
1. 随便选个哨兵 $4$
2. 站队,序列变成 $[3,2,1] ~ 4 ~ [5,8,7,6]$
3. 分别排序,序列变成 $[1,2,3] ~ 4 ~ [5,6,7,8]$
因此,关键在于实现「站队」。只要能让比他矮的人站他左边去、比他高的站到右边去,就能实现快速排序。如何实现?提示:可以用一个辅助数组。
【等待学生提出实现】

  总而言之,笔者认为「引导式」的教学远优于「维基百科式」的教学。讲师应当控制好课程节奏,与学员多些互动。

  更多「引导式」教学例子见:

什么是动态规划(Dynamic Programming)?动态规划的意义是什么? - 知乎
0. intro 很有意思的问题。以往见过许多教材,对动态规划(DP)的引入属于“奉天承运,皇帝诏曰”式:…
KMP算法教程
KMP算法是一种字符串匹配算法,可以在 O(n+m) 的时间复杂度内实现两个字符串的匹配。本文将引导您学习KMP算法。

内容编排

  笔者一节课的内容可能包含知识点介绍、现场写代码环节、思考题这几个部分。其中,知识点介绍部分可以带领学员去学习新的算法和数据结构;思考题是知识点的补充,引导学员发现一些细节(例如,在讲完上文的序列分块之后,可以提示学生将整个序列分两块、分四块……进而推出线段树的基本结构;也可以提示前缀和,并要求学生指出前缀和处理单点修改的代价)。

  现场直播写代码是必要的。这一内容留到后面专门论述。

  有一部分 OI 教育者(常常是退役不久的 OIer)喜欢往初级培训中加入很多需要前置知识的高难度内容,最终造成选手听不明白课、却对教师十分崇拜的结果。这种倾向必须抑制。

  笔者注意到,有些机构的课程安排,缺失了「什么是算法」「什么是数据结构」以及「如何计算复杂度」这几个专门板块。古人言「纲举而目张」,这些基础概念应当在第一节课就教给学员。

教学节奏

  笔者的一贯风格是「等所有学生都学明白再推进内容」,若有人表示听不懂,则重新讲一遍知识。当然,依受众的不同,这个标准可以有变——例如,假设某教练对小学生进行培训,并在一学期后筛掉 70% 的人,那么完全可以在少部分学生听明白内容之后就推进进度。

  不宜进行长篇累牍的知识点教学。这中间可以穿插思考题和直播写代码等环节。此外,学生也能会在课上提出备课时未曾想到的问题,如果认为详细回答该问题对学生有很大好处,可以考虑压缩后续时间,讨论学生提的问题并加以引申。

  OI 授课经验较少的讲师容易在时间控制上出现问题。如果内容准备偏少,有一个简单的办法:准备过量的题目,并按授课时的进度,跳过一些题目,这样最终可以将时间控制在满意的范围。如果内容准备偏多,那确实没有太好的办法,可以考虑只讲基础性的内容,将拔高性的内容留作课后阅读。

关于直播写代码

  首先说一个观点:直播写代码不是炫耀技术。直播写代码是为了:

  • 解释算法中的细节,帮助选手更深刻地理解算法
  • 帮助选手养成良好的代码习惯,例如缩进习惯
  • 介绍一些较优实现,例如实现循环队列时保持 l, r 本身递增,只在获取数组下标时取模
  • 在写代码的过程中介绍一些坑点,例如滥用 define 的后果

  笔者一般在讲课前一天晚上先写一遍课上准备打的所有代码,第二天讲课时,把代码放在副屏上展示,而在直播主屏幕上抄写。这并非假吹、假弹、假唱,原因在于直播写代码不是炫耀技术,而是教学的一部分。一方面,如果直播时写错了代码,会浪费课堂时间在 debug 上(还有可能长期 debug 不成功);另一方面,学生通过观看教师写代码的过程,也能自己掌握这个算法的实现要点。如同演员不能因为自己演技好就不彩排,OI 讲师也不应该因为自己的代码水平高,就不提前准备代码。

  写代码应当按照逻辑顺序。笔者举一个例子:在写记忆化搜索的时候,笔者定义函数后,会先写边界情况、再写主体情况、最后加上记忆化,而非按照代码文本顺序从上到下写。这样有助于选手的理解。

  代码里面注释要到位,在写到关键逻辑时应当提示学生。讲师应当维持一个稳定的代码风格。

  讲师有责任帮选手选出一个鲁棒性佳的实现,来让所有选手都可以流畅且无 bug 地写出该算法的代码。例如,书写二分时,应当使用「l, r 差距大于 5 时二分,小于 5 时逐个判断」的写法。下面是一个「开根号向下取整」问题的二分实现例子:

void work() {
    ll l=1, r=1000000000;
    // 始终维持答案落在 [l, r] 范围内
    
    while(r - l > 5) {
        ll mid = (l + r) / 2;   // 二分

        if(mid * mid <= n)      // mid 猜小了
            l = mid;
        else                    // mid 猜大了
            r = mid;
    }

    ll ans = l;

    for(ll i=l; i<=r; i++)      // 差距小于 5,逐个枚举
        if(i * i <= n) ans = i;
    cout << ans << endl;
}

  再举一例。教快速排序时,笔者抛弃了网络上流行的双指针 swap 实现

void qsort(int l,int r)
{
    int mid=a[(l+r)/2];
    int i=l,j=r;
    do{
        while(a[i]<mid) i++;  //查找左半部分比中间数大的数
        while(a[j]>mid) j--;  //查找右半部分比中间数小的数
        if(i<=j)              //如果有一组不满足排序条件(左小右大)的数
        {
            swap(a[i],a[j]);  //交换
            i++;
            j--;
        }
    }while(i<=j);             //这里注意要有=
    if(l<j) qsort(l,j);       //递归搜索左半部分
    if(i<r) qsort(i,r);       //递归搜索右半部分
}
▲ 网络上流行的双指针 swap 实现

  之所以抛弃这个实现,是因为其鲁棒性极差,依赖于背诵。选手非常容易敲错一点点(例如把小于号敲成小于等于号,或反之),且难以 debug。

  笔者选择教学生写以下依赖于 tmp 数组的实现:

// 左闭右开
void quickSort(int l, int r) {
    if(l >= r - 1) return;              // 只有单个元素待排序,直接返回

    int flag = a[rand() % (r-l) + l];   // 随机取哨兵
    
    int p = l, q = r;       
    // tmp[l,p): 比 flag 小的;tmp[q, r): 比 flag 大的

    for(int i=l; i<r; i++) {
        if(a[i] < flag)
            tmp[p++] = a[i]; // 比哨兵矮的放在左边
        else if(a[i] > flag)
            tmp[--q] = a[i]; // 比哨兵高的放在右边
    }

    for(int i=p; i<q; i++)   // 与哨兵一样高的
        tmp[i] = flag;

    for(int i=l; i<r; i++)   // 覆盖回 a 数组
        a[i] = tmp[i];
    
    quickSort(l, p);         // 递归
    quickSort(q, r);
}
▲ 笔者推荐的实现

  这个实现好在:选手只需要知道快速排序的基本原理,就能自然地写出以上代码,完全无需背诵。

学习效率与自学能力的权衡

  培训机构可能希望学生自学能力长期不提升,以便学生依赖该机构提供的培训。然而作为负责任的讲师,应当努力帮助选手提升自学能力,从而为其将来的发展提供更多动力。

  如果教师在课上事无巨细进行讲解,学生可能也就懒于自学。但学生自学水平的提高是一个慢速的过程,应当进行有意识的训练。有些中学采取学生之间相互讲课的方法:教练指定下节课的教学内容,学生查资料之后分别上台讲述。在使用这个方法时,教练应当尽可能补充学生未讲到的细节。

  在培训机构上课的选手,若想提升自己的自学能力,可以事先预习下一节课的内容。

课件制作

  笔者 18、19 年使用 PowerPoint 制作课件,后来全面切换到 Latex Beamer。无论选择哪种软件,笔者都建议把公式写准确,并尽量避免整版文字。课件上的字应当是重点,技术性的细节可以靠口述。

  应当避免花哨动画,如 PowerPoint 的「蜂巢」「涡流」等转场效果。因为奇特的动画可能将学生的注意力从课堂上转移到课件本身,对学习没有帮助。Beamer 的使用者应该无需关心这个问题。

结语

  《OI 教育漫谈》系列文章至此更新完毕。希望对读者有帮助。


  欢迎读者来信交流,笔者邮箱是 ruanxingzhi@gmail.com 。