python - 直接计算第 n 个斐波那契项，而无需使用比内公式找到先前的项。（在 O(1) 时间内）

Question

from math import sqrt

n = int(input())
phi = (1 + sqrt(5))/2

fib_n = round((phi**n))

print(fib_n)

上面提到的代码是不正确的，它给出了一些更接近 fib_n 的值。

from math import sqrt

n = int(input())
phi = (1 + sqrt(5))/2

fib_n = round((phi**n)/sqrt(5))

print(fib_n)

在第 6 行除以 sqrt(5) 后，此代码绝对完美。

我的疑问是：

1. 除以 sqrt(5) 有什么意义，为什么只有 sqrt(5) 而不是任何其他数字？
2. 我可以使用地板或天花板（或任何其他）解决同样的问题，而不用除以根（5）吗？

非常感谢任何帮助/指导/资源！

Answer 1

这是错误的公式。公式应该是：

from math import sqrt

n = int(input())
phi1 = (1 + sqrt(5))/2
phi2 = (1 - sqrt(5))/2

fib_n = (pow(phi1, n) - pow(phi2, n)) / sqrt(5)

print(fib_n) 

sqrt(5) 来自证明：证明 基本上，sqrt(5) 来自解决部分分数

旁注： pow(phi, n) 通常比 phi ** n 更有效，它还可以计算 mods。pow(phi, n, m) 给出 (phi ** n) % m