今日は Problem 14。
cf. Project Euler – Problem 14
コラッツ問題の数列を求めるのは以前にやったのを流用。あとは力任せに…
module Main (main) where
collatz :: Int -> [Int]
collatz 1 = 1 : []
collatz n | n `mod` 2 == 0 = n : collatz (n `div` 2)
| otherwise = n : collatz (n * 3 + 1)
euler014 :: Int -> [Int]
euler014 n = snd $ foldl g (0, []) $ map f [1..n]
where
f x = ((length.collatz) x, x)
g (x,zs) (l,z) | x < l = (l, z:[])
| x == l = (x, z:zs)
| otherwise = (x, zs)
main :: IO ()
main = mapM_ (putStrLn.show) $ euler014 1000000
やったらあえなくスタックオーバーフローに。ありゃ。
^o^ >runhaskell euler014.hs *** Exception: stack overflow
100,000までだったらうまくいったので間違ってはいないと思う。たぶん数列がすごく長くなる数があるんだろうな。再挑戦はまた今度。
あと，ついでに書いておくと，各数の数列にはおなじ部分列が何度も出現する。これを覚えておけば計算量を少なくできるんだけど，メモ化のやり方がわからない。