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

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.outGive me an n: 1055尝试用python重现它In [2]: %paste                                                                                                        F:List = [-1] * 50def 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):

    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

在您的情况下发生的情况是您可能已经n在之前在 IPython 中运行过的单元格中进行了定义。因此，您不会得到“NameError”，但您的参数会得到 name 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

Answer 2

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

# 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