斐波那契數列

寫一個函數，輸入 n ，求斐波那契（Fibonacci）數列的第 n 項（即 F(N)）。斐波那契數列的定義如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契數列由 0 和 1 開始，之后的斐波那契數就是由之前的兩數相加而得出。

答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請返回 1。

示例 1：

輸入：n = 2
輸出：1
示例 2：

輸入：n = 5
輸出：5

# 解法一 遞歸解法 # 由遞推公式可得 f(n) = f(n-1) + f(n-2) def fei_bo_na_qie_1(n):if n == 0 or n == 1:return nreturn fei_bo_na_qie_1(n-1) + fei_bo_na_qie_1(n-2)# 由于遞歸的時間復雜度呈指數級增長 # 當n的值比較大的時候 是非常非常耗時的(經檢驗n=35的時候 耗時已經超過20s) # 為了優化此問題 我們添加一個備忘錄 我們可以在遞歸函數外面嵌套一個非遞歸的殼 def fei_bo_na_qie_2(n, mem):if n == 0 or n == 1:return nif mem[n] is not None:return mem[n]mem[n] = fei_bo_na_qie_2(n - 1, mem) + fei_bo_na_qie_2(n - 2, mem)return mem[n]def main(n):mem = [None] * (n + 1)return fei_bo_na_qie_2(n, mem)# 解法二 循環求余法 def fei_bo_na_qie_3(n):a, b = 0, 1for _ in range(n):a, b = b, a + breturn a

總結

以上是生活随笔為你收集整理的python 斐波那契数列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。