Project Euler 079~083
關(guān)于啥是Project Euler 詳見 https://projecteuler.net/about? ? ??
觀前聲明：? ? ? ? ? ? ?
這是個人興趣使然的對自己入坑pe的記錄，僅提供思路和部分代碼；
各個方面肯定都是有著優(yōu)化與提升空間的，甚至在許多大佬看來這應(yīng)該是初學(xué)者的淺薄而未經(jīng)剪枝的丑碼，如果能幫到有興趣的人自是最好，也歡迎能醍醐灌頂?shù)纳疃扔懻摗??
大佬看到了笑笑就行，還請輕噴。
帶著惡意，抬杠者...俺也噴不過您，也不能拿您咋樣...畢竟這只是我個人興趣使然的行為或者說是學(xué)習(xí)記錄分享。?（說是記錄，但因?yàn)槭窃缦葘懙乃云鋵?shí)是在各種意義上公開處刑和吐槽自己 并嘗試補(bǔ)救優(yōu)化）
語言是c++，用的VS平臺
前排：79水題，80題用了Frazer Jarvis的關(guān)于使用減法來迭代求平方根的方法；81，82，83屬于動態(tài)規(guī)劃系列題（？熟悉的組合）
Passcode derivation
Problem 79
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file,?keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.
keylog.txt：https://projecteuler.net/project/resources/p079_keylog.txt
網(wǎng)上銀行通用的一種加密方法是向用戶詢問密碼中的三位隨機(jī)字符。例如，如果密碼是 531278，那么銀行可以詢問第 2,3,5 位字符，預(yù)期的回復(fù)應(yīng)該是317。keylog.txt中包含 50 次成功的登錄嘗試，已知三位字符總是按順序詢問，分析文件并找出可能的最短的密碼（長度未知）。
keylog如下：
319 680 180 690 129 620 762 689 762 318 368 710 720 710 629 168 160 689 716 731 736 729 316 729 729 710 769 290 719 680 318 389 162 289 162 718 729 319 790 680 890 362 319 760 316 729 380 319 728?716
實(shí)際上就50個字符，這道題我是純手算過的。
只要時刻注意? 1.滿足最短的密碼；2.總是按順序詢問? ?即可
可以看到4，5一次都沒出現(xiàn)，那么從最少數(shù)字的情況來考慮，沒有4，5；
那么不妨假設(shè)就只有8個數(shù)字，從第一個數(shù)字串開始，不斷根據(jù)數(shù)字出現(xiàn)順序改變數(shù)字的位置或添加新數(shù)字：
（注意每次變更需與之前的判斷不矛盾，不然就要繼續(xù)變更，不能變更時說明要加數(shù)字）
比如一開始是319，第二個是680，那么不妨假設(shè)數(shù)字是319680，然后是180，符合條件，再然后是690，說明6在9前面，那么改成316980；
然后是129，1，9之間有個2，那么變?yōu)?162980，620不變，762說明6前有個7，變?yōu)?1762980，689說明8在9前，改成31762890，318不變，368不變，710說明7在1前面，改成37162890，720不變，710不變，629不變，168不變，160不變，689不變，716不變，731說明7在3前，改為73162890，之后可逐一驗(yàn)證均無需改變。
（這道題還可用拓?fù)渑判驅(qū)⒚课粩?shù)字可能的后位數(shù)字列出 相關(guān)知識請自行搜索）
ans：73162890
Square root digital expansion
Problem 80
It is well known that if the Square root of a natural number is not an integer, then it is irrational. The decimal expansion of such Square roots is infinite without any repeating pattern at all.
The Square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475.
For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational Square roots.
眾所周知如果一個整數(shù)的平方根不是一個整數(shù)，那么這個平方根就是一個無理數(shù)，這種平方根的小數(shù)表示是無限不循環(huán)的。2的平方根是1.41421356237309504880...，它的前一百位數(shù)字的和是475。
對于前一百個自然數(shù)，找出其中無理平方根的小數(shù)部分前一百位的總和。
在《數(shù)值分析》中有許多關(guān)于方程數(shù)值解迭代的方法，比如牛頓迭代，二分，拋物線法，割線法等，但對于本題要求的100位的高精度而言，計算機(jī)浮點(diǎn)值難免會有誤差，所以本題使用了一種收斂不快但必定精確的方法。
此法出自Frazer Jarvis的論文Square roots by subtraction? ?
詳細(xì)原理可自行查詢原文，我只說說算法本身。
如果要求n的平方根，初始時令(a,b)=(5n,5)
重復(fù)以下步驟：
如果a≥b，則(a,b)->(a-b,b+10)
如果a<b，則a->100*a,在b的個位數(shù)前加一個0。
b代表n的平方根
比如2的平方根初始時(a,b)=(10,5)
(10,5)->(5,15)->(500,105)->(395,115)->(280,125)->(155,135)->(20,145)->(2000,1405)->(595,1415)->(59500,14105)->(45395,14115)->(31280,14125)->(17155,14135)->(3020,14145)->(302000,141405)->160595,141415)->(19180,141425)->(1918000,1414205)..
可見，b在不斷接近沒有小數(shù)點(diǎn)的根號2。
因?yàn)?00位，所以c++勢必要用到大整數(shù)，但這個算法與大整數(shù)可謂十分契合，直接模擬即可
（為了與大整數(shù)加法，乘法等一致保持A[0]儲存位數(shù)，其余部分逆序儲存數(shù)的性質(zhì)，所以減法的寫法略微繁瑣，之前好像因?yàn)闆]用到所以都沒給出？）
再寫一個函數(shù)使用2個規(guī)則迭代，在主函數(shù)中跑100內(nèi)的非平方數(shù)即可。
ans：40886
上兩題難度分別為5%，20%.
81，82，83是關(guān)于路徑的動態(tài)規(guī)劃，雖說83我用的dijkstra...
Path sum: two ways
Problem 81
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by?only moving to the right and down, is indicated in bold red and is equal to 2427.
Find the minimal path sum from the top left to the bottom right by only moving right and down in?matrix.txt, a 31K text file containing an 80 by 80 matrix.
matrix.txt：https://projecteuler.net/project/resources/p081_matrix.txt
在5×5的矩陣中從左上角移動到右下角，每次只能向下或向右移動，路徑的最小值是2427，在matrix.txt中有一個80×80的矩陣，找到依此規(guī)則移動的路徑的最小值。
這其實(shí)是簡單的動態(tài)規(guī)劃問題，若以op[i][j]表示從當(dāng)前位置(i,j)移動到右下角的路徑最小值：
以上圖的5×5矩陣為例，比如op[5][5]=A[5][5]，因?yàn)楸旧硪言诮K點(diǎn)，op[4][5]=A[4][5]+op[5][5],
op[5][4]=A[5][4]+op[5][5];
op[4][4]=A[4][4]+min{op[4][5],op[5][4]}
所以狀態(tài)轉(zhuǎn)移方程為：op[i][j]=A[i][j]+min(op[i+1][j],op[i][j+1]);注意一下邊界條件即可直接在主函數(shù)實(shí)現(xiàn)（這里我的數(shù)組A已經(jīng)儲存了80×80矩陣）：
ans：427337
Path sum: three ways
Problem 82
NOTE: This problem is a more challenging version of?Problem 81.
The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.
Find the minimal path sum from the left column to the right column in?matrix.txt?, a 31K text file containing an 80 by 80 matrix.
從最左側(cè)（任意位置）移動到最右側(cè)（任意位置），每次只能向上或下或右移動一步，權(quán)值最短路徑如圖所示，最短路徑和為：994，在matrix.txt中（與上題相同的文件）的80×80矩陣中求出最短路徑和。
顯然，這也是個動態(tài)規(guī)劃問題。
對于最后一列，顯然op[i][j]=A[i][j]
對于倒數(shù)第二列，op[i][j]不一定為A[i][j]+op[i][j+1]，實(shí)際上，若該列中能有更小的op[k][j]
使得A[i][j]+op[i][j+1]>A[i][j]+A[i+1][j]+...+A[k-1][j]+op[k][j]? 那么對于op[i][j]最短路徑顯然是先到A[k][j]再繼續(xù)移動，所以從最后一列開始向前規(guī)劃的思路由此誕生：
狀態(tài)轉(zhuǎn)移方程：
op[i][j]=min(op[k][j+1]+A[k][j]+...+A[i][j])
k為某一行，A[k][j]+...+A[i][j]中為k到i的所有A[m][j] i<=m<=k或k<=m<=i
ans：260324
Path sum: four ways
Problem 83
NOTE: This problem is a significantly more challenging version of?Problem 81.
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.
Find the minimal path sum from the top left to the bottom right by moving left, right, up, and down in?matrix.txt??a 31K text file containing an 80 by 80 matrix.
上兩題的矩陣，上下左右4個方向...
這道題能dp，但我選擇dijkstra最短路徑.
把點(diǎn)權(quán)處理一下模擬成邊權(quán)即可。
大致說下dijkstra算法思想：
聲明一個數(shù)組dis來保存源點(diǎn)到各個頂點(diǎn)的最短距離和一個保存已經(jīng)找到了最短路徑的頂點(diǎn)的集合：S，初始時，原點(diǎn) s 的路徑權(quán)重被賦為 0 （dist[s] = 0）。若對于頂點(diǎn) s 存在能直接到達(dá)的邊（s,m），則把dist[m]設(shè)為w（s, m）,同時把所有其他（s不能直接到達(dá)的）頂點(diǎn)的路徑長度設(shè)為無窮大。初始時，集合S只有頂點(diǎn)s。
然后，從dist數(shù)組選擇最小值，則該值就是源點(diǎn)s到該值對應(yīng)的頂點(diǎn)的最短路徑，并且把該點(diǎn)加入到T中。
然后，我們需要看看新加入的頂點(diǎn)是否可以到達(dá)其他頂點(diǎn)并且看看通過該頂點(diǎn)到達(dá)其他點(diǎn)的路徑長度是否比源點(diǎn)直接到達(dá)短，如果是，那么就替換這些頂點(diǎn)在dist中的值。
然后，又從dist中找出最小值，重復(fù)上述動作，直到S中包含了圖的所有頂點(diǎn)
還是建議沒聽過的話先百度下.搞懂后再來看我的改編版吧：
首先設(shè)置一個初始的Ds0數(shù)組，將初始邊權(quán)定義為相鄰兩點(diǎn)的點(diǎn)權(quán)之和
然后開始dijkstra
需要注意的是，80×80的矩陣中，(i,j)點(diǎn)的編號為80*i+j
編號為n的點(diǎn)的行為n/80,列為n%80
所以新的一輪的路徑較短的點(diǎn)的判斷為：
dist[u] + A[j / 80][j % 80] < dist[j]
S[u]=1表示點(diǎn)u加入集合S.
ans：425185
3道題難度分別為10% 20% 25%...
希望這月底前能更到100吧 然后我就可以（）了.
預(yù)告一下.84是無聊的模擬題.說下思路就過吧 （絕不是我為了節(jié)能）
