如果输入是斐波那契级数中的第n项，则找到n

Question

在斐波那契级数中，让我们假设第n个斐波那契项是T。F(n)=T。但是我想写一个程序，它将以T作为输入，并返回n，这意味着它是级数中的哪个项(假设T总是斐波那契数。我想知道是否有一种有效的方法来找到它。

Answer 1

最简单的方法是开始生成斐波那契数，直到F(i) == T，如果实现正确，复杂度为O(T) (即:不是递归的)。此方法还允许您确保T是有效的斐波那契数。

如果保证T是有效的斐波那契数，则可以使用近似规则：Formula

这看起来很复杂，但事实并非如此。问题的关键是:从某一点开始，F(i+1)/F(i)的比值变成一个常量。由于我们不是生成斐波那契数，而只是寻找“索引”，我们可以省略其中的大部分，只需意识到以下几点：

breakpoint := f(T)
Any f(i) where i > T = f(i-1)*Ratio = f(T) * Ratio^(i-T)

我们可以通过简单地取Log(N，R)来得到相反的结果，R是比率。通过调整早期数字的不准确性，我们甚至不必选择断点(如果您这样做:对于i>17，它是~正确的)。

这个比率大约是1.618034。取6765 (= F(20))的对数(1.618034)，我们得到值18.3277。对于任何更高的Fibonacci数，精度都是相同的，所以只需向下舍入并加上2，就可以得到确切的Fibonacci“秩”(假设F(1) = F(2) = 1)。

Answer 2

第一步是以非递归方式实现fib数，例如

fib1=0;fib2=1;
for(i=startIndex;i<stopIndex;i++)
{
     if(fib1<fib2)
     {
        fib1+=fib2;
        if(fib1=T) return i;
        if(fib1>T) return -1;
     }
     else
     {
        fib2+=fib1;
        if(fib2=T) return i;
        if(fib2>t) return -1;
     }
}

这里，startIndex将设置为3，stopIndex将设置为10000左右。为了减少迭代，您还可以选择2个种子号，它们是序列中进一步向下连续的纤丝号。然后，将startIndex设置为下一个索引，并通过对stopIndex进行适当的调整来执行计算。我建议根据机器性能和最大预期输入将序列分成几个部分，以最大限度地减少运行时间。