首页 文章

Fibonacci在缓存的解决方案中

提问于
浏览 次
1

我在c中学到了对斐波那契的记忆解决方案

#include<iostream>
using namespace std;
int F[51];

int fib(int n) {
    if (n<=1)
    {
        return n;
    }
    if (F[n] != -1)
    {
        return F[n];
    }
    F[n] =  fib(n-1) + fib(n-2);
    return F[n];
}

int main()
{   
    for (int i=0; i<51; i++)
    {
        F[i] = -1;
    }
    int n;
    cout<<"Give me an n: ";
    cin>>n;
    int result = fib(n);
    cout<<result;
}

它运作正常，

$ g++ fibonacci.cpp 
$ ./a.out
Give me an n: 10
55

尝试用python重现它

In [2]: %paste                                                                                                        
F:List = [-1] * 50

def fib2(int:n) -> int:

    if n < 2:
        return n
    if F[n] != -1:
        return F[n]
    F[n] =  fib2(n-1) + fib2(n-2)
    return F[n]

print(fib2(10))

不过，它报告 RecursionError: maximum recursion depth exceeded in comparison

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-2-5e5ce2f4b1ad> in <module>
     10     return F[n]
     11 
---> 12 print(fib2(10))

<ipython-input-2-5e5ce2f4b1ad> in fib2(int)
      7     if F[n] != -1:
      8         return F[n]
----> 9     F[n] =  fib2(n-1) + fib2(n-2)
     10     return F[n]
     11 

... last 1 frames repeated, from the frame below ...

<ipython-input-2-5e5ce2f4b1ad> in fib2(int)
      7     if F[n] != -1:
      8         return F[n]
----> 9     F[n] =  fib2(n-1) + fib2(n-2)
     10

双重检查python解决方案与正在进行的解决方案具有相同的逻辑 .

我的代码有什么问题 .

python fibonacci memoization

3 回答

  • 0

    类型提示不正确，这对我有用：

    # fixed type hint
F:list = [-1] * 50

# fixed type hint
def fib2(n:int) -> int:
    if n < 2:
        return n
    if F[n] != -1:
        return F[n]
    F[n] = fib2(n-1) + fib2(n-2)
    return F[n]

fib2(49)
=> 7778742049
    回复于
  • 2

    问题在于你的类型提示：它应该是 n: int 而不是 int: n .

    在普通脚本中，您将获得 NameError ，如下所示：

    def fib2(int: n):
    pass

---------------------------------------------------------------------------

NameError                                 Traceback (most recent call last)
<ipython-input-19-2a2734193e18> in <module>()
----> 1 def fib2(int: n):
      2     pass

NameError: name 'n' is not defined

    在你的情况下发生的事情是你可能在've run before in IPython. So, you don'得到一个'NameError'的单元格中定义了 n ，但你的参数名为 int ，函数中使用的 n 是你以前用过的全局 n . 如果它是一个大于2的数字，您的递归调用将永远不会结束：

    n = 3  # might have been in some other cell

    F = [-1] * 101

def fib2(int: n):

    if n < 2:
        return n
    if F[n] != -1:
        return F[n]
    F[n] =  fib2(n-1) + fib2(n-2)
    return F[n]

print(fib2(100))
---------------------------------------------------------------------------

[...]

RuntimeError: maximum recursion depth exceeded in comparison

    只需按正确的顺序写出类型提示，一切都很好：

    F = [-1] * 101

def fib2(n: int):
    if n < 2:
        return n
    if F[n] != -1:
        return F[n]
    F[n] =  fib2(n-1) + fib2(n-2)
    return F[n]

print(fib2(100))
# 354224848179261915075
    回复于
  • 1

    试试这个：

    fib_aux = [-1] * 50
def fib(n):
    if n < 2:
        return n
    else:
        if fib_aux[n] < 0:
            fib_aux[n] = fib(n - 1) + fib(n - 2)
        return fib_aux[n]

    使用列表，您也可以这样做以避免递归：

    fib_aux = [0, 1]
def fib(n):
    m = len(fib_aux)
    for i in range(m, n + 1):
        fib_aux.append(fib_aux[i - 1] + fib_aux[i - 2])
    return fib_aux[n]

    您可以使用常规记忆功能，而不是管理列表：

    def memoize(f):
    h = {}
    def g(*arg):
        if arg not in h:
            h[arg] = f(*arg)
        return h[arg]
    return g

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

    有关Python装饰器（@）的更多信息，请参见this question .

    请注意，由于递归限制，第一个和最后一个方法可能会失败 . 第二种解决方案不使用递归 . 但是，如果对于大型 n 只需要 fib(n) 的几个值，则使用参数加倍有更快的解决方案（请参阅Math.SE上的this） .

    回复于

相关问题