擅长:python、mysql、java
<p>Collatz序列是使用<a href="http://en.wikipedia.org/wiki/Dynamic_programming" rel="nofollow"><em>"dynamic programming"</em> techniques</a>的好机会。来自给定数字<code>n</code>的序列的长度将始终相同,因此您可以存储该结果,并在将来的某个序列中再次到达<code>n</code>时使用它。例如,使用修饰符来<a href="http://en.wikipedia.org/wiki/Memoization" rel="nofollow"><em>"memoize"</em></a>结果:</p>
<pre><code>def memo(func):
def wrapper(*args):
if args not in wrapper.cache:
wrapper.cache[args] = func(*args)
return wrapper.cache[args]
wrapper.cache = {}
return wrapper
@memo
def collatz_length(n):
if n == 1:
return 1
elif n % 2:
return 1 + collatz_length((3 * n) + 1)
return 1 + collatz_length(n // 2)
</code></pre>
<p>现在,如果我们运行程序的初始值为<code>n</code>,您可以看到<code>cache</code>被预先计算的结果填充,从而加快了将来的调用(以牺牲存储空间为代价—这是一种典型的编程权衡):</p>
^{pr2}$
<p>这可以在大约1.5s内得出结果:</p>
<pre><code>>>> from timeit import timeit
>>> timeit('max(collatz_length(x+1) for x in range(10**6))',
setup='from __main__ import collatz_length',
number=1)
1.5072860717773438
</code></pre>