關(guān)于啥是Project Euler 詳見(jiàn) https://projecteuler.net/about?

觀前聲明：

1. 這是個(gè)人興趣使然的對(duì)自己入坑pe的記錄，僅提供思路和部分代碼；各個(gè)方面肯定都是有著優(yōu)化與提升空間的，甚至在許多大佬看來(lái)這應(yīng)該是初學(xué)者的淺薄而未經(jīng)剪枝的丑碼，如果能幫到有興趣的人自是最好，也歡迎能醍醐灌頂?shù)纳疃扔懻摗?/p>

2. 大佬看到了笑笑就行，還請(qǐng)輕噴。

3. 帶著惡意，抬杠者...俺也噴不過(guò)您，也不能拿您咋樣...畢竟這只是我個(gè)人興趣使然的行為或者說(shuō)是學(xué)習(xí)記錄分享。?（說(shuō)是記錄，但因?yàn)槭窃缦葘懙乃云鋵?shí)是在各種意義上公開(kāi)處刑和吐槽自己 并嘗試補(bǔ)救優(yōu)化）

4. 語(yǔ)言是c++，用的VS平臺(tái)

第16題：

Power digit sum

Problem 16

2^15?= 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?

求出2的1000次方每位數(shù)的和.

這種大整數(shù)類型的題.簡(jiǎn)直是在難為c++（也還好.），因?yàn)閜ython可以直接算出2^1000，java自帶大整數(shù)類，而咱的c++啥都莫得要自己想辦法，直接pow(2,1000)不用想肯定是會(huì)溢出的

放個(gè)python的寫法:

sum = 0

for n in str(2**1000):?

sum += int(n) print sum

所以俺只能用數(shù)組模擬大整數(shù)，在之前的題也用過(guò)類似的思路了，就是用A[0]存放數(shù)的位數(shù)，然后A[1]儲(chǔ)存?zhèn)€位數(shù)，A[2]儲(chǔ)存十位數(shù)，一直儲(chǔ)存到A[A[0]]；（有興趣還閑得發(fā)慌的人可以用數(shù)組模擬大整數(shù)4則運(yùn)算，也不是啥難事.存?zhèn)€模板以后用起來(lái)也很方便）

而這里只要求計(jì)算2^n，所以這個(gè)數(shù)組對(duì)應(yīng)的函數(shù)也很簡(jiǎn)單，就是將A[1]到A[A[0]]都乘2，然后進(jìn)位處理，如果位數(shù)變化改變A[0]即可：

void sum(int A[1000])//A[0]存儲(chǔ)位數(shù),逆序自加;

{

? ? int i;

? ? for (i = 1; i <= A[0]; i++)

? ? ? ? A[i] *= 2;

? ? for (i = 1; i <= A[0]; i++)

? ? {

? ? ? ? if (A[i] < 10)continue;

? ? ? ? A[i + 1] += A[i] / 10;

? ? ? ? A[i] %= 10;

? ? ? ? A[0] += (i == A[0]);

? ? }

}

在主函數(shù)中令A(yù)[0]=1,A[1]=2,循環(huán)調(diào)用該函數(shù)999次，再求每位數(shù)的和即可.

算是比較暴力但清晰的思路了，好在規(guī)模不大可以秒出

需要注意的是，像A[]這種大數(shù)組盡量放在全局，不要放在函數(shù)內(nèi)，放在函數(shù)內(nèi)部是一個(gè)很不好的習(xí)慣，因?yàn)?^1000的位數(shù)上界不過(guò)1000，所以設(shè)置數(shù)組A[1000]是沒(méi)有問(wèn)題的。

ans:1366

第17題：

Number letter counts

Problem 17

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE:?Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

1到1000全用英文字母（英式）表示，然后數(shù)字母?jìng)€(gè)數(shù).(不算空格與劃線)

簡(jiǎn)單模擬題，寫個(gè)函數(shù)判斷數(shù)字n的字母?jìng)€(gè)數(shù)然后循環(huán)跑一遍即可

再不然，紙筆手算也不算復(fù)雜.無(wú)非列出大致的幾種情況加一下.

因?yàn)樯辖缡?000，one thousand有11個(gè)字母，所以我們跑到999最后加上11就行了；

將n分解為百位n1十位n2與個(gè)位n3：

int n1 = n / 100, n2 = (n / 10) % 10, n3 = n % 10;

然后用3個(gè)數(shù)組分別表示0~9，10~19，20~90字母數(shù)字范圍（因?yàn)樗?000內(nèi)數(shù)字都可通過(guò)這三個(gè)的組合與and和劃線來(lái)表示，比如143，one hunderd and forty-three，1對(duì)應(yīng)0~9，4對(duì)應(yīng)20~90，3再對(duì)應(yīng)0~9）

