我正在使用比奈公式來計算大n的斐波那契數列比奈公式：我的代碼：#!/usr/bin/env python3def calc_fib(n): if (n <= 1): return n root_5 = 5 ** 0.5 phi_n = ((root_5 + 1) / 2) ** n alpha_n = ((root_5 - 1) / 2) ** n fn = round((phi_n - alpha_n) / root_5) return fnn = int(input())print(calc_fib(n))$ ./fibonacci.py 200 280571172992512015699912586503521287798784.（錯誤）正確的結果是：280571172992510140037611932413038677189525問題是，對于非常大的n，比如說n = 200，結果不準確，我認為由于浮點計算，我該如何更改我的代碼，以便我可以獲得更準確的結果？
2 回答
素胚勾勒不出你
TA貢獻1827條經驗 獲得超9個贊
Binet公式的問題在于，您需要提高準確性才能進行計算，而浮點數并不能為您提供這一點。
有幾種方法可以有效地計算斐波那契數列。這是我最喜歡的，它不是（明確地）迭代的，并且具有大致正確的運行時復雜性：
def fib(n):
X = 1<<(n+2)
return pow(X, n+1, X*X-X-1) % X
這使用具有與n線性增長的位數的算術，我認為這是可以的，因為結果的位數線性增長。
替代的 log（n） 方法是使用加倍公式，使用 Binet 公式的整數版本（通常在代數環中）或矩陣冪。我有一篇博客文章更詳細地描述了它們：https://blog.paulhankin.net/fibonacci2/
添加回答
舉報
0/150
提交
取消