Problem 14 その3
http://projecteuler.net/index.php?section=problems&id=14
コラッツ予想。1〜1,000,000 の数の中で1に収束するまでの遷移数が一番多い数は?
配列版。リストより効率がよい。
import List import Array n = 1 * 1000 * 1000 - 1 main = print $ maximumBy (\(_, a) (_, b) -> a `compare` b) $ assocs $ collatz n collatz n = memoCollatz where memoCollatz = listArray (1, n) $ 1 : [1 + (f i) | i <- [2..n]] where f i = let i' = if even i then i `div` 2 else 3 * i + 1 in if i' <= n then memoCollatz ! i' else 1 + f i'
27.05s user 0.39s system 99% cpu 27.696 total
速いな。
配列の ! はリストの !! と違って、Int じゃなく、Ix のインスタンスで構わない。
桁溢れを気にしなくてよくなったのかな。