algorithm - 欧拉计划 #14 : Collatz Conjecture - What are some algorithms to utilize memoization/speed effectively?

Question

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

所以我在 R 中使用一个相当“简单”的记忆化实现解决了这个问题。基本上，我只是从 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。除了仅内存 3 之外，您还可以内存 10, 5, 16, 8, 4。

这将减少操作的数量，也许会大大减少。继续上面的例子，当你第一次看到它时记住 4 节省了以后内存它所需的 2 个步骤，而内存 5 又节省了 3 个步骤。看起来这些保存的步骤应该很快滚雪球。