Python-内存和Collat​​z序列

当我努力做Problem 14 in Project Euler时，我发现我可以使用一种称为备忘录的方法来加快我的过程(我让它运行了15分钟，但它仍然没有返回答案)。问题是，我该如何实现？我已经尝试过，但是遇到了keyerror(返回的值无效)。这让我感到烦恼，因为我很确定，我可以对此应用备注，并更快地获取它。

lookup = {}

def countTerms(n):
   arg = n
   count = 1
   while n is not 1:
      count += 1
      if not n%2:
         n /= 2
      else:
         n = (n*3 + 1)
      if n not in lookup:
         lookup[n] = count

   return lookup[n], arg

print max(countTerms(i) for i in range(500001, 1000000, 2))

谢谢。

最佳答案

还有一种不错的递归方法可以执行此操作，这可能比贫穷的解决方案要慢，但是它与您的初始代码更相似，因此您可能更容易理解。

lookup = {}

def countTerms(n):
   if n not in lookup:
      if n == 1:
         lookup[n] = 1
      elif not n % 2:
         lookup[n] = countTerms(n / 2)[0] + 1
      else:
         lookup[n] = countTerms(n*3 + 1)[0] + 1

   return lookup[n], n

print max(countTerms(i) for i in range(500001, 1000000, 2))

关于Python-内存和Collat​​z序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15488634/