问题链接: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 也是如此,但我越想这个问题,就越觉得它很有趣。
似乎有很多不同的方法可以在空间和运行时方面提高效率。也许向后循环?也许先跑完奇数或偶数,再跑另一半?也许在递增时保留中间结果而不仅仅是末端链长度?可能还有一些想法本质上更“数学”,而不是与动态规划直接相关。有没有人考虑过这个问题/算法并且可以提供一些其他可能更有效的实现?
最佳答案
您正在按照 1:1000000 的严格顺序进行内存。但是,没有理由在您第一次看到一个值时不记住它。例如,从 3
开始给出序列 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
。除了仅内存 3
之外,您还可以内存 10, 5, 16, 8, 4
。
这将减少操作的数量,也许会大大减少。继续上面的例子,当你第一次看到它时记住 4
节省了以后内存它所需的 2 个步骤,而内存 5
又节省了 3 个步骤。看起来这些保存的步骤应该很快滚雪球。
关于algorithm - 欧拉计划 #14 : Collatz Conjecture - What are some algorithms to utilize memoization/speed effectively?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31351173/