Project Euler 036~040
關(guān)于啥是Project Euler 詳見 https://projecteuler.net/about?????
觀前聲明：? ? ? ? ?.
這是個人興趣使然的對自己入坑pe的記錄，僅提供思路和部分代碼；各個方面肯定都是有著優(yōu)化與提升空間的，甚至在許多大佬看來這應(yīng)該是初學(xué)者的淺薄而未經(jīng)剪枝的丑碼，如果能幫到有興趣的人自是最好，也歡迎能醍醐灌頂?shù)纳疃扔懻摗? ?
大佬看到了笑笑就行，還請輕噴。
帶著惡意，抬杠者...俺也噴不過您，也不能拿您咋樣...畢竟這只是我個人興趣使然的行為或者說是學(xué)習(xí)記錄分享。?（說是記錄，但因為是早先寫的所以其實是在各種意義上公開處刑和吐槽自己 并嘗試補救優(yōu)化）
語言是c++，用的VS平臺
本期觀前提示：36~40除了40都需要頻繁的用到數(shù)組與數(shù)的轉(zhuǎn)化，而且本期基本莫得操作，全按定義頭鐵的運行即可.所以部分題可能不會怎么分析（）所以我看起來會很撈...
第36題：
Double-base palindromes
Problem 36
The decimal number, 585 = 10010010012?(binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
(Please note that the palindromic number, in either base, may not include leading zeros.)
求出1000000以內(nèi)所有十進制與二進制寫法都為回文數(shù)的數(shù)的和。
記得第四題的回文數(shù)嗎..這不就進階版嗎，多了個二進制寫法也要是回文數(shù)。注意到二進制寫法如果是回文數(shù)，則一定為奇數(shù)，因為0不能開頭，而二進制偶數(shù)以0結(jié)尾。
對于一個數(shù)怎么變成二進制數(shù)，實際情況是比較復(fù)雜的，但如果只是正整數(shù)的話就簡單得多（負(fù)數(shù)要取反加1，小數(shù)要......請自行搜索），舉個例子，若數(shù)組第0位存儲二進制寫法的末尾數(shù)，那么比如9=2^3+2^0，第3位，第0位就為1，第1，2位為0，9的二進制寫法就為1001；
詳細(xì)得到步驟：若二進制表示為ana(n-1)a(n-2)……a0,那么ak=nk%2,n(k-1)=nk/2;n(n)=n
9：
9%2=1，9/2=4（整型數(shù)據(jù)自動下取整）；
4%2=0，4/2=2；
2%2=0，2/2=1；
1%2=1，1/2=0；得到0后算法終止
9的二進制即為1001。對應(yīng)算法：
while (n)//用A數(shù)組保存
{
A[j++] = n?% 2;
n?/= 2;
}
那么對于每個小于1000000的奇數(shù)，先分別存成十進制與二進制的數(shù)組，再判斷十進制與二進制是否為回文數(shù)；存十進制數(shù)組懶得再講，二進制在上面；判斷，判斷還要說嘛？不就個獲取數(shù)組長度后頭到尾尾到頭看看相不相等的事實現(xiàn)真的不難，實在不行回去看看第四題俺怎么水的吧。
ans：872187
第37題：
Truncatable primes
Problem 37
The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
3797是個有趣的質(zhì)數(shù)，從左到右或從右到左不斷拆掉其中的數(shù)字還為質(zhì)數(shù)：797，97，7，379，37，3；只有11個質(zhì)數(shù)有這種性質(zhì)，求出它們的和。
上界不好求，但人家告訴我們只有11位，那么從11開始用因子確認(rèn)的方式跑，或者先用個非常大的M先篩一遍，然后看看這之中有多少個符合這種性質(zhì)的質(zhì)數(shù)（從答案上來看不超過7位數(shù)）不過既然題干都確信只有11個質(zhì)數(shù)具有此性質(zhì)，那么應(yīng)該是有嚴(yán)格的數(shù)論證明的.有興趣的話不妨自己去搜搜，俺因為太懶就沒去找了.（找到了@俺一下.俺也想看（））
確認(rèn)質(zhì)數(shù)，遍歷跑這些都不難，講講做成數(shù)組后提取其中某個部分。
其實也沒啥好講的，能把數(shù)組化數(shù)提取其中一部分做成數(shù)也不難，大概長這樣：
int changeinter(int A[], int start, int end)
{
int i, j, sum = 0;
for (i = start, j = end - start; i <= end; i++, j--)
sum += A[i] * pow(10, j);
return sum;
}
對于每個質(zhì)數(shù)判斷其每個可能的分解是否為質(zhì)數(shù)，分解函數(shù)如上；判斷質(zhì)數(shù)可以跑表也能直接判斷（規(guī)模不大 頭鐵無傷）真的是莫得操作的題...
ans：748317
第38題：
Pandigital multiples
Problem 38
Take the number 192 and multiply it by each of 1, 2, and 3:
192 × 1 = 192，192 × 2 = 384，192 × 3 = 576
By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)
The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).
What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... ,?n) where?n?> 1?
如果讓192與（1，2，3）中的每位數(shù)字分別相乘得到（192，384，576），組合成一個9位數(shù)192384576，正好能不多不少的囊括1~9的所有數(shù)字，用9乘（1，2，3，4，5）也能得到同樣的結(jié)果918273645，找到用這種方式得到的最大的9位數(shù)。
簡單來說，就是一個整數(shù)n與(1,2,3...,k)的組合，先來分析下上界，要得到的是個9位數(shù)，所以k肯定小于等于9，不然就會得到9位數(shù)以上了，同樣因為題設(shè)要求k>1，所以整數(shù)上界為10000（不然10000與（1，2）的組合會得到10位數(shù)）
那么檢驗數(shù)n與(1,...,k)的代碼要怎么寫呢？
其實也是很簡單的思路，現(xiàn)用一個數(shù)組儲存每個i*n，再把它們縫合到一個更大的數(shù)組B[100]上，如果不是9位數(shù)可以直接判斷匹配失敗，如果是9位數(shù)再把其中每個數(shù)記錄到C上，比如定義數(shù)組C[10]，C[B[i]]=1，表示B[i]出現(xiàn)過，遍歷記錄完B后再去看C[1~9]是否都出現(xiàn)過；
或者將B直接存到C里再對C使用sort函數(shù)排序，排完序后直接驗證C[i]是否為i。
不懂事時寫的丑碼 僅供參考：
int checken(int n, int k)//整數(shù)n為（1，2...,k）的整合;
{
int A[10], i, j, B[1000];
for (i = 1; i <= k; i++)
A[i] = n * i;
for (i = 1, j = 0; i <= k; j = change(B, A[i++], j));//B儲存整合后的數(shù),j儲存B位數(shù);
if (j != 9)return 0;
int C[9];
for (i = 0; i < 9; i++)
C[i] = B[i];
sort(C, 0, 8);
for (i = 0; i < 9; i++)
if (C[i] != i + 1)return 0;
return changeinter(B, 0, 8);
}
調(diào)用的2個函數(shù)功能分別為int changeinter(int A[], int start, int end)//將數(shù)組A中s->end的一段轉(zhuǎn)化為數(shù)字;上一題就有；
int change(int A[], int n,int start)//將n做成數(shù)組其初始位儲存在A的start上,返回n的結(jié)尾數(shù)+1;
{
int i, j = 0;
while (n / (int)pow(10, j))
{
j++;
}
for (i = start; i < j + start; i++)
A[i] = (n / (int)pow(10, j + start - i - 1)) % 10;
return i;
}
這3個函數(shù)都是早年寫的.感覺不太干凈利落? 僅供參考.知道實現(xiàn)思路后諸位應(yīng)該能寫出比俺的看的更容易入眼的代碼.
答案是9327與{1，2}形成的數(shù)。
ans：932718654
第39題：
Integer right triangles
Problem 39
If?p?is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for?p?= 120.
{20,48,52}, {24,45,51}, {30,40,50}
For which value of?p?≤ 1000, is the number of solutions maximised?
若p是整數(shù)邊長的直角三角形的周長，那么對于p=120能夠找到3個直角三角形{20,48,52}, {24,45,51}, {30,40,50}；對于p<=1000，p取什么值時找到的直角三角形數(shù)量最多。
這題肯定有比我更好的解法，但看到規(guī)模這么小，我，莫得感情，莫得思考，莫得操作，化身頭鐵機器。
判斷直角三角形：
int checkright(int a, int b, int p)//p為周長;
{
int c = p - a - b;
if (a + b < c || a + c < b || b + c < a)return 0;
if (a * a + b * b == c * c)return 1;
if (a * a + c * c == b * b)return 1;
if (b * b + c * c == a * a)return 1;
return 0;
}
判斷p的解：
int nump(int p)//會有重復(fù)，結(jié)果除以3
{
int a, b, num = 0;
for (a = 1; a <= p / 2; a++)
for (b = a + 1; b <= p / 2; b++)
if (checkright(a, b, p))
num++;
return num / 3;
}
主函數(shù)頭鐵的跑...到1000為止
總共有8個；
ans:840
第40題：
Champernowne's constant
Problem 40
An irrational decimal fraction is created by concatenating the positive integers:
0.123456789101112131415161718192021...
It can be seen that the 12th?digit of the fractional part is 1.
If?dn?represents the?nth?digit of the fractional part, find the value of the following expression.
d1?×?d10?×?d100?×?d1000?×?d10000?×?d100000?×?d1000000
將所有非負(fù)整數(shù)連到一起形成一個有規(guī)律可循的無理數(shù)0,1,2,3,4...->0.1234567891011...
第12位是1，那么第1位×第10位×...×第1000000位是多少？
這應(yīng)該是小學(xué)生找規(guī)律求余求商的題吧？建議手算。
比如算第100位，可知1~9占滿了1~9位，剩91位，現(xiàn)在看2位數(shù)，91/2=45...1，所以從10開始經(jīng)過45個2位數(shù)后到達(dá)第90位，第45個2位數(shù)是54，4剛好占到第90位，下一個兩位數(shù)55，第一個5占到第91位，所以d100=5...用這個思路分析一下真的不難 差不多幾分鐘就能寫出來：
d1=1,d10=1,d100=5,d1000=3,d10000=7,d100000=2,d1000000=1;
手算之余 實在太懶也可以敲代碼實現(xiàn)這個思路：
int nlength(int n)
{
if (n == 0)return 1;
int dight = 0;
while (n)
{
dight++;
n /= 10;
}
return dight;
}
int position(int n)
{
if (n < 10)return n;
int sum = 9, presum = 0, j = 1;
while (n - sum > 0)
{
presum = sum;
j++;
sum += j * 9 * (int)pow(10, j - 1);
}
int nyu = n - presum;
int nx = nyu / j, ny = nyu % j;
nx += pow(10, j - 1);
return nx / (int)pow(10, nlength(nx) - ny) % 10;
}
太簡單就不解釋了，實際上完全不需要代碼的。
ans:210
這期感覺俺顯得很撈..畢竟這幾道題沒啥操作，要么按定義要么頭鐵...
快樂BF快樂節(jié)能~
（希望各位也能體會到鐵憨憨跑題的快樂吧（霧）
那么.有緣再見.
