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