Project Euler 001~005
開始了填歐拉計(jì)劃的坑.
應(yīng)該不會(huì)有覺得歐拉是替身使者的人吧....以防萬一多說一句是那位迫害廣大學(xué)渣的偉大數(shù)學(xué)家，不是某jo太郎打的拳。
關(guān)于啥是Project Euler 詳見 https://projecteuler.net/about
總之就是給出了一系列需要依賴數(shù)學(xué)方面的知識(shí)與編程能力結(jié)合的有趣的題，難度也跨度較廣，但肯定是越往后越難的
因?yàn)橹挥星?00題屬于新手向且無所謂答案討論公開與否 所以這個(gè)坑可能就完結(jié)于第100題吧..大概 如果不咕咕咕的話。（再往后的題大概率會(huì)因本人太菜寫不出來了）
（因?yàn)榍懊娴亩纪?jiǎn)單 所以就多題放一起 后期估計(jì)就1題水一期了）
觀前聲明：
這是個(gè)人興趣使然的對(duì)自己入坑pe的記錄，僅提供思路和部分代碼；各個(gè)方面肯定都是有著優(yōu)化與提升空間的，甚至在許多大佬看來這應(yīng)該是初學(xué)者的淺薄而未經(jīng)剪枝的丑碼，如果能幫到有興趣的人自是最好，也歡迎能醍醐灌頂?shù)纳疃扔懻摗?/p>
大佬看到了笑笑就行，還請(qǐng)輕噴。
帶著惡意，抬杠者...俺也噴不過您，也不能拿您咋樣...畢竟這只是我個(gè)人興趣使然的行為或者說是學(xué)習(xí)記錄分享。?（說是記錄，但因?yàn)槭窃缦葘懙乃云鋵?shí)是在各種意義上公開處刑和吐槽自己 并嘗試補(bǔ)救優(yōu)化）
語言是c++，用的VS平臺(tái)
那么第一題原題如下：
Multiples of 3 and 5
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的倍數(shù)的和，畢竟是第一題也就這么個(gè)難度，甚至不需要代碼.
容斥隨便算算：
3的等差數(shù)列+5的等差數(shù)列-15的等差數(shù)列
（999為3n的第333項(xiàng)，995為5n的第199項(xiàng)，990為15n的第66項(xiàng)）
答案是233168
第二題：
Even Fibonacci numbers??
Problem 2
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
求4000000以內(nèi)的斐波那契數(shù)列中的值為偶數(shù)的項(xiàng)的和.
斐波那契數(shù)列的通項(xiàng)其實(shí)只要具有高中的數(shù)列知識(shí)就能用待定系數(shù)法自己推出來...
但在這用通項(xiàng)估計(jì)是不好使的.所以節(jié)能的我放棄手算了
現(xiàn)在想來可以在全局設(shè)置一個(gè)數(shù)組靜態(tài)存儲(chǔ)每一項(xiàng)然后順序動(dòng)態(tài)規(guī)劃的，但當(dāng)時(shí)的我非常頭鐵直接就毫無優(yōu)化的使用遞歸函數(shù)了
int fabonaci(int n)
{
if (n == 1)return 1;
if (n == 2)return 2;
return fabonaci(n - 1) + fabonaci(n - 2);
}
int main()
{
int n, sum = 0;
for (n = 1; fabonaci(n) <= 4000000; n++)
if (fabonaci(n) % 2 == 0)sum += fabonaci(n);
cout << sum;
return 0;
}
實(shí)際上這是個(gè)時(shí)間復(fù)雜度相當(dāng)高的代碼? ?單個(gè)項(xiàng)n要跑o(2^n)左右（大概？），在主函數(shù)里甚至每個(gè)n都要跑一遍 毫無人性 現(xiàn)在的我看來都覺得蠢? ?至少用個(gè)數(shù)組記錄存著吧. 就不用每次求f(n)的時(shí)候都求一遍f(k)(k<n)了
好在才第二題計(jì)算量不大..當(dāng)時(shí)的我也根本沒意識(shí)到嚴(yán)重性看到跑出來就滿意的走了
answer 4613732
第三題：
Largest prime factor
Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
13195的質(zhì)因數(shù)為5，7，13，29，求600851475143的最大質(zhì)因數(shù).
求因數(shù)、判斷質(zhì)數(shù)這一塊有許多相應(yīng)的知識(shí)，即便是小學(xué)生都能知道這題可以暴搜所有小于等于600851475143/2的數(shù)先判斷是否為因子再判斷是否為質(zhì)數(shù)
（是的當(dāng)時(shí)原始人一樣思考的我就是這么做的）：
int checkprime(int n)
{
int i;
for (i = 2; i <= sqrt(n); i++)
if (n % i == 0)return 0;
return 1;
}
int main()
{
long long n, larfac = 1;
for (n = 1; n * n < 600851475143 ; n++)
if ((600851475143 % n == 0) && checkprime(n))
if (n > larfac)larfac = n;
cout << larfac;
return 0;
}
因?yàn)閿?shù)字太大所以放了個(gè)long long跑了一會(huì)跑出來了
顯然當(dāng)時(shí)的我好像不懂全局設(shè)個(gè)數(shù)組這種優(yōu)化概念，這里寫個(gè)判斷質(zhì)數(shù)是o(n^(1/2))主函數(shù)又跑了o(n^(1/2))（不知當(dāng)時(shí)的我這么寫算不算僥幸這個(gè)數(shù)的最大質(zhì)因數(shù)恰小于sqrt(n)）
比較合理的做法是先確定質(zhì)因數(shù)的上界，再歐拉篩獲得這部分的質(zhì)數(shù)，然后從大到小判斷是否為因子。（概念諸如歐拉篩一類出于節(jié)能考慮懶得放了，查查學(xué)學(xué)并不難，大致思想就是從2開始循環(huán)到n，對(duì)每個(gè)進(jìn)行的i如果沒有標(biāo)記就默認(rèn)為質(zhì)數(shù)，然后再套個(gè)循環(huán)將i的所有倍數(shù)標(biāo)記為合數(shù)，i跑完沒有被標(biāo)記的數(shù)就是質(zhì)數(shù)了）
再或者不斷將這個(gè)數(shù)除以質(zhì)數(shù)，當(dāng)不能整除這個(gè)質(zhì)數(shù)時(shí)，就檢驗(yàn)商是否能整除下一個(gè)質(zhì)數(shù)，比如從2開始，n不斷整除2，n/(2^k)不能整除2后開始除以3，以此類推循環(huán)到不能整除之后的所有質(zhì)數(shù)為止，這樣就得到了這個(gè)整數(shù)的質(zhì)因數(shù)分解。
answer 6857
第四題：
Largest palindrome product?
Problem 4
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
9009這樣的數(shù)字稱為回文數(shù)，找到由2個(gè)三位數(shù)乘積得到的值最大的回文數(shù)
m×n位數(shù)是m+n位數(shù)或m+n-1位數(shù) 因?yàn)榫?位數(shù) 這題暴搜也不慢
遍歷所有2個(gè)三位數(shù)的乘積判斷是否為回文就行了.
int checkp(int A[6])
{
int i;
if (A[0] == 0)
if ((A[1] == A[5]) && (A[2] == A[4]))
return 1;
for ( i = 0; i < 3; i++)
if (A[i] != A[5 - i])break;
if (i == 3)return 1;
return 0;
}
int main()
{
int i, j, k, wei[6], larnum = 0;
for(i=100;i<=999;i++)
for (j = 1; j <= 999; j++)
{
for (k = 0; k < 6; k++)
wei[k] = (i*j / (int)pow(10, 5 - k)) % 10;
if (checkp(wei) && (i * j > larnum))
larnum = i * j;
}
cout << larnum;
return 0;
}
check函數(shù)就是判斷是否為回文，先不論這個(gè)函數(shù)是不是寫丑了，當(dāng)時(shí)的我在主函數(shù)里將數(shù)字做成數(shù)組的非常的一言難盡...
for (k = 0; k < 6; k++)
wei[k] = (i*j / (int)pow(10, 5 - k)) % 10;
這種寫法在數(shù)字大時(shí)非常容易溢出..建議用while循環(huán)每次將n除以10 余10這樣存.
例如 這種.
while(n)
{
A[i++]=n/10;
n%=10;
}
暴搜沒啥好說的 答案906609
第五題：
Smallest multiple
Problem 5
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is?evenly divisible?by all of the numbers from 1 to 20?
2520是因子中有1~10中的每一個(gè)的最小的數(shù)，求因子有1~20的最小的正整數(shù)。
不多的能手算的水題....把公因數(shù)去一下乘起來即可：
1×2×3×2（4約去公因數(shù)2）×5×1（6約去前面的公因數(shù)）×7×2（8約去前面的2×2，以此類推）×3×1×11×1×13×1×1×2×17×1×19×1=232792560
水完了，俺累了.不定期更新之后的題吧.
