我正在嘗試開發(fā)一個函數(shù)，該函數(shù)接受一個值n并輸出nth斐波那契數(shù)列中的數(shù)字。我有一個循環(huán)函數(shù)，它的工作原理似乎如下：def fibonacci_v1(n): a = b = 1 for _ in range(1, n): a, b = b, a + b return a我正在嘗試開發(fā)一個使用比奈公式的版本，如下所述：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但當(dāng)輸入高于 72 的數(shù)字時會中斷...我懷疑這與函數(shù)的準(zhǔn)確性有關(guān)，但這里的math.sqrt()文檔沒有說明其準(zhǔn)確性級別...這是我的功能的問題還是有其他問題？math.sqrt出于測試目的，我使用了這個 for 循環(huán)：for x in range(1, 73): print(fibonacci_v1(x)) print(fibonacci_v2(x))
2 回答
一只萌萌小番薯
TA貢獻(xiàn)1795條經(jīng)驗 獲得超7個贊
如果您追求速度和準(zhǔn)確性，請改用 Python 生成器。下面在 5 毫秒內(nèi)計算前 10,000 個斐波那契數(shù)，然后在約 17 秒內(nèi)計算（但不存儲） F 0到 F 999,999 ，然后打印 F 1,000,000中的位數(shù)。由于它使用整數(shù)數(shù)學(xué)而不是浮點，因此速度更快并且沒有任何錯誤。
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貢獻(xiàn)1820條經(jīng)驗 獲得超2個贊
math.sqrt這與浮點數(shù)在 python 中的表示方式關(guān)系不大。默認(rèn)實現(xiàn)
如今（2000 年 11 月）幾乎所有機器都使用 IEEE-754 浮點算法，并且?guī)缀跛衅脚_都將 Python 浮點映射到 IEEE-754“雙精度”。
您可以使用十進制模塊來解決這種不準(zhǔn)確性
與基于硬件的二進制浮點不同，十進制模塊具有用戶可更改的精度
如果您需要更準(zhǔn)確的表示，您可以使用getContext()調(diào)整精度
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
提交
取消