歐拉計劃
外觀
此條目過於依賴第一手來源。 (2021年10月25日) |
網站類型 | 解題類網站 |
---|---|
創始人 | Colin Hughes |
網址 | projecteuler.net |
商業性質 | 非盈利 |
註冊 | 免費 |
推出時間 | 2001年10月5日 |
歐拉計劃(Project Euler)是一個解題網站,站內提供了一系列數學題供用戶解答,解題的用戶主要是對數學和計算機編程感興趣的成年人及學生。其主旨為鼓勵、挑戰和培養愛好數學的人的技能和樂趣。目前該站包含了七百多道不同難度的數學題。每一題都可以通過電腦程式在1分鐘內求出結果。該網站自2001年起定期增加新的題目,每題都有對應的討論區,只有註冊用戶在正確提交了這題的答案後才能進入。[1] 網站設立了6個排行榜,其中的歐拉人(Eulerians)排行榜的分數需要最新題目的前50位解答者才能獲得。[2]歐拉計劃不希望在站外分享題目的答案。
例題與解答
[編輯]歐拉計劃的第一題是:
列舉出10以下所有3或5的倍數,我們得到 3, 5, 6 和 9。他們的和是23。
求1000以下所有3或5的倍數之和。
雖然這題比歐拉計劃大多數題目要容易的多,我們仍然可以用它來分析不同解題方法的效率。
用 的窮舉法來測試1000以下的所有符合條件的自然數,再將它們相加就能得到這題的結果。這很容易實現,用以下兩種不同的程式語言都能用很快求解出答案。
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以下所花費的時間是相等的。
參考文獻
[編輯]- ^ 关于Project Euler. [2009-02-08]. (原始內容存檔於2008-03-14).
- ^ 欧拉人积分规则和排行榜. [2011-07-03]. (原始內容存檔於2011-09-25).