欧拉计划 #14：考拉兹猜想 - 有哪些有效利用记忆化和速度的算法？

Question

欧拉计划 #14：考拉兹猜想 - 有哪些有效利用记忆化和速度的算法？

algorithmperformancebig-odynamic-programmingmemoization

3

链接到问题：https://projecteuler.net/problem=14 所以我使用了一种相当“平凡”的 R 中的记忆化实现来解决这个问题。基本上，我只是从 1:1,000,000 开始计数，并计算得到 1 所需的 Collatz 应用次数。如果我遇到一个小于当前迭代的数字，则只需将该数字的“链”添加到当前序列中。

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来说也是如此，但我越想这个问题，就越觉得它很有趣。

从空间和运行时间的效率方面来看，似乎有大量不同的方法可以处理它。也许倒序循环？也许先运行奇数或偶数，然后再运行另一半？也许在递增时保留中间结果而不仅仅是终端链长度？可能还有一些更加“数学”而不是直接与动态规划相关的想法。有没有人思考过这个问题/算法并能提供一些其他可能更有效的实现呢？

- Frank P.

1

只是一些建议：根据这些变量的命名方式，我在合理的时间内无法弄清楚代码的功能。有待改进。将while循环拆分为一个函数将有助于解开控制流的混乱。 - usr

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tony Tuttle · Accepted Answer

您正在以严格的1:1000000顺序进行记忆化。然而，没有理由不在第一次看到值时记忆化。例如，从3开始得到的序列3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1。您可以除了仅仅记忆化3之外，还可以记忆化10, 5, 16, 8, 4。

这将减少操作次数，也许会显著地减少。继续上面的示例，第一次记忆化4可以节省后来所需的2步，而记忆化5则又节省了3步。这些节省下来的步骤似乎应该很快就会像雪球一样增加。