歐拉計劃

維基百科,自由的百科全書
歐拉計劃
Project Euler
網站類型
解題類網站
創始人Colin Hughes
網址projecteuler.net
商業性質非盈利
註冊免費
推出時間2001年10月5日,​22年前​(2001-10-05

歐拉計劃(Project Euler)是一個解題網站,站內提供了一系列數學題供用戶解答,解題的用戶主要是對數學計算機編程感興趣的成年人及學生。其主旨為鼓勵、挑戰和培養愛好數學的人的技能和樂趣。目前該站包含了七百多道不同難度的數學題。每一題都可以通過電腦程式在1分鐘內求出結果。該網站自2001年起定期增加新的題目,每題都有對應的討論區,只有註冊用戶在正確提交了這題的答案後才能進入。[1] 網站設立了6個排行榜,其中的歐拉人(Eulerians)排行榜的分數需要最新題目的前50位解答者才能獲得。[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多次運算,獲得 的時間複雜度。

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以下所花費的時間是相等的。

參考文獻[編輯]

  1. ^ 关于Project Euler. [2009-02-08]. (原始內容存檔於2008-03-14). 
  2. ^ 欧拉人积分规则和排行榜. [2011-07-03]. (原始內容存檔於2011-09-25). 

外部連結[編輯]