project euler problem 15
この問題はスタートである左上をを上へ右下を下へ持っていき各点を通る組み合わせは以下の図の様になる。
これはパスカルの三角形である。
ということで求めるものは一辺nマスの場合、(a+b)^(2*n)の真ん中の係数が求めるもの。
パスカルの三角形は以前 id:nobsunに教えてもらったものを流用して…
Prelude Data.Array> let cs=[1]:[zipWith (+) ([0]++c) (c++[0]) | c <- cs ] in maximum $ cs !! (2*2) 6 (0.01 secs, 2629016 bytes) Prelude Data.Array> let cs=[1]:[zipWith (+) ([0]++c) (c++[0]) | c <- cs ] in maximum $ cs !! (2*3) 20 (0.01 secs, 3146608 bytes) Prelude Data.Array> let cs=[1]:[zipWith (+) ([0]++c) (c++[0]) | c <- cs ] in maximum $ cs !! (2*20) 137846528820 (0.01 secs, 3156772 bytes)
この問題はパスカルの三角形であることに気がつくのが大変だった。