我正在嘗試開發一個函數，該函數接受一個值n并輸出nth斐波那契數列中的數字。我有一個循環函數，它的工作原理似乎如下：def fibonacci_v1(n): a = b = 1 for _ in range(1, n): a, b = b, a + b return a我正在嘗試開發一個使用比奈公式的版本，如下所述：Phi = (1 + math.sqrt(5)) / 2def fibonacci_v2(n): c = pow(Phi, n) return math.floor((c - pow(-1, n) / c) / math.sqrt(5))這似乎適用于較低的值，n但當輸入高于 72 的數字時會中斷...我懷疑這與函數的準確性有關，但這里的math.sqrt()文檔沒有說明其準確性級別...這是我的功能的問題還是有其他問題？math.sqrt出于測試目的，我使用了這個 for 循環：for x in range(1, 73): print(fibonacci_v1(x)) print(fibonacci_v2(x))
2 回答
一只萌萌小番薯
TA貢獻1795條經驗 獲得超7個贊
如果您追求速度和準確性，請改用 Python 生成器。下面在 5 毫秒內計算前 10,000 個斐波那契數，然后在約 17 秒內計算（但不存儲） F 0到 F 999,999 ，然后打印 F 1,000,000中的位數。由于它使用整數數學而不是浮點，因此速度更快并且沒有任何錯誤。
import time
def fib():
a,b = 0,1
while True:
yield a
a,b = b,a+b
s = time.time()
it = fib()
f = [next(it) for _ in range(10000)] # list of F[0] - f[9999]
print(time.time() - s)
s = time.time()
it = fib()
for _ in range(1000000): # Skip over F[0]-F[999999]
next(it)
print(time.time() - s)
print(len(str(next(it)))) # display no. of digits in F[1000000].
f = [next(it) for _ in range(10000)]
it = fib()
for _ in range(1000000): # Skip over F[0]-F[999999]
next(it)
print(len(str(next(it)))) # display no. of digits in F[1000000].
輸出：
0.005221128463745117
17.795812129974365
208988
DIEA
TA貢獻1820條經驗 獲得超2個贊
math.sqrt這與浮點數在 python 中的表示方式關系不大。默認實現
如今（2000 年 11 月）幾乎所有機器都使用 IEEE-754 浮點算法，并且幾乎所有平臺都將 Python 浮點映射到 IEEE-754“雙精度”。
您可以使用十進制模塊來解決這種不準確性
與基于硬件的二進制浮點不同，十進制模塊具有用戶可更改的精度
如果您需要更準確的表示，您可以使用getContext()調整精度
from decimal import *
# Your Existing v1 implementation?
def fibonacci_v1(n):
? ? a = b = 1
? ? for _ in range(1, n):
? ? ? ? a, b = b, a + b
? ? return a
Phi = (1 + Decimal(5).sqrt()) / 2
# V2 implementation using the decimal module
def fibonacci_v2(n):
? ? getcontext().prec = 4096 # You need to tweak this number based on your precision requirements?
? ? c = Decimal(Phi) ** n
? ? fib = (c - (Decimal(-1)** n) / c) / Decimal(5).sqrt()
? ? return fib.quantize(Decimal('1.'), rounding=ROUND_UP)
for x in range(73, 80):
? ? print(f"n={x}: v1={fibonacci_v1(x)}, v2={fibonacci_v2(x)}")
輸出：
n=73: v1=806515533049393, v2=806515533049393
n=74: v1=1304969544928657, v2=1304969544928657
n=75: v1=2111485077978050, v2=2111485077978050
n=76: v1=3416454622906707, v2=3416454622906707
n=77: v1=5527939700884757, v2=5527939700884757
n=78: v1=8944394323791464, v2=8944394323791464
n=79: v1=14472334024676221, v2=14472334024676221
添加回答
舉報
0/150
提交
取消