Problem 14

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

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

カテゴリー: Haskell パーマリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください