亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

緩存解決方案中的斐波那契數列

緩存解決方案中的斐波那契數列

慕尼黑5688855 2021-09-11 10:57:32
我在 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 解決方案是否與正在進行的解決方案具有相同的邏輯。我的代碼有什么問題。
查看完整描述

3 回答

?
慕田峪7331174

TA貢獻1828條經驗 獲得超13個贊

問題在于您的類型提示:它應該是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


查看完整回答
反對 回復 2021-09-11
?
心有法竹

TA貢獻1866條經驗 獲得超5個贊

類型提示不正確,這對我有用:


# 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


查看完整回答
反對 回復 2021-09-11
  • 3 回答
  • 0 關注
  • 289 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號