再谈project euler

haolloyin 师兄已经在这里介绍了project euler这个很不错的算法练手网站,经过俺的亲身体会,觉得非常有必要推荐给各位同学。而且project euler 最近改版了,新版有很多有趣的奖,看着就激动更不用说得到了。
 
师兄的文章里全面介绍了project euler 这个网站,我想续写一下,顺便总结这些天玩 euler 题目的心得。通常解一道题并不是马上就会有思路,可以先将这个问题放到头脑中进行思索,走路的时候拿出来思考(注意不要撞到树或人),或许说不定你的大脑在你努力之后异步返回一个相当聪明的解法。通常需要经过一定时间的思索才能找到比较快(1 分钟)之内得到答案的方法,当然有时候根本不需要动用计算机,只需要动动脑筋就可以解答出来。而且数学用得越多,你的方法就可能越快。
 
【一般的解题步骤】
这个是从一本叫做《数学与创造》的书里面抄的,拿来用。
不过就只有两句话:观察,观察,再观察     ; 思考,思考,再思考。
解题过程中会有许多有趣的现象,那就是你观察的越细致认真,越能找出其中规律,但是质数类题目一般难以找出规律(主要以霸王硬上弓为主)。思考地越全面往往就有越巧妙的方法,当然只有想法是不能得到答案的,因为很多题目都要进行大量的计算。
一般都是先看懂题目,进行初步观察,选择最恰当的数据结构(数组、链表、树等)。选对数据结构很重要,选对数据结构代表方向对了,算法也就能找到了。
【解决完题目之后】
而编码实现又是另外一方面的功夫,解除一道题目之后会有相当多的留言,有各种各样的代码。但是看别人的代码是很痛苦的,能看懂就不错了。我往往去找找那些没有代码,而是给出一些数学分析的留言来看,当然最好是别人评价了一个good的。少贴代码,多讲思想。当然好的编程风格或者巧妙地实现应当看看,便于日后学习其中的方法以及养成良好的编程习惯。
题目渐渐地累积,慢慢地就会发现很多题目都是类似的。所以聪明人往往很能借鉴之前的一些好的经验应用到新的问题上,当然也有抽象能力十分强的人,一下子就感觉到那些表面上不同的题目背后相同的本质。题目慢慢多了,也越来越难了,很多东西需要重复利用的,但是找的时候却怎样都找不到。除了根据题目来索引您需要寻找的内容或者代码段,您最好建立一个专门的记录来保存每道题的解题思路以及运用到的一些可能都运用到的算法。像判断质数函数、求阶乘的函数,以及取出每一位数都需要好好保存,要用的时候贴上去就可以了,当然也可以建立自己的库,直接include也行。
最好的莫过于对每道题进行分类总结,制作一个思维导图能够自由地索引到任何一道题目,以后要用到的时候可以到map里面找找灵感,收获绝对不会小。
下面是几个常用的代码段,实现可能很烂,但毕竟还是可以用的
1、判断是否是质数
bool isPrime(long long x)
{
    bool flag = true;
    for(long long i = 2;i*i<=x;i++)
    {
        if(x%i==0)//zheng chu
        {flag =false;break;}
    }
    if(x==1)
        flag = false;
    return flag;
} 
2、递归实现阶乘
long long factory(int x)
{
    if(x==1||x==0)
        return 1;
    else
        return factory(x-1)*x;    
}
3、分解出每一位              
long long temp = a;//得到每一位进行组合
while(temp !=0)
{
    digits.push_back(temp%10);
    temp = temp / 10;
}
4、大数运算
可以采用n进制,n可以是任意计算机能表示的数 如1000,表示满n进1,一般是用数组或链表实现
当然也有用string类实现的。各有所长,总之要能用软件的方法扩展硬件的不足。
东西虽然小,保存起来总有用处
好下面来点有意思的——崭新的project euler
【project euler 里面的奖章】
看到下图你就非常激动了,这么多眼花缭乱的奖章,十项全能、百里挑一、金牌等等,还等什么以前来加入project euler吧!
euler award

解决题数从少到多,等级从低到高,每一次都会有各种的惊喜。下面是等级分类 ,是不是想尝试一下呢

euler level
















by bibodeng 2011-10-20