欧拉计划(Project Euler)
创始者:Colin Hughes
推出时间:October 5, 2001
目前该站包含了400多道不同难度的数学题,每一题都可以通过计算机程序在1分钟内求出结果。该网站自2001年起定期增加新的题目,每题都有对应的讨论区,注册用户在正确提交了某题的答案后才能进入该题的讨论区。站内根据完成题目的数量将用户分为6个级别,设立了6个排行榜,并用正多面体和球体来表示不同的级别。另外还设有一个欧拉人(Eulerians)排行榜,只包含在最新的25题里作出13题以上的用户。
例题与解答
欧拉计划的第一题是:
列举出10以下所有3或5的倍数,我们得到 3, 5, 6 和 9。他们的和是23。
求1000以下所有3或5的倍数之和。
虽然这题比欧拉计划大多数题目要容易的多,我们仍然可以用它来分析不同解体方法的效率。
用穷举法来测试1000以下的所有自然数,再将它们相加就能得到这题的结果。这很容易实现,用以下两种不同的编程语言都能很快求解出答案。
Python:
print sum(filter(lambda x:x % 3 == 0 or x % 5 == 0, xrange(1, 1000)))
C++:
#include <iostream>
using namespace std;
int main( ) {
int sum = 0;
for (int i = 0; i < 1000; i++)
if ( i % 3 == 0 || i % 5 == 0 )
sum += i;
cout << sum << endl;
return 0;
}
但如果用排容原理进行求和,就可以减少1000多次运算。
Python 实现:
def sum1toN(n):
return n * (n + 1) / 2
def sumMultiples(limit, a):
return sum1toN((limit - 1) / a) * a
sumMultiples(1000, 3) + sumMultiples(1000, 5) - sumMultiples(1000, 15)
采用这种方法,计算10,000,000以下或1000以下所花费的时间是相等的。若用大O符号来描述两种方法的优劣,那么穷举算法为O(n)而高效的算法为O(1)。