前几天,秋叶拓哉(iwi)、岩田阳一(wata)和北川宜稔(kita_masa)所著,我(watashi)、庄俊元(navi)和李津羽(itsuhane)翻译的《挑战程序设计竞赛》,终于通过人民邮电出版社正式出版了。可喜可贺,可喜可贺。有关该书的简介,目录、试读和购买链接请通过传送门访问。这里我主要想说一下自己为什么要翻译和推荐本书,还有对程序设计竞赛学习资料的一些看法。也附带一些对译者序和第1章的补充说明。

在译者序中我也略谈到了自己翻译此书的动机。和很多读者一样,最开始当然是奔着作者的名头去的,三位作者不但是国际知名的选手,而且TopCoder的最高rating加起来都破9k了。顶尖实力的作者往往可以站在更高的高度指点江山,也就更可能写出一本好书。随后就是读到书中的内容了,书中的绝大多数东西,我大概都在过去四五年时间的摸爬滚打中,逐步通过各种书籍、网络、道听途说、解题经验和总结体会掌握了。不过还是有一些耳目一新的内容,其中有一两个问题还是通过邮件得到了原作者的解答,涨了姿势。但仍有一种相见恨晚的感觉,假如自己早两年读到此书,想必能少费不少劲。从我个人的经历和对周围同学的了解来看,这是一本非常值得引进和推荐的书。

当然,在此之前国内已经出版有不少算法竞赛相关的书籍了,很多人想必希望知道这本书有什么特别之处。算法竞赛相关的书籍大致有两类,一类是算法和数学类的书籍,比如各种数据结构教材、离散数学教材、《算法导论》、《具体数学》等,一类是专门针对算法竞赛的书籍,其中的代表就是刘汝佳所著的几本书,而《算法艺术与信息学竞赛》(黑书)又是其中的代表。作者之一的iwi在MSRA实习期间也得知了黑书的大名。

首先,个人觉得这些书籍大致可以分为两类:教科书和工具书。诸如《数据结构与算法分析》(DSAA)之类的书可以作为教科书的代表,而诸如《计算机程序设计艺术》(大名鼎鼎的TAOCP)则毫无疑问是工具书的代表。大致地说,前者简单易懂,适于学习,后者高深全面,适于参考。二者并没有明显的分界线,很多时候全凭主观,因人而异。比如说,看懂了,这就是教科书,看懂目录了,这就是工具书。当然,和数学沾边越多的书,总是越难啃的,所以就难度而言,这类书籍和编程语言类书籍自然是没有可比性。

许多书都作为程序设计竞赛的学习资料被反复推荐,但事实上,我们大概可以仿照《最常被程序员们谎称读过的计算机书籍》写一篇《最常被ACMer们谎称读过的书籍》的吐槽文。里头有一句话很重要,所以我再抄一遍:“如果你自己没有读过这些计算机书籍,请不要推荐给别人”。当然,像《算法导论》这样的书个人觉得还是值得一读的,多数的章节并不难,可以当作教科书,后面的一些内容可以作为工具书需要时再参考,里面很多东西讲的很细,容易做到真正的理解吸收,比如从自动机引出KMP等等。而TAOCP则无疑是最常躺枪的装逼神器。有一天,我在同学的桌上看到一本TAOCP第一卷,打开一看很黄很暴力,我赶紧就把它盖上了。TAOCP很厉害,看exponentiation by squaring能引用到它,看permanent也能引用到它,连看数え上げお姉さん都能引用到它。读完TAOCP那必须能变得超厉害了,可那得是能读完啊,读不完说啥都白搭。所以推荐学习资料不能光看书好不好,还得看对目标人群合不合适。而一本好的教科书,不应该是尽可能体现作者有多牛,而是要能够尽可能简单地帮助读者变得更牛。如果看完了,懂的还是懂,不懂的还是不懂,那是没有意义的。

