程序、竞赛与算法

《程序、竞赛与算法》是老文章，里面讲的内容基本过时，没有什么意思。重新放出来是希望大家记得，在我们的CS学院，ACM竞赛是很牛逼的事情。--作者注

---

2013年左右，笔者抽空关注了一下某些程序设计竞赛的书。我是竞赛盲，没有参加过任何程序竞赛，不过我就喜欢折腾、瞎想，顺便也与几位搞过ACM竞赛的同学探讨相关问题。

首先，我找来某同学推荐的《挑战程序设计竞赛（第2版）》（ 作者: 秋叶拓哉 / 岩田阳一 / 北川宜稔 出版社: 人民邮电出版社 译者: 巫泽俊 / 庄俊元 / 李津羽 出版年: 2013-6）翻看了一下，挺有意思。加上我之前买的刘汝佳的几本竞赛书，我对程序竞赛有了一点点认识。我就想，一本讲竞赛的书与一本算法书有什么区别呢？比如，《算法导论》？

挑战程序设计竞赛（第2版）

然后主要是针对《挑战程序设计竞赛》和《算法导论》进行了一些比较。我发现，从内容的组织上它们有非常类似之处：从基本的数据结构出发（堆、栈、树、图），讲解一些基本的算法，然后贪心法、回溯法，进而动态规划，网络流，计算几何，再加上一些数学知识，主要以数论、组合数学为主的知识。尽管类似，但是又有非常明显的区别。（《数据结构》、数论、概率等本身就独立成课，使得分析下去会更复杂。《算法导论》有数据结构的内容，但显然这部分内容并非必须。）

主要体现在，竞赛书的讲解主要针对特定的题目，强调技巧和程序。算法书针对已知问题（难题），强调准确性、系统性和通用性。我列表如下，其中有些结论我心目中不是那么武断，只是写下来就成了这个样子，大家可以探讨：

           目标       系统性  理论性  技巧性   关注点    趣味性  学习要求
 算法学习： 学科训练     强      强     较弱    通用难题   较弱      高
 ACM竞赛： 比赛        较弱     弱     强      特定问题   强        高

注：难题，我指的是理论上准确定义的无高效算法的那一类问题。有了准确定义之后，世界上就只有一种难题。特定问题，我想说，它们是被设计出来而且必然有答案的“玩具”题，对很多人也许很难，但本质上一定是“容易”的问题。

以上比较还没涉及另一个关键词：程序。竞赛培训书都会讲一点编程，一般也会分析不少的代码，而算法书大多是用伪代码，而不会讲程序。值得注意，竞赛书会涉及编程，但又绝不能替代程序设计的入门教程。所以，我这里列出了三个关键词：程序、竞赛和算法。恰恰竞赛就在“程序”与“算法”的中间，是利用程序和算法思路去解题。竞赛当然需要高IQ、丰富的想象、高超的技巧和有针对性的强化培训。值得注意并且我想强调的是，竞赛训练并不能替代编程的训练和算法的学习。希望通过程序竞赛来进行程序和算法的学习，或者寄望其可强化学习或作为高阶训练，就显得有点不切实际。

计算学科发展这么几十年，在基础科目上都有非常专门的训练内容。请大家记住这一点，也许你缺乏这些训练，只是你缺乏，而不是教学内容上缺乏。而且这种训练绝不能用竞赛的训练来替代。对此缺乏足够认识的同学将要碰钉子的！如何有针对性地进行学科训练则不是本文所讨论的问题。

总之，我现在的建议是：竞赛本身是非常有意思的活动，它帮助了程序设计的训练和算法的学习，激发了同学们的学习兴趣，也有助于培养学习能力、交流能力、团队精神，值得提倡。但是竞赛不能替代编程与算法的学科训练。编程与算法是计算机学科的两大基本学科内容，是必修的基础科目，需要系统地强化训练与学习。

2017年7月6日整理