两周前看到“推荐几个好玩又有难度的编程网站”这篇文章,对里面提到的几个编程网站都进去看了一下,明显对作者首推的Project Euler(http://projecteuler.net/)编程网站很有兴趣——“一分钟原则”、只要求结果正确、都是描述简短明了的数学题。下面会给出个人认为Project Euler更有意思的特点。
比ACM OJ要求少、题目类型单一、任意语言实现
我曾经在ZOJ(浙江大学ACM在线评测,英文题目)、zjut(浙江工业大学ACM在线评测,中文题目)两个国内比较突出的ACM编程网站分别做过前面简单的那么20来道题目,花了不少时间。
当时是刚开始接触并尝试ACM题目,做的都是前面偏简单的入门题目,但却花了大部分时间在反复详细阅读较大篇幅的题目描述、检查并调整结果输出格式、猜测可能被忽略的关键点、注释掉调试语句、“试图”用网站上不同的编译器(只能用C或C++)提交代码...
然而上面这些让我感到繁杂(其实也是更锻炼做题者)的特点,在Project Euler中不复存在,原因在于Project Euler全部都是“mathematical/computer programming problems”,题目描述简短明了,并且只需要你输入唯一正确的答案、输入验证码,点击提交即可——不管你用什么方式(手工演算推导、各种编程语言)得到答案(当然搜索现成的答案一点意思都没有!)。
具体介绍请参考about页面(http://projecteuler.net/index.php?section=about),摘取其末尾一句话——“Project Euler exists to encourage, challenge, and develop the skills and enjoyment of anyone with an interest in the fascinating world of mathematics.”
推荐像我这样子“非职业的”ACM参赛学生通过Project Euler练习编程技能、锻炼思考/分析能力。
论坛讨论、官方解答
一旦你提交的答案通过,Project Euler会给出该题目的论坛详细记录,里面是以前解题者的思路、方案、讨论、实现的详细信息,你能够在这里看到大家用各种“莫名其妙”的编程语言(汇编、APL/J/K...)的完整实现,或者一些思路的交流,以此来完善你的实现、吸收更妙的思考、解法。
此外,部分题目通过后还会给出“官方解答”(一个针对该题的PDF文件,可下载),里面主要是一些推导、伪代码实现、参考链接等。
因此,你完全可以自己用“蛮力法”求得正解之后作为“敲门砖”,提交通过获得上面所述的“福利”。一位外国软件工程师在这里也说“can be either solved by a simple brute-force approach”,同时也推荐他的这个博客。
实际上,目前我完成了的30几道题有一部分就是通过简单直接的解法得到答案的,想要改进时再到论坛去认真转一转,肯定会收益不少。
题目总数与发布
对了,目前Project Euler*有340道题目,大概每周发布一道新题。你可以按照ID(发布时间)、difficulty(solved人数)对题目进行升降序排列,方便查看。
我的操作方式与一点点体会
正因为题目描述简短,我用手机上的UC浏览器保存了details of all problems页面,在食堂、车站排队无聊时拿出来理解一道题目,然后思考一下找寻解题思路,回到宿舍再在草稿纸上画一画,最后才写代码实现求解。
还记得我在Problem 18的递归解法中的bug就是我早上起来刷牙时突然想到的(归功于前一晚睡觉前也纠结了一下这个bug)。我想这也是“暗时间”的利用方式,而且思考能够避免焦虑,不会去想今天食堂怎么这么多人排队 ; )
Project Euler只要求唯一的正解,于是我用简洁而强大的Python(初学者)来写代码,这篇文章“*为什么要开发Ruby”提到Ruby不做明确的数据类型定义,不必要的声明都可以省略,可以专注于算法。我想这对Python也是一样的,都是动态类型的脚本语言,在解题方面效率的确是高很多。当我不知道Python中有chr()与ord()这两个char与int互转的内置函数时,改用Java实现时有多少似嫌多余的代码啊。很明显我也因此越来越喜欢上Python了 ; )
说来也真巧,我又看到与最前面那篇“推荐几个好玩又有难度的编程网站”同一作者赖勇浩前辈的另一篇文章——“使用 Python能延长你的生命”。
一直都是按ascending order of difficulty(solved人数)从易到难做题的,认为别人能做到的自己也应该努力做到,但是发现其实有些solved人数少的题其实也并不比当前solved人数多的题更难。于是觉得别人没通过的题不一定代表了自己也没能力解决,对别人容易的题目自己做起来也不一定简单。归根结底这是一个坚持与积累的过程。
我的不足
在两周多有趣的解题过程中,渐渐地发现了自己的一些坏习惯,应该重视并改掉。
1、习惯长期纠结于某道已经有思路、写了代码却得不到正解的题目而不愿意放下,实际上这样子时间、精力都耗费得更多。这种时候尝试一下另一道题或者刚才放下隔两三天再回头思考更有益,例如又是用到递归的Problem 24。
2、虽然说用Python实现更加简洁,但也更加随意,因此存在“巧合编程”的习惯,循环计数改为+1或 -1。而且几乎没有写注释,趁着解决的题目还不多,要考虑整理一下所有脚本代码放到google code上去。
Project Euler其他有趣的特点
看下图以及其底部的note(http://projecteuler.net/index.php?section=scores),要完成100道题才能称得上Novice(初学者、入门者)Level 3级别啊。看起来我才Level 1就在这里吵闹真是...坚持啊积累啊!
下图有当前登录者的解题数量进度条(进度条能让你明确到了那个阶段,不至于打击你的自信与动力),到底是新题发布得快还是我们自己解题速度更快呢?一点一点慢慢赶上吧。
在Statistics(http://projecteuler.net/index.php?section=statistics)页面中,统计了各个国家的注册用户与编程语言的使用情况。美国有15843 注册用户,中国是其1/9有1686,粗略一看,排得上前五了。另外有53种编程语言被使用了。个人觉得稍微看看这些信息还挺有意思的,希望越来越多的同学们在Project Euler注册开始解题啊。
最最后一个疑问?
Euler是啥意思?哈,我又很巧地在经典之作 《概率论及其应用》的人名翻译对照表中看到“尤拉”这个名字,数学家来的,上上面那张头像是也,上 Wikipedia 查查吧。
本文出自 “蚂蚁” 博客,请务必保留此出处http://haolloyin.blog.51cto.com/1177454/577664