项目Euler#14:Collat​​z猜想 - 有效利用记忆/速度的算法是什么？

Question

链接到问题:https://projecteuler.net/problem=14

所以我在R中使用相当"琐碎"的memoization实现解决了这个问题.基本上,我只是从1:1,000,000计算并计算到达1所需的collat​​z应用程序数量.如果我遇到的数字少于在当前的迭代中,我只是将该数字的'链'添加到当前序列中.

R代码:

collatz <- function(n) {

  if(n %% 2 == 0) return(n / 2)
  else return(3 * n + 1)

}

chains <- rep(0, 1e6)

for(i in 1:length(chains)) {

  n <- i
  iter <- 0

  while(n != 1) {

    n <- collatz(n)
    iter <- iter + 1

    if(n < i) {
      iter <- iter + chains[n]
      break
    }

  }

  chains[i] <- iter

}

which.max(chains)

现在这个代码运行得相对较快,即使是R,但是我对这个问题的思考越多,我发现它就越有趣.

似乎有很多不同的方法可以在空间和运行时方面提高效率.也许循环倒退？也许首先通过奇数或偶数,然后再做另一半？也许保持中间结果而不仅仅是递增时的终端链长度？可能还有一些想法本质上更"数学"而不是直接与动态规划相关.是否有人考虑过这个问题/算法并且可以提供其他一些可能更有效的实现？

Answer 1

你正在以严格的1:1000000命令进行记忆.但是,没有理由在第一次看到值时不记忆.例如,从3给出序列开始3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.10, 5, 16, 8, 4除了记忆之外,您还可以进行记忆3.

这将大大减少操作次数.继续上面的例子,4第一次看到它时的记忆5保存了以后记忆它需要的两个步骤,并且记忆保存了另外3个步骤.似乎这些保存的步骤应该很快滚雪球.