haskell - 优化 Haskell 中最长的 Collat​​z 链

Question

我一直在做项目欧拉问题来学习 Haskell。

我在路上遇到了一些颠簸，但设法解决了问题 14。问题是，哪个起始数字小于 1 000 000 会产生最长的 Collat​​z 链(链开始后允许数字超过 100 万)。

我已经尝试了几个解决方案，但都没有奏效。我想反其道而行之。从 1 开始，当数字超过 100 万时终止，但这显然行不通，因为项可以超过 100 万。

我试过内存普通算法，但同样，数字太大，内存太多。

我读到最明显的解决方案应该适用于此，但出于某种原因，我的解决方案需要 10 多秒才能达到 20000 的最大值。更不用说 100 万了。

这是我目前使用的代码:

reg_collatz 1 = 1
reg_collatz n
        | even n        = 1 + reg_collatz (n `div` 2)
        | otherwise     = 1 + reg_collatz (n * 3 + 1)

solution = foldl1 (\a n -> max a (reg_collatz n)) [1..20000]

非常欢迎任何帮助。

Answer 1

答案很简单:不要记住超过一百万的数字，而要记住低于一百万的数字。

module Main where

import qualified Data.Map as M
import Data.List
import Data.Ord

main = print $ fst $ maximumBy (comparing snd) $ M.toList ansMap

ansMap :: M.Map Integer Int
ansMap = M.fromAscList [(i, collatz i) | i <- [1..1000000]]
  where collatz 1 = 0
        collatz x = if x' <= 1000000 then 1 + ansMap M.! x'
                                     else 1 + collatz x'
          where x' = if even x then x `div` 2 else x*3 + 1