欧拉计划

维基百科,自由的百科全书
跳转至: 导航搜索
欧拉计划(Project Euler)
Euler
網址 projecteuler.net
商業性質? 非盈利
網站類型 解题类网站
註冊 Free
創始者 Colin Hughes
推出時間 October 5, 2001

欧拉计划(Project Euler)是一个解题网站,站内提供了一系列数学题供用户解答,解题的用户主要是对数学计算机编程感兴趣的成年人及学生。目前该站包含了四百多道不同难度的数学题,每一题都可以通过计算机程序在1分钟内求出结果。该网站自2001年起定期增加新的题目,每题都有对应的讨论区,注册用户在正确提交了某题的答案后才能进入该题的讨论区。[1] 站内根据完成题目的数量将用户分为6个级别,设立了6个排行榜,并用正多面体球体来表示不同的级别。另外还设有一个欧拉人(Eulerians)排行榜。只有最新题目的前20位解答者才可以上榜。[2]

例题与解答[编辑]

欧拉计划的第一题是:

列举出10以下所有3或5的倍数,我们得到 3, 5, 6 和 9。他们的和是23。

求1000以下所有3或5的倍数之和。

虽然这题比欧拉计划大多数题目要容易的多,我们仍然可以用它来分析不同解题方法的效率。
穷举法来测试1000以下的所有自然数,再将它们相加就能得到这题的结果。这很容易实现,用以下两种不同的编程语言都能很快求解出答案。

Python

print(sum(i for i in range(1000) if i%3 == 0 or i%5 == 0))

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多次运算。

sum(n) = \sum_{i=1}^{\lfloor \frac{n}{3} \rfloor} 3i + \sum_{i=1}^{\lfloor \frac{n}{5} \rfloor} 5i - \sum_{i=1}^{\lfloor \frac{n}{15} \rfloor} 15i
\sum_{i=1}^n ki = k\frac{(n)(n+1)}{2}

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)

参考文献[编辑]

  1. ^ 关于Project Euler. [2009-02-08]. 
  2. ^ 欧拉人积分规则和排行榜. [2011-07-03]. 

外部链接[编辑]