缓存解决方案中的斐波那契数列

Question

我在 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 解决方案是否与正在进行的解决方案具有相同的逻辑。

我的代码有什么问题。

Answer 1

问题在于您的类型提示：它应该是n: int而不是int: n.在普通脚本中，您会得到NameError如下所示：def fib2(int: n):&nbsp; &nbsp; pass---------------------------------------------------------------------------NameError&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Traceback (most recent call last)<ipython-input-19-2a2734193e18> in <module>()----> 1 def fib2(int: n):&nbsp; &nbsp; &nbsp; 2&nbsp; &nbsp; &nbsp;passNameError: name 'n' is not defined在您的情况下发生的情况是您可能已经n在之前在 IPython 中运行过的单元格中进行了定义。因此，您不会得到“NameError”，但您的参数会得到 name int，并且n函数中使用的是n您之前在某处使用过的全局变量。如果它是一个大于 2 的数字，您的递归调用将永远不会结束：n = 3&nbsp; # might have been in some other cellF = [-1] * 101def fib2(int: n):&nbsp; &nbsp; if n < 2:&nbsp; &nbsp; &nbsp; &nbsp; return n&nbsp; &nbsp; if F[n] != -1:&nbsp; &nbsp; &nbsp; &nbsp; return F[n]&nbsp; &nbsp; F[n] =&nbsp; fib2(n-1) + fib2(n-2)&nbsp; &nbsp; return F[n]print(fib2(100))---------------------------------------------------------------------------[...]RuntimeError: maximum recursion depth exceeded in comparison只需按正确的顺序编写类型提示，一切都很好：F = [-1] * 101def fib2(n: int):&nbsp; &nbsp; if n < 2:&nbsp; &nbsp; &nbsp; &nbsp; return n&nbsp; &nbsp; if F[n] != -1:&nbsp; &nbsp; &nbsp; &nbsp; return F[n]&nbsp; &nbsp; F[n] =&nbsp; fib2(n-1) + fib2(n-2)&nbsp; &nbsp; return F[n]print(fib2(100))# 354224848179261915075

Answer 2

类型提示不正确，这对我有用：# fixed type hintF:list = [-1] * 50# fixed type hintdef fib2(n:int) -> int:&nbsp; &nbsp; if n < 2:&nbsp; &nbsp; &nbsp; &nbsp; return n&nbsp; &nbsp; if F[n] != -1:&nbsp; &nbsp; &nbsp; &nbsp; return F[n]&nbsp; &nbsp; F[n] = fib2(n-1) + fib2(n-2)&nbsp; &nbsp; return F[n]fib2(49)=> 7778742049