对斐波那契分析求解方法的质疑

Question

我正在练习使用比奈公式计算斐波那契数，通过遵循比奈公式，我想出了以下代码并通过了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？根据比奈公式，我认为我的代码是正确的，但我想知道为什么leetcode使用另一种方式仍然得到正确的结果。

这是比奈公式的 link： https://artofproblemsolving.com/wiki/index.php/Binet%27s_Formula

Answer 1

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

给定的解决方案是纠正该错误的合理尝试：不是减去精确的校正量，因为该量通常显示为小于 1，给定的解决方案仅加 1 并截断 floor 整数，产生比 "exact" 实施更远的正确结果。

尝试生成一些结果：

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)

对斐波那契分析求解方法的质疑

Doubts About Fibonacci Analytical Solving Approach

python

fibonacci