c++ - 找到最接近的斐波那契数

Question

我正在尝试解决一个更大的问题，我认为程序的一个重要部分都花在了低效的计算上。

我需要计算给定数 N 的区间 [P, Q]，其中 P 是 <= 到 N 的最大斐波那契数，Q 是 >= 到 N 的最小斐波那契数。

目前，我正在使用 map 来记录斐波那契数的值。查询通常涉及搜索最多 N 的所有斐波那契数，而且时间效率不高，因为它涉及大量比较。

这种类型的查询在我的程序中经常出现，我对改进查找的方法很感兴趣，最好是亚线性复杂度。

Answer 1

斐波那契数由比内公式给出

F(n) = ( phi^n - (1-phi)^n ) / \sqrt{5}

在哪里 phi是黄金比例，

phi = (1 + \sqrt{5}) / 2. 

这可以直接实现(Python 示例):

<<fibonacci_binet.py>>=
phi = (1 + 5**0.5) / 2

def fib(n):
    return int(round((phi**n - (1-phi)**n) / 5**0.5))

由于浮点舍入错误，这只会给出 n < 70 的正确结果.

可以通过忽略 (1-phi)^n 来反转比内公式术语，对于大 n 消失.因此，我们可以定义逆斐波那契函数，当给定 F(n) , 返回 n (忽略 F(1) = F(2) ):

<<fibonacci_binet.py>>=
from math import log

def fibinv(f):
    if f < 2:
        return f
    return int(round(log(f * 5**0.5) / log(phi)))

这里使用舍入对我们有利:它消除了我们对比内公式的修改引入的错误。当给定任何可以作为精确整数存储在计算机内存中的斐波那契数时，该函数实际上将返回正确答案。另一方面，它不会验证给定的数字是否真的是斐波那契数；输入一个大的斐波那契数或任何接近它的数将给出相同的结果。因此，您可以使用这个想法来找到最接近给定数字的斐波那契数。

这个想法是应用逆斐波那契图来找到N和 M ，两边最接近的两个斐波那契数，然后使用直接斐波那契图计算P = F(N)和 Q = F(M) .这涉及更多的计算，但更少的搜索。