对Fibonacci分析求解方法的质疑

Question

我正在练习使用Binet公式计算Fibonacci数，通过遵循Binet公式，我得出了以下代码，并通过了leetcode中的测试用例：

class Solution(object):
def fib(self, N):
goldenratio = (1 + 5 ** 0.5) / 2
ratio2 = (1 - 5 ** 0.5) / 2
return int((goldenratio**N-ratio2**N)/(5**0.5))

但我不理解leetcode给出的解决方案(当然给出了正确的结果(：

class Solution:
def fib(self, N):
golden_ratio = (1 + 5 ** 0.5) / 2
return int((golden_ratio ** N + 1) / 5 ** 0.5)

我对leetcode解决方案的问题是：为什么它们在"golden_ratio**N"后加1？根据Binet公式，我认为我的代码是正确的，但我想知道为什么leetcode使用另一种方式，但仍然得到正确的结果。

以下是Binet公式的链接：https://artofproblemsolving.com/wiki/index.php/Binet%27s_Formula

Answer 1

您的代码是精确公式φ^n - ψ^n的数字呈现；这对于机械表示的精度限制是正确的，但由于结果超出该点而失败。

给定的解决方案是纠正该错误的合理尝试：由于该量被简单地显示为小于1，因此该解决方案没有减去精确的校正量，而是只加1并截断floor整数，从而产生比"精确"实现更远的正确结果。

尝试生成一些结果：

def fib_exact(n):
goldenratio = (1 + 5 ** 0.5) / 2 
ratio2 = (1 - 5 ** 0.5) / 2 
return int((goldenratio**n - ratio2**n)/(5**0.5))
def fib_trunc(n):
golden_ratio = (1 + 5 ** 0.5) / 2
return int((golden_ratio ** n + 1) / 5 ** 0.5)
for n in range(100):
a = fib_trunc(n)
b = fib_exact(n)
print(n, a-b, a, b)