按:本文作者未经正式编程训练,数学底子也不牢,只是个野路子学习爱好者,自然逃不了“ACMer面前刷水题”的无力感,还请列位看官多多包涵~

何为Project Euler?

"Project Euler exists to encourage, challenge, and develop the skills and enjoyment of anyone with an interest in the fascinating world of mathematics."

ProjectEuler.net是一个好玩的网站!上面有许多数值计算题,比如小于一百万的数里面有多少个数在十进制下和二进制下都是回文数。从2006年(甚至之前没有独立域名的时候)开始,就已经有不少用户了;不过那时候我还没把学习编程提上日程……

解法不限语言,不限代码复杂度,用户只需要提交数值答案即可。如果答案正确,则用户可以进入该题的讨论帖,看看其他人对题目有什么分析,用了什么解法,写了什么代码。

这就意味着提供了一种以问题为导向的编程学习方式

Project Euler面向什么样的用户呢?

平时上课无法满足求知欲的学生,不是学数学出身的成年数学爱好者,希望不断磨砺解题能力和数学水平的职业人士。

从公开的数据来看,目前似乎使用C/C++或Python的用户最多,不过在论坛里,Mathematica、Haskell、APL甚至汇编等等也都很抢眼,当然还有最最风骚的Pencil/Paper。

网站有等级和勋章系统,每答对25题升一级,还有奇奇怪怪的勋章(比如解出第3、14、15、92、65……题可以获得As Easy As Pi成就),算是小小的激励和乐趣吧。不过最大的乐趣和成就感当然还是来自解题本身!

从何处下手?

两条原则:

  • 一般来说,成功解题的人越多,就说明题目越容易;但是难易定义是相对的。
  • 一般来说,题号越大,题目可能越难;但是题目难度并非严格递增,比如说第357题其实非常简单。另外有些题是有一定关联的,比如多边形数的题目就有好多道,连分数的题目也是,循序渐进会轻松一些。

做题步骤大概就是审题,想清楚题目设定,从简单情况推一下看看有什么结论,考虑遍历顺序什么的,然后有些简单题可以笔算,有些题需要编码。最后,提交答案,哦也!

我一般会提前读好几道题,在脑袋里面放着,有时候走在路上灵光一现,没准就有思路了。当然跟读完题就有清晰思路的大牛没法比……

智商不够,暴力来凑

大部分题目看起来都可以直接写出穷举的暴力解法,有些题目也确实可以这样解决。但是咱对P/NP问题还是有点概念的,这样硬算有可能一辈子都算不完。所以请务必注意!题目设计有个所谓的“一分钟原则”:

设计出一则成功的算法,可能需要花掉好多个小时;但是有了高效的实现,那么靠谱的机器应该能在一分钟内求出解来。

数学是基础,暴力是辅助。一方面,磨刀不误砍柴工,复习算法+学点数论、图论、组合知识才是王道;另一方面,如果一分钟算不出来,说明你的设计八成不太靠谱……

当然了,对于我这种时不时智商捉急又无法充值的人来说,有时候只能勉强把代码优化到可以跑出结果的地步(有的题跑过几小时我会说么),再去论坛里观摩高手的做法……

不会做,肿么破?

有时绞尽脑汁也没思路,写了一堆循环,仿佛根本没办法在有生之年算完;或者好不容易写出来了,怎么算都得不到正确答案。

恭喜你!这说明你有机会学到新东西!

在这种情况下,官方给出的hint是:

非常非常仔细地读题,尤其是仔细观察给出的例子。用纸笔演算一番,试着体会题目背后的思想。如果不熟悉这些思想,上网搜索或者查阅图书,补补背景知识;仔细读题就会知道应该查什么东西。写个程序,试试看能不能搞定简单情形,输出是不是符合示例;如果顺利,你就知道自己确实理解了题目,没走错方向。然后,试着推算求解原题所需时间。假如远远超过一分钟,那么请重新考虑解题策略。

作为一只小弱,我再补充几句:

  • 仔细审题!有时候题目表述可能有点问题,比如第17题(数字单词字数);有时候边界特殊情况需要谨慎考虑。
  • 搜索知识,不要搜索答案!比如跟某些数列有关的题目,答案或许可以直接搜到,但是这有何意义呢?如果要搜索,不如看看这个数列有什么数学性质可以用吧。
  • 会做的题目也要看看讨论,看看自己的方法能否进一步优化,说不定你会发现神奇的技巧。
  • 至于直接抄代码什么的——你确定真的要剥夺自己Eureka的乐趣吗?!
  • 存几个常用数表备用(比如N以内的素数表)。
  • 对于各种复杂度的运行时间,大概有点概念。
  • 找本OI教材,上手或许较快。

最重要的……

现在,Project Euler有超过35万注册用户解出至少1道题,其中解出3道题的人大约16万,但解出25道题成功升级的就只剩下不足6万了,而这6万人大部分一直停留在Lv. 1。作为刷到Lv. 3的Python小白,甚感欣慰(咳咳)……

这样的数据当然毫不令人意外。

每当有人写东西介绍Project Euler,总会引起一波注册热潮,但是这样的鸡血有多少后劲呢?你大概还记得有个妹子180天做180个网站自学编程的故事吧。当时你是不是也蠢蠢欲动、准备学coding来着?然后呢?

别忘了那个已经走上码农之路的妹子说的:Start small & keep building!

以上!