星海's Blog

老头初学编程
C未解决的问题

转贴:projecteuler vs ACM and the path

星海 posted @ 2010年10月20日 09:23 in Python学习 , 1553 阅读

转自

http://sgxiao.blog.163.com/blog/static/119937386201032211218977/

 

最开始接触projecteuler也就是几个月前看到laiyonghao大大在2008年发表的一篇博文《推荐几个好玩又有难度的编程网站》。projecteuler是其中第一个网站,也是我认为可玩性最高的一个网站。直到目前为止,中国大陆有1098个账号在上面活动,而用户人数最多的国家是美国,有11550个。这样的结果并不符合一个负责任大国所应有的表现,因此很有必要继续赶英超美(单英格兰在这天就有2267人)。

 
即使对于一个ACM弱鸟来说,projecteuler的模式也不会显得陌生,就是给出一问题,然后由你来进行求解。如果 正确,则你的排名就会上升,这样是一个相当有成就感的事情。当然,两者之间仍然是有一些不一样的。
 
  1. 首先,两者的提交内容不一样。ACM类型的网站需要你提交编写好的程序,上传好了代码之后在服务器端编译和进行judge,只有当你AC了之后,这个题目才算通过。而projecteuler则不一样,它只要求你提交答案。对于题目类型比较偏重数学的内容来说,projecteuler的设计自由度更大。
  2. 其次,限制程度不一样。ACM需要提交程序,自然对程序的运行时间和消耗的内存大小也有一定明确的限制,这就要求你对于某些蛮力无法搞笑解决的问题要学会变通,要求更高。而projecteuler允许你不局限于某种具体的编程语言,而是鼓励你用更多的方法来解决同一个问题。有人用C++,Java,python等等流行的程序语言语言。还有用php,perl,ruby,javascript等等流行的脚本语言来解题。更有出于装B或者是其他不可告人的目的而采用汇编来解题的:-)。总之答案是丰富多彩的,解决的途径自然也是丰富多彩的。
  3. 网站排名对人的影响不一样。玩ACM的时候,我总是想方设法的想刷高排名,所以在自己写不出代码的时候,也会想方法找到高手的代码,看懂然后提交来争取排名靠前。projecteuler则不一样,由于很多solution类型的网站(如 http://code.google.com/p/projecteuler-solutions/)的出现,你想刷的话,一天之内大概就能刷到第一名了,这样盲目刷分反而变得没意义了。因此我更喜欢把题目搞明白,代码运行清楚了,才把代码提交上去。
说到要把题目搞明白,除了自身的努力之外,不断的参考和学习很多不同的内容自然是少不了的。学习的途径自然有不少的。这个过程非常强调动手的能力,只有在动手的过程中,你才能学到更多深入的东西。例如,素数(primes)这样的概念,在中学甚至是小学的时候就有接触过。并且做projecteuler的题目的时候也会经常遇到跟素数相关的内容。能够把经常使用的某个范围的素数找出来,就显得很有必要了。

  要解决这个问题,首先就是要动手去搜索。我搜索到了 1000以内的素数表 ,很快自然也搜到了 10000以内的素数表 ,紧接着,我还能找到 列有 1000000以内的素数表 这样的乏味的blog内容。直到1后面出现了7个0,这才开始没有直接的答案可用。

  于是就被迫开始写代码了。我从最基本的暴力穷举的方法开始尝试,编写一个叫做素数生成器的C语言程序,直到感觉性能实在是太慢了的时候,就又开始找其他的方法了。云风在他的著作《我的编程感悟》讨论优化的问题时,也对上述问题进行了一个简单的讨论。其最终采用的方法,叫做埃拉托色尼筛子算法,是以欧几里德同时代的数学家埃拉托色尼命名的方法。这是可知的已经非常高效的方法,至于具体的实现,我会在以后的文章中探讨。

  除了上述搜索进而动手写代码的方法外,多参考别人的材料,学会站在巨人的肩上往往能达到事半功倍的效果。http://dcy.is-programmer.com/ 这个blog比较适合初学者,里面对前40题都有完整的python代码,适合那些希望写出精炼切高效代码的人。而 http://blog.skainet.net/ 是我发现的一个对每个题目都有比较详尽解释并且提供不同代码的blog,这里的题目比上一个更加深入一点,确实非常值得参考。
 
最后,学习自然也还是不能离开书本。《具体数学》(<concrete mathematics>)是我比较推崇的一本,里面有专门的一章讲述素数的各种有趣的特性。唯一不好的地方就是此书门槛较高,适合数学基础比较好而且英语也还不错的朋友,不过目前国内已经有中文的版本,大家上网搜搜就可以知道了。这样的书,最时候找一块特定的时间离开电脑,安心坐下来看看,你会对大师讲述的睿智和精妙赞叹不绝的。
Avatar_small
Remove Saved Card fr 说:
2021年11月23日 16:51

Mobikwik is a renowned payment App in India that is widely used to do mobile recharge, bill payment, DTH recharge, etc. There is an option in Mobikwik which provides its user with an option to save Remove Saved Card from Mobikwik the details of their bank cards. Here, a user can save the details of the card which he/she uses frequently while making their transactions through Mobikwik.

Avatar_small
seo service london 说:
2024年5月18日 19:39

Wonderful blog! Do you have any tips and hints for aspiring writers? Because I’m going to start my website soon, but I’m a little lost on everything. Many thanks! Excellent to be visiting your blog again, it has been months for me. Rightly, this article that I've been served for therefore long. I want this article to finish my assignment within the faculty, and it has the same topic together with your article. Thanks for the ton of valuable help, nice share


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter