有沒有辦法顯示第N個斐波那契數列？例如，我想要第15個斐波那契數列，但這只給出了一個列表。a = int(input('Enter N Number: '))def fib(n): a = b = 1 for i in range(n): yield a a, b = b, a + bprint(fib(a))
4 回答
蕭十郎
TA貢獻1815條經驗 獲得超13個贊
一種幼稚的方法是生成所有n個斐波那契數列并返回最后一個需要時間的元素。您可以使用Binet公式計算第N個斐波那契數列（假設需要時間）。O(n)O(1)math.powO(1)
比奈公式：
Fib(n) =(Phin ? (?Phi)?n)/√5
哪里
Phi=(1+√5)/2= and -Phi=(1-√5)/2(1+√5)/2也被稱為黃金比例。
import math
def fib(n):
phi=1.61803398874989484820
return round(((math.pow(phi,n))-(math.pow(-(1-phi),n)))/math.sqrt(5))
fib(15)
# 610
fib(10)
# 55
數學證明和計算器在這里。
幕布斯6054654
TA貢獻1876條經驗 獲得超7個贊
將 的結果轉換為列表，并在 以下位置為其編制索引：fib()-1
print(list(fib(a))[-1]) >> Enter N Number: 15 >> [610]
元芳怎么了
TA貢獻1798條經驗 獲得超7個贊
您可以使用遞歸和記憶來計算第N個斐波那契數列
為什么？
例如：假設您要計算，因此您需要計算和.但是現在，對于你需要計算和，等等。但是等等，當你完成計算分支時，你已經計算了3和2的所有斐波那契，所以當你從第一個遞歸調用回到另一個分支（）時，你已經計算了它。那么，如果有一種方法可以存儲這些計算，以便我可以更快地訪問它們，該怎么辦？您可以使用裝飾器來創建一個memoize類（某種內存以避免重復計算）：fibonacci(5)fibonacci(4)fibonacci(3)fibonacci(4)fibonacci(3)fibonacci(2)fibonacci(4)fibonacci(3)
這樣，我們將把每個計算都存儲在 a 上，每次調用之前，我們都會檢查它是否存在于字典上，如果返回，或者計算它。這種方式更快，更準確。fibonacci(k)dictTrue
class memoize:
def __init__(self, function):
self.f = function
self.memory = {}
def __call__(self, *args):
if args in self.memory:
return self.memory[args]
else:
value = self.f(*args)
self.memory[args] = value
return value
@memoize
def fib(n):
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)
r = fib(300)
print(r)
輸出：
222232244629420445529739893461909967206666939096499764990979600
它只花了幾秒鐘。0.2716239
SMILET
TA貢獻1796條經驗 獲得超4個贊
發布的答案的另一種方法是使用內置函數中的memoization概念lru_cache這是一個：
裝飾器，用于使用記憶可調用來包裝函數，該可調用將最大大小保存到最大最近的調用。當使用相同的參數定期調用昂貴的或 I/O 綁定的函數時，它可以節省時間。
from functools import lru_cache
@lru_cache()
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
print(fib(300))
# 222232244629420445529739893461909967206666939096499764990979600
獎金：
$> %timeit fib(300)
78.2 ns ± 0.453 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
添加回答
舉報
0/150
提交
取消