Python-记忆和Collat​​z序列 [英] Python - Memoization and Collatz Sequence

问题描述

当我在做欧拉计划中的问题14 时，我发现我可以使用一件事称为备忘录来加快我的流程(我让它运行了15分钟，但它仍然没有返回答案).问题是，我该如何实施?我已经尝试过，但是遇到了keyerror(返回的值无效).这让我感到烦恼，因为我很确定，我可以对此应用备注，并更快地获取它.

When I was struggling to do Problem 14 in Project Euler, I discovered that I could use a thing called memoization to speed up my process (I let it run for a good 15 minutes, and it still hadn't returned an answer). The thing is, how do I implement it? I've tried to, but I get a keyerror(the value being returned is invalid). This bugs me because I am positive I can apply memoization to this and get this faster.

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)) 

谢谢.

推荐答案

还有一种很好的递归方法可以完成此操作，这可能比贫穷的解决方案要慢，但它与初始代码更相似，因此可能更容易理解.

There is also a nice recursive way to do this, which probably will be slower than poorsod's solution, but it is more similar to your initial code, so it may be easier for you to understand.

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序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！