int numberx1[10] = { 0,3,3,5,4,4,3,5,5,4 };//0~9單詞字母數(shù);只要用到后面9個(gè)（c++數(shù)組物理序是從0開(kāi)始數(shù)的不會(huì)有人不知道吧....），第0個(gè)設(shè)為0(one~nine)

int numberx21[10] = { 3,6,6,8,8,7,7,9,8,8 };//10~19;(ten~nineteen)

int numberx22[10] = { 0,0,6,6,5,5,5,7,6,6 };//20~90;同上，只要用到后面8個(gè);(twenty~ninety)

（這部分小心點(diǎn)數(shù)別數(shù)錯(cuò).順便 當(dāng)時(shí)寫的時(shí)候才知道自己英語(yǔ)居然這么差.）

然后就開(kāi)始分類討論吧 如果n1不為0，則說(shuō)明是3位數(shù)，那么就要加上hundred?（7個(gè)字母）和第一個(gè)數(shù)組的[n1]；為0則不加；

然后討論n2為0，為1和大于1的情況，n3代入的數(shù)組依賴于n2的取值情況.細(xì)節(jié)懶得討論了自己想想不難的，姑且放出部分代碼：

int x1, x2;

x1 = numberx1[n1];

if (x1)x1 += 7;//n1 hunderd and...;

if (n2 == 1)x2 = numberx21[n3];

if (n2 > 1)x2 = numberx22[n2] + numberx1[n3];

if (n2 == 0)x2 = numberx1[n3];

if (x1&&x2)return x1 + x2 + 3;//and有3位字母;

else return x1 + x2;

其余部分包括主函數(shù)隨便寫寫即可；

手算：

one 3 -two 3 -three 5 -four 4 -five 4 -six 3 -seven 5 -eight 5 -nine 4 = 36

ten 3 -eleven 6- twelve 6 -thirteen 8 -fourteen 8 -fifteen 7 -sixteen 7 -seventeen 9 -eighteen 8- nineteen 8 = 70

twenty 6 -thirty 6 -forty 5 -fifty 5 -sixty 5 -seventy 7 -eighty 6 -ninety 6 = (46 * 10)? + (36 * 8) = 460 + 288 = 748

1~99=36+70+748=854；

只有1個(gè)hundred(7個(gè)字母，100，200，...900):

7*9+36=99

hundred+and（10個(gè)字母）（不考慮前面hunderd前面的數(shù)字，100，110，..990與1~9）:

10*99*9=8910

只考慮hunderd前面的數(shù)字（1~9作為百位，每個(gè)百位有99種情況）：

36*99=3564

所有百位后的1~99：

854*9=7696

1000：

11

全加起來(lái)：

ans:21124

第18題：

Maximum path sum I

Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7?4
2?4?6
8 5?9?3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

手機(jī)端圖看這里：

NOTE:?As there are only 16384 routes, it is possible to solve this problem by trying every route. However,?Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

對(duì)于這樣一個(gè)數(shù)字組成的三角陣，從頂元素開(kāi)始往下加，每次只能左下或右下進(jìn)行加法運(yùn)算，加到底層時(shí)最大數(shù)字為多少；這道題只有16384種情況，暴搜起來(lái)也不慢，但是pe67作為同類型的題有100行，就無(wú)法暴搜了。

實(shí)際上，這是個(gè)很經(jīng)典的動(dòng)態(tài)規(guī)劃問(wèn)題。

把這坨東西寫成下三角矩陣的形式：

a11

a21? a22

a31? a32? ?a33

....

不難發(fā)現(xiàn)，若令ost[i][j]表示從i行第j列出發(fā)到底層的路徑最大值

則ost[i][j]=A[i][j]+max(ost[i+1][j],ost[i+1][j+1])(i<n)? ;ost[n][j]=A[n][j]

那么思路就很簡(jiǎn)單了，從最后一行開(kāi)始，不斷取二者中的最大值向上給ost[i][j]賦值.

ost[0][0]即為所求.（實(shí)際上這是由底至頂?shù)臓顟B(tài)轉(zhuǎn)移方程.詳細(xì)可以去學(xué)運(yùn)籌學(xué)的動(dòng)態(tài)規(guī)劃.）

int ost[100][100] = { 0 };

void getost(int i, int j)

{

if (i == 14)ost[i][j] = A[i][j];

else ost[i][j] = A[i][j] + (ost[i + 1][j] > ost[i + 1][j + 1] ? ost[i + 1][j] : ost[i + 1][j + 1]);

}

int main()

{

for (int i = 14; i >= 0; i--)

for (int j = 0; j <=i; j++)

getost(i, j);

cout << ost[0][0];

return 0;

}

ans:1074

第19題：

Counting Sundays

Problem 19

You are given the following information, but you may prefer to do some research for yourself.

• 1 Jan 1900 was a Monday.

• Thirty days has September,
  April, June and November.
  All the rest have thirty-one,
  Saving February alone,
  Which has twenty-eight, rain or shine.
  And on leap years, twenty-nine.

