to site top page

Problem 18, 67 - Project Euler

num = 
[[75],
[95,64],
[17,47,82],
[18,35,87,10],
[20,4,82,47,65],
#以下略
#Triangle(Problem18:373Byte)
#Triangle(Problem67:15250Byte)

st = num.length - 2
for i in 0..st
    n = st - i
    for j in 0..n
        num[n][j] += (num[n+1][j] + num[n+1][j+1] + (num[n+1][j] - num[n+1][j+1]).abs ) / 2
    end
end
puts num[0][0]

上からたどると,Problem18なら2の14乗で16384通り,Problem67なら2の99乗で633825300114114700748351602688通り. Problem18なら,まだBrute Forceが通用する量だが,Problem67でBrute Forceは使えない.というか,使うと終わらない. 仮に1G通り/s検証出来たとして,最大で約6*10^20秒,86400s/dayで一年365日が31436000秒.7桁落としたところで2*10^13年. ま,終わる頃には地球なんて無いですね.

故に逆から計算.大小比較して大きい方を上に加える.それの繰り返し.計算ステップが4950.激減です.

内側のfor文内部は,まぁ,ifで振り分けた方がわかりやすいかも知れない.

num[n][j] += num[n+1][j] if num[n+1][j] >= num[n+1][j+1]
num[n][j] += num[n+1][j+1] if num[n+1][j] < num[n+1][j+1]

みたいな.

can't load my result

最近の記事(5件分)

する事

そのうち記事にするかもリスト

欲しい本