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

Question

我一直在做项目Euler问题来学习Haskell.

我在途中遇到了一些障碍,但设法解决了问题14.问题是,起始数量低于1 000 000的产生了最长的Collat​​z链(链条开始后数量可以超过100万).

我尝试了几种解决方案但没有一种方法可行.我想反过来.从1开始并在数字超过一百万时终止但显然不起作用,因为这些条款可能高于一百万.

我已经尝试过记忆正常的算法,但是再次,数字太多,以及更多的记忆.

我已经读到最明显的解决方案应该适用于此,但出于某种原因,我的解决方案需要10秒以上才能达到最大值20 000.更别说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