按照这个分类标准,个人觉得《挑战程序设计竞赛》是一本很好的教科书。它非常的适合作为有志参加程序设计竞赛的同学自学,或是正在学习数据结构与算法分析的读者作为练习和拓展的参考书。该书将不同的主题按难度分成了三部分,循序渐进。作为教科书,其一个明显的特点是,几乎没有外链,把每个的主题都讲得很清楚,便于读者理解。多数题目附有核心代码,代码风格也不错,而且讲解的时候会附带一些思路的说明和方法技巧的总结。它在正文中详细完整的介绍了在程序设计竞赛中最重要的知识和思想,全书涵盖了在绝大多数题目中所会用到的知识和思想。而对于拓展内容则以补充说明或是附录的形式给出,并未多做介绍。这样的好处是该书很连贯,结合练习容易完整掌握,并突出了对大多数人而言更为重要,应该多花力气的地方。

在此举几个例子。书中介绍一般图匹配的时候并没有介绍经典的带花树实现,而是介绍了利用Tutte矩阵求匹配数的随机算法。因为要在书中真正把带花树的实现给读者讲清楚很困难,而对Edmonds算法的介绍资料也很多。在介绍后缀数组的时候,用的也不是线性算法,因为后缀数组最重要的是理解其性质和应用,而求后缀数组往往是模板的工作。在介绍字符串上的动态规划算法的时候,没有介绍KMP算法和Aho-Corasick算法,而是用暴力的方法求出了二者所对应的状态和转移,事实上这反而更有助于真正理解KMP算法和Aho-Corasick算法。

另一方面,如果你是想要学像弦图、动态树、Dancing Links(DLX)之类的高深玩意的话,这本书对你就几乎没有任何帮助。当然,说到DLX,我不知道为什么国内会曾经有一段时间盛行出DLX的题,题目的规模大得惊人,能AC的原因却是因为数据太水。真正理解DLX的人应该明白,这本质就是一个常数优化的启发式搜索,并不能改变问题本身的困难程度。从某种意义上说,在把基础搞扎实前,还是少折腾这些高深玩意比较靠谱。

相比较而言,刘汝佳的《算法艺术与信息学竞赛》则介于教科书与工具书之间。书中按专题介绍了了相当多的知识,从头到尾许多小节都涉及到非常难的内容,还有一些神题。书中所提及的算法和数据结构要比《挑战程序设计竞赛》多得多,特别是计算几何部分要更为系统详细。书中包含有大量的外链,非常可惜的是OIBH早在多年前就挂掉了。书中对很多问题进行了总结归纳,但不都有详细的讲解介绍,对于身经百战的读者很容易找到共鸣,但对于其他读者而言,恐怕读起来就不那么轻松了,很多地方需要自己钻研,另找资料学习。黑书是可以多读几遍的书。起初可以在短时间内接触大量的算法和技巧,然后通过其他资料学习。遇到某个有印象的问题,或时隔一段时间后,可以再翻开看。慢慢地,就会对书中越来越多东西有共鸣了。

当然,从最初阅读《算法艺术与信息学竞赛》,到去年翻译《挑战程序设计竞赛》,我自身的实力也已经不可同日而语了。所以上面对于两书的评价,当作两个不同的人做出的应该会更为客观一些。

冰冻三尺非一日之寒。虽然书中的内容已经足以让读者的rating冲上2500,但真要达到2500的实力却还离不开充足的训练,通过实践把书中的内容真正化为己有。另一方面,训练的方法也是很重要了,好的方法能够做到事半功倍。正如《挑战程序设计竞赛》最开始所说的:程序设计竞赛是综合了以下两个要素的复合竞赛:

  • 设计高效且正确的算法
  • 正确地实现

并且,为了设计算法:

  • 灵活的想象力
  • 算法的基础知识

也是必不可少的。平时训练过程中切莫顾此失彼。


Q&A

Q: 能找作者/译者签名么?

A: 如果我们有机会见面的话,而且你居然还不嫌我的字丑的话,是可以的。由于我和另外两位译者马上就要分处三个不同的城市了,能不能集齐就得看RP了。如果你参加今年的TCO的话,我们到时候还可以去搭讪iwi和wata要签名。

