資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學用 Python 查詢斐波那契數列在第 n 項結果的程式
假設我們有一個數字 n。我們必須找到前 n 個斐波那契數列項之和（斐波那契數列最多 n 個項）。如果答案太大，則返回結果取餘 10^8 + 7。
所以，如果輸入像 n = 8，則輸出將是 33，因為前幾個斐波那契數列項是 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33
要解決此問題，我們將遵循以下步驟 −
- m := 10^8+7
- memo := 一個新對映
- 定義一個函式 solve()。這將獲取 n，m
- 如果 memo 中有 n，則
- 返回 memo[n]
- 當 n < 2 時，memo[n] := n；否則 (solve(n-1, m) +solve(n-2, m)) mod m
- 返回 memo[n]
- 從主方法獲取 memo 值列表，並計算其總和。
示例
讓我們看看以下實現，以獲得更好的理解 −
m = 10**8+7
memo = {}
def solve(n, m):
if n in memo:
return memo[n]
memo[n] = n if n < 2 else (solve(n-1, m)+solve(n-2, m)) % m
return memo[n]
n = 8
solve(n, m)
print(sum(list(memo.values())[:n]))輸入
8
輸出
33
更新於：2021-10-12
386 次瀏覽
廣告