Problem 14

Haskell

今日は 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までだったらうまくいったので間違ってはいないと思う。たぶん数列がすごく長くなる数があるんだろうな。再挑戦はまた今度。


あと，ついでに書いておくと，画数の数列にはおなじ部分列が何度も出現する。これを覚えておけば計算量を少なくできるんだけど，メモ化のやり方がわからない。