• A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

1901年1月1日開(kāi)始到2000年12月31日有多少個(gè)星期天在每月初的第一天？

上面的英文有額外告訴我們的已知情況，不過(guò)除了1900年的1月1日是周一外沒(méi)啥特別有用的

又是這種咋一看有意思但實(shí)際寫起來(lái)提不起興趣的模擬題.因?yàn)槲乙话阌胏++寫模擬題都又臭又長(zhǎng)（我水平有限）

簡(jiǎn)單介紹下手算法...無(wú)非是像上題那樣把所有情況考慮一下該加加該減減注意閏年.就不多說(shuō)了 感興趣者自己算算也不難。

如果要代碼的話那么怎么敲呢. 實(shí)際上這題我寫了個(gè)比較蠢的代碼

簡(jiǎn)單推算知1901.1.1是周一，到2000.12.31共36524天。

若某年某月的天數(shù)模7等于x，那么如果這月從周n開(kāi)始，下月的起始天為周（x+n）%7? （周0算作周天）

那么先寫個(gè)求某年某月當(dāng)月天數(shù)的函數(shù)getdaynum；再用這個(gè)函數(shù)寫個(gè)求當(dāng)月月初是周幾的函數(shù)days

int getdaynum(int year, int month)//這個(gè)考慮好閏年即可，不難寫；

{

if (year % 4 == 0 && year % 400 == 0)

if (month == 2)return 29;

if (month == 2)return 28;

if (month == 4 || month == 6 || month == 9 || month == 11)return 30;

return 31;

}

對(duì)于days(int year,int month)函數(shù)，我們知道，如果是1901年1月，則返回1；

如果是其他年月，那么則返回（上一個(gè)月的天數(shù)+上月的起始周）%7

int days(int year, int month)

{

if (year == 1901 && month == 1)return 1;

if (month == 1)return (days(year - 1, 12) + getdaynum(year - 1, 12) ) % 7;

return (days(year, month - 1) + getdaynum(year, month - 1)) % 7;

}

實(shí)際上我這寫法也不好，應(yīng)該在函數(shù)外再建一個(gè)數(shù)組儲(chǔ)存，直接調(diào)用數(shù)組的，這種暴力遞歸如果在主函數(shù)直接跑實(shí)際上會(huì)白跑很多趟. 不過(guò)當(dāng)時(shí)比現(xiàn)在還傻.現(xiàn)在又懶得改了，大家注意一下就行。

ans:171

第20題：

Factorial digit sum

Problem 20

n! means?n?× (n?? 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

算出100！每個(gè)位數(shù)數(shù)字的和。

又是這類大正數(shù)問(wèn)題，又到了c++拉跨時(shí)間。

還記得之前的寫的大整數(shù)加法嗎.大整數(shù)乘法也不難寫.但當(dāng)時(shí)的我明顯想偷懶，所以稍微改了一下大整數(shù)加法變成加法實(shí)現(xiàn)的簡(jiǎn)易階乘（大整數(shù)乘法的話后面有些題遲早要放的 現(xiàn)在在姑且讓我節(jié)一下能）

大整數(shù)加法再放送：

void sum(int A[1000],int B[1000])//A[0]存儲(chǔ)位數(shù),逆序加;

{

? ? int i;

? ? for (i = 1; i <= A[0]; i++)

? ? ? ? A[i] += B[i];

? ? for (i = 1; i <= A[0]; i++)

? ? {

? ? ? ? if (A[i] < 10)continue;

? ? ? ? A[i + 1] += A[i] / 10;

? ? ? ? A[i] %= 10;

? ? ? ? A[0] += (i == A[0]);

? ? }

}

n!等于（n-1）！個(gè)n相加

所以只要寫個(gè)n-1個(gè)A[]自加的函數(shù)(A,n)，循環(huán)調(diào)用n次(A,i)（i從n到1）即可

void valve(int A[1000], int n)//自加n-1次;

{

? ? int i;

? ? for (i = 0; i < 1000; i++)

? ? ? ? B[i] = A[i];

? ? for (i = 1; i < n - 1; i++)

? ? ? ? sum(A, B);

}

int main()

{

? ? int i, j, sum = 0;

? ? A[0] = 3, A[1] = 0, A[2] = 0, A[3] = 1;

? ? for (i = 100; i > 0; i--)//簡(jiǎn)易階乘;

? ? ? ? valve(A, i);

? ? for (i = A[0]; i > 0; i--)

? ? ? ? sum += A[i];

? ? cout << sum;

? ? return 0;

}

所幸規(guī)模不大基本秒出. 但這種寫法極其偷懶，大家還是自己思考下怎么模擬大整數(shù)的乘法吧.當(dāng)然以后俺也會(huì)放出來(lái)的（如果還有以后的題的話）

ans:648

那么.有緣再見(jiàn)