Python中的记忆斐波那契算法

问题描述

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

I have this memoization technique to reduce the number of calls getting a Fibonacci sequence number:

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时，如何确切地减少通话数量？

But i am stuck at here: memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo) and here memo = {0:1, 1:1}. How is it exactly reducing the number of calls each time i want to get fib of a number?

推荐答案

您应该返回 memo [n] 总是，不仅在不成功的查找中（ fastFib（）的最后一行）：

You should return memo[n] always, not only on unseccesful look up (last line of 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）（<$ c $的上限） c> 2n 个发票），而不是一遍又一遍地重新计算相同的值，而是有效地使递归调用次数成指数增长。

The number of calls is reduced this way, because for each value of n you actually compute and recurse from at most once, limitting the number of recursive calls to O(n) (upper bound of 2n invokations), instead of recomputing the same values over and over again, effectively making exponential number of recursive calls.

一个小例子对于fib（5），其中每一行都是递归调用：

A small example for fib(5), where each line is a recursive invokation:

天真的方法：

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次），您将获得：

Now, if you use memoization, you don't need to recalculate a lot of things (like f(2), which was calculated 3 times) and you get:

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 ）越大，这种差异越明显。

As you can see, the second is shorter than the first, and the bigger the number (n) becomes, the more significant this difference is.

这篇关于Python中的记忆斐波那契算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！