2

我使用以下代码解决了Project Euler #14 ：

import time
start_time = time.time()
def collatz_problem(n):
    count = 0
    while n!=1:
        if n%2==0:
            n = n/2
            count = count+1
        elif n%2!=0:
            n = 3*n+1
            count = count +1
    return count+1


def longest_chain():
    max_len,num = 1,1
    for i in xrange(13,1000000):
        chain_length = collatz_problem(i)
        if chain_length > max_len:
            max_len = chain_length
            num = i

    return num

print longest_chain()
print time.time() - start_time, "seconds"

上述解决方案需要~35 seconds运行。现在，我从这里尝试了另一种解决方案。

解决方案：

import time
start_time = time.time()
cache = { 1: 1 }
def chain(cache, n):
     if not cache.get(n,0):
         if n % 2: cache[n] = 1 + chain(cache, 3*n + 1)
         else: cache[n] = 1 + chain(cache, n/2)
     return cache[n]
m,n = 0,0
for i in xrange(1, 1000000):
    c = chain(cache, i)
    if c > m: m,n = c,i

print n
print time.time() - start_time, "seconds"

现在，这个解决方案只需要~3.5 seconds.

第一个问题：

现在，由于我是 python 初学者，我不明白为什么这两种方法有这么大的区别，以及如何修改我的代码以使其更有效。

第二个问题：

在解决项目欧拉问题时，是否应该牢记任何时间限制，并且我的代码真的那么低效。

4

1 回答 1

8

在第一个版本中，您可能会多次计算某些链的长度，因为它们是其他链中的子链。

在第二个解决方案中，由于缓存，您只计算每个链的长度一次。这种优化技术称为记忆化。

记忆化的一个更引人注目的例子是斐波那契数列的计算。这是简单的递归解决方案：

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

它需要指数级的时间，因为fib(n)评估fib(n-1)和fib(n-2)，但fib(n-1)也评估fib(n-2)，所以你最终会再次进行完全相同的计算。尝试fib(35)使用此算法计算或更高。

通过缓存fib(x)for each的结果，x您可以避免重新计算相同的结果，从而将性能提高到线性时间。

def fib2(n):
    if n < 2:
        return n
    elif n in cache:
        return cache[n]
    else:
        result = fib2(n-1) + fib2(n-2)
        cache[n] = result
        return result

有关的

于 2012-07-28T08:15:22.933 回答