Q: 卖出一本书你能抽成多少?

A: 0. 我们拿的是一笔稿酬。所以如果你买书的目标是给我钱的话,不如直接一点,打开支付宝。我会很开心的。

Q: 为什么黑Knuth?

A: 呃,虽然文中黑的两个东西全是Knuth搞的,但我绝无黑Knuth的意思,恰恰相反,我黑的是那些亵渎Knuth作品的人。比如建议你想要进某社先把TAOCP读个几遍啊,或者把DLX当万金油使的这类人。

Q: 《具体数学》怎么样?

A: 说来这又是Knuth搞的东西?《具体数学》可以算不怎么简单的教科书。里面许多内容还是可以看得津津有味的,但是有些地方就看着有点费劲了,里面那两页求和公式“简单的例子”当初可看死我了。《具体数学》系统地介绍了许多有用的数学工具,当你遇到过几类数学相关的问题,并开始觉得自己不会数数,不会算概率的时候,就很有看一看的必要了。

Q: 更上一层楼的练习方法。

A: 《挑战程序设计竞赛》也有这么一段,这里做一个补充。一是近年来Codeforces得到了很大的发展,其功能丰富,用户群也很大,是一个很好的练习平台。二是SGU也是一个老牌的OJ,其题库比较精简,且质量比较高,不会像其它OJ有刷不完的题,因此比较推荐。学习算法的时候,可以找一些相关的题做,巩固知识。练习的时候,不应该跟着解题报告做题,而是要尽量独立思考,否则“灵活的想象力“恐难有提高。同样的,不要在“神模板”和“神题”上走火入魔,而忽略了“算法的基础知识”。

Q: ….

A: 如有其它相关问题,欢迎留言。

