968
歐拉項目【ProjectEuler】係列-第一題
歐拉項目【ProjectEuler】係列-第一題
----人既無名
既然是第一次，當然要寫個基本的介紹咯。
歐拉項目是一係列挑戰數學/計算機編程的問題. 需要的不僅僅是數學見解,還要利用計算機編程技巧,需要解決大多數問題，當然，數學幫助你運用優雅而有效的方法,實現漂亮而快速的代碼。
歐拉項目的網站是https://projecteuler.net，隻要上去注冊一個賬號就可以開始你的歐拉之旅了，當你把一個問題解決之後就可以參加該問題的討論，說說你的解決辦法，看看其他人的處理思路咯。言歸正傳，開始歐拉項目的第一題咯。
Problem 1：If
we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9.
The sum of these multiples is 23.Find
the sum of all the multiples of 3 or 5 below 1000.
意思就是：求出1000以下3或者5的倍數的自然數的和。
分析1：
3的倍數可以簡單表示為 n%3==0.
5的倍數可以簡單表示為 n%5==0.
3或者5的倍數就可以表示為 (n%3)&&(n%5)==0
因此，最簡單的辦法就是遍曆1-999，判斷該數是不是3或者5的倍數，是就加上，不是就跳過
int Fuc1()
{//Lazy way
int sum = 0;
int i=0;
for( i = 1; i < 1000; ++i)
if(0==((i % 3) && (i % 5)))
sum += i;
return sum;
}
分析2：
1000以下3的倍數
序列1:3 6 9 12 15 18 ... 999
5的倍數有
序列2:5 10 15 ... 995 （注意是1000以下，不包括1000）
我們是不是可以把這些數加起來作為最終的和呢？
很顯然，兩個序列中都有
序列1:15 30 ... 990（3和5的公倍數，也就是15的倍數）。
因此如何把序列1和序列2 加起來和還要減去序列3.
sum=序列1+序列2-序列3;
這個也是我最初的思路。整個代碼也就是
int MyFuc()
{
int sum = 0;
int i;
//序列1
for(i=3;i<1000;i+=3)
{
sum+=i;
}
//序列2
for(i=5;i<1000;i+=5)
{
sum+=i;
}
//序列3,注意是減去
for(i=15;i<1000;i+=15){sum-=i;}
return sum;
}
分析3：
可能會有人注意到，在我的第二個分析實現是第三步是減去序列3，也就是序列3的數實際上被訪問了兩遍，有沒有更好的辦法隻將所有的目標數隻訪問一遍就能求出結果呢？在來分析這些序列的特點
3 5 6 9 10 12 15 18 20 21 24 25 27 30 33 35 36 39 40 ...
除去3的倍數，即序列1，剩下的部分可以發現分為兩個序列
5 20 35 ...
10 25 40 ...
因此優化後的代碼為
int MyFuc2()
{
int sum = 0;
int i;
//序列1
for(i=3;i<1000;i+=3)
{
sum+=i;
}
//序列2
for(i=5;i<1000;i+=15)
{
sum+=i;
}
//序列3
for(i=10;i<1000;i+=15)
{
sum+=i;
}
return sum;
}
當然我們完全可以把這段代碼用匯編來實現，這是我用VC6下實現的匯編代碼：
int Fuc3(){
int sum;
_asm{
xor edx,edx ;sum
mov eax,3
A: cmp eax,1000
jnl B
add edx,eax
add eax,3
jmp A
B: mov eax,5
B1: cmp eax,1000
jnl C
add edx,eax
add eax,15
jmp B1
C: mov eax,10
C1: cmp eax,1000
jnl D
add edx,eax
add eax,15
jmp C1
D: mov sum,edx
}
return sum;
}
此時我已經沉浸在勝利的喜悅中，因為我的代碼優化已經達到了匯編級別，將上述4個函數分別運行1000000次測試結果顯示,從最開始需要6.898秒到現在隻要0.618秒，運行的速度得到了10倍左右的提升。具體的運行參數如下表：
| 函數 | 運行特點 | 運行時間(s) |
| Fuc1() | 最原始的方法 | 6.898 |
| MyFuc() | 序列1+序列2-序列3 | 2.093 |
| MyFuc2() | 優化後的序列法 | 1.569 |
| Fuc3() | 匯編優化 | 0.618 |
| Fuc5() | 等差數列求和公式 | 0.103 |
最後的分析：
難道真的這樣就完了嗎？如果現在要求把1000改成1000000會怎樣?我們還是虛心看看別人寫的東西吧！要想知道速度快不快還得和別人的比較才行。
再回到我最初的想法：
序列1+序列2-序列3
如果現在真的要求把1000改成1000000，我還有從3,6
,9遍曆到999999嗎？
3,6,9,...,999999
5,10,15,...,999995
15,30,...,999990
這三個序列都是等差數列啊，高中不就學過等差數列求和的方法嗎？
對於等差數列a1,a2,...,an,其中an=a1*dn,他們的和Sn為：
Sn=(a1+an)*n/2;
或者
Sn=a1*(1+dn)*n/2;
等等，通過這個公式是就可以快速求出3個等差序列的和
如，對於序列1：
999/3=333
序列1的和=3+6+9+...+333=3*（1+333）*333/2
同樣
999/5=199(取整即可)
序列2的和=5+10+...+995=5*（1+199）*199/2
999/15=66
序列2的和=15+30+...+990=15*（1+66）*66/2
sum=3*（1+333）*333/2+5*（1+199）*199/2+15*（1+66）*66/2;
設計一個求序列和的函數SumSeiresBy(int
n)
int SumSeiresBy(int n)
{
int p=999/n;
return n*(1+p)*p/2;
}
最終求和可以寫成
int Fuc5()
{
int sum;
sum=SumSeiresBy(3)+SumSeriesBy(5)-SumSeresBy(15);
return sum;
}
運行1000000次的時間為0.103秒(見表1)，要不要這麼狠，比我的匯編代碼還快，我下巴都快掉了，這就是一個高中送分的題啊，被我們想得這麼複雜，筆算都可以很快算出來啊。
不過有一點是值得我們思考的，在學習了很多是數學知識後我們沒有很好的將它們利用起來，遇到問題就以為用暴力的方式解決，不僅成效不高,還達不到優雅美觀，有失個人風範。而歐拉項目的目的是用數學幫助你運用優雅而有效的方法,實現漂亮而快速的代碼。數學什麼時候都不會過時。
最後更新：2017-04-02 22:16:21