使用 binet 公式直接计算第 n 个 Fibonacci 项，而无需查找先前的项。 （在 O(1) 时间内）
Computing directly nth Fibonacci term without finding previous terms using binet's formula. (in O(1) time)
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) 后绝对完美。
我的疑惑是：
- What is the significance of dividing by sqrt(5) and why only sqrt(5) and not any other number?
- Can I solve the same thing using the floor or ceiling (or any other) and without dividing by root(5)?
非常感谢help/guidance/resources！
这是错误的公式。
公式应为：
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) 出来的证明：Proof
基本上，sqrt(5) 来自求解部分分数
旁注：pow(phi, n) 通常比 phi ** n 更有效，它还可以计算模数。 pow(phi, n, m) 给出 (phi ** n) % m
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) 后绝对完美。
我的疑惑是：
- What is the significance of dividing by sqrt(5) and why only sqrt(5) and not any other number?
- Can I solve the same thing using the floor or ceiling (or any other) and without dividing by root(5)?
非常感谢help/guidance/resources！
这是错误的公式。 公式应为：
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) 出来的证明：Proof 基本上，sqrt(5) 来自求解部分分数
旁注：pow(phi, n) 通常比 phi ** n 更有效，它还可以计算模数。 pow(phi, n, m) 给出 (phi ** n) % m