71 Responses to “《挑战程序设计竞赛》推荐及算法相关书籍吐槽”
  1. 1169158401 says:

    这本书有没有勘误表的网址链接?

  2. watashi says:

    orz

  3. crazyshark says:

    额,LZ提到《具体数学》,我想问一下这些种类的书的中文译本应该不会和原著差别太多吧。是不是就一定要读原著啊

    • watashi says:

      我想大多数的技术类的书籍都不是非读原著不可的。
      个人的感觉的话,算法和数学类的书籍如果有好的中译版本,看起来减小不少阅读障碍,当然如果翻译质量不过关就反而会增加阅读障碍了。
      编程语言和工具相关的书籍,我比较偏好英语的。一是比较新的书或者不那么大众的东西未必有好的中译版本;二是这类书中的英语读起来也没什么障碍,三是即便书有中文的,大多数的文档都没有质量合格的中文版本。

      • sevenkplus says:

        我认为读原著有阅读障碍是因为英文水平太低,而不是读原著的问题。如果连数学书的英语都觉得困难,可能应该先学习英语。
        虽然确实不是“非读原著不可”,但是翻译永远比原著要差一些。

        • watashi says:

          我指的就是不习惯英文表达带来的阅读障碍吧。数学里很多东西中英文的表达挺不一样的,有时候看到证明里超长的一句话感觉还是有点绕的。
          “翻译永远比原著要差一些”有点绝对了吧,毕竟神一样的书也不多,多少都有点可以改进的地方。有时候看到某句英文的证明,就觉得换中文可以说得更简短清楚。某些上古时代的书,作者都可能都已经挂掉了,译者还可以作一些补充。

  4. loobin says:

    谢谢,watashi大神的这本竞赛书,目前感觉是相当赞的,原因就不说了,谁用谁知道。。。
    其实我现在已经不搞ACM了,但是出于对ACM的留恋以及对您的崇敬,买了这本书,看了后真的受益匪浅。求大神邮箱,可不可以发我一下。
    不胜感激。

  5. 与星独白 says:

    已入!

  6. [...] 本文转自《挑战程序设计竞赛》译者巫泽俊的blog:http://blog.watashi.ws/2382/pccb-etc/ This entry was posted in 默认分类 and tagged 出版, 数据结构, 算法, 类, 计算机 on 2013/07/16 by ttsgs. [...]

  7. figo says:

    马上就要拿到书了,满满的期待啊。。。

    shi哥你是怎么精通那么多种语言的(尤其是haskell),总觉得你有用不完的精力啊~

    • watashi says:

      我称得上非常熟练的语言应该不多的
      C++(绝大多数人都不敢说自己精通C++语言吧)
      Perl(应该比很多人要了解得多,做过一些深入了解)
      Ruby(能写出很漂亮的代码,但是对某些实现机制未做过深入研究)
      Haskell(Real World Haskell讲得非常好,结合Haskell Wiki)
      Java最多算半个
      C#, PHP, Python在工作中使用基本都没有问题,有一定了解和工作经验,但称不上精通
      其他大多是通过一两本教程学过,但不太常用,写的时候可能还需要比较多借助文档的了

  8. yomean says:

    同求电子版呀,希望可以快点出电子版。

  9. ragnlang says:

    跪求博主跟出版社商量一下卖电子版吧,纸质书太占空间而且不方便携带啊

  10. 1169158401 says:

    我想问下:
    有人说,奋斗的意义不在于结果,而在于过程。。。
    问下你在ACM的过程中收获了什么呢?
    如果当初给你不搞ACM,会做什么呢?

    • watashi says:

      其实主要的收获在两方面:
      1. 通过大量的算法题训练,锻炼了逻辑思维和写出漂亮代码片段的能力
      2. 结识了不少优秀的浙大学长和外校同好
      当然,借着各种onsite比赛的机会,也增长了不少见识

      至于不搞ACM会做什么,那就说不准了,太yy了……

  11. aa2985759 says:

    大三快大四了,决定再搞一年ACM,目标rating2500↑。希望能完成小心愿。期待在珠海要到您的签名,哈哈

  12. Jackie says:

    您的博客可以加一个回到顶部的按钮吗?

  13. Yular says:

    Shi哥~去哪里工作了?

  14. winguse says:

    虽然工作了,但是还是买来看看。shi哥这个blog让我已经学到好多了,衷心感谢!

  15. aaahexing says:

    预感您的支付宝要爆……我觉得您直接淘宝开个店,兜售各种有亲笔签名的算法类书籍会很有钱途~.~

  16. Navi says:

    真的是一本不错的书,希望越来越多人喜欢 =w=

  17. 1169158401 says:

    对于大三即将大四毕业的,并且以后从事IT ,编程方面的工作,这本书对于以后的职业生涯有什么帮助么?

    • watashi says:

      对绝大多数参与工程开发的程序员而言,学习算法恐怕没有那么明显和直观的帮助
      大多数领域并不会涉及多少这类算法的设计,只要具备选择合适的数据结构的能力就足够了

      不过通过练习编写解决复杂算法问题的代码,对锻炼思维和写出漂亮的代码还是有帮助的
      所以个人有兴趣的话,可以钻研一下
      但是没有兴趣,纯以为未来工作准备的话,视工作应该有很多更合适的书

      类似的,熟练掌握算法在面试中应该会占点便宜,但真要比较扎实的掌握,时间上的投入是少不的
      而纯粹以面试为目的,又有另一些(我不太喜欢,乃至比较反感的)捷径

  18. loying says:

    到时看看==

  19. 名字还是不说了 says:

    来抢个座……前排Orz,球问NOI – Ag~Cu水平的看这个书合适嘛?

    • watashi says:

      难说,按我对浙江大学集训队的了解来看,以Regional成绩大致为标准
      Au看起来应该会很轻松,也能有所收获,时间成本不高,就看愿不愿意花书钱了
      Ag~Cu我个人比较推荐认真看一下,可以系统的学算法,也可以检验学习进度
      Fe的话,可能还要加以结合C++, STL和DSAA的一些基础书籍学习

      没有参加过OI,所以只能拿我比较了解的情况来做类比了

  20. 鲜崽 says:

    虽然水平不在一个档次,但是充满了共鸣耶!

  21.  
Leave a Reply