Python中的记忆斐波那契算法

我有这种记忆技术,可以减少获得斐波那契序列号的呼叫数量:

def fastFib(n, memo):

global numCalls

numCalls += 1

print 'fib1 called with', n

if not n in memo:

memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)

return memo[n]

def fib1(n):

memo = {0:1, 1:1}

return fastFib(n, memo)

numCalls = 0

n = 6

res = fib1(n)

print 'fib of', n,'=', res, 'numCalls = ', numCalls

但是我被困在这里:memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)这里memo = {0:1,

1:1}。每次我想获取数字fib时,如何准确减少通话次数?

回答:

您应该memo[n]始终返回,不仅要进行不安全的查找(的最后一行fastFib()):

def fastFib(n, memo):

global numCalls

numCalls += 1

print 'fib1 called with', n

if not n in memo:

memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)

#this should be outside of the if clause:

return memo[n] #<<<<<< THIS

这样可以减少调用次数,因为对于n您的每个值,实际上最多只能计算和递归一次,从而将递归调用的次数限制为O(n)2n调用上限),而不必一次又一次地有效地重新计算相同的值进行指数递归调用。

fib(5)的一个小例子,其中每一行都是递归调用:

天真的方法:

f(5) = 

f(4) + f(3) =

f(3) + f(2) + f(3) =

f(2) + f(1) + f(2) + f(3) =

f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) =

1 + f(0) + f(1) + f(2) + f(3) =

2 + f(1) + f(2) + f(3) =

3 + f(2) + f(3) =

3 + f(1) + f(0) + f(3) =

3 + 1 + f(0) + f(3) =

5 + f(3) =

5 + f(2) + f(1) =

5 + f(1) + f(0) + f(1) =

5 + 1 + f(0) + f(1) =

5 + 2 + f(1) =

8

现在,如果您使用备忘录,则无需重新计算很多事情(例如f(2),它被计算了3次),您将获得:

f(5) = 

f(4) + f(3) =

f(3) + f(2) + f(3) =

f(2) + f(1) + f(2) + f(3) =

f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) =

1 + f(0) + f(1) + f(2) + f(3) =

2 + f(1) + f(2) + f(3) =

3 + f(2) + f(3) = {f(2) is already known}

3 + 2 + f(3) = {f(3) is already known}

5 + 3 =

8

如您所见,第二个比第一个短,并且数字(n)越大,该差异就越大。

以上是 Python中的记忆斐波那契算法 的全部内容, 来源链接: utcz.com/qa/399939.html

回到顶部