0

在斐波那契数列中，我们假设第 n 个斐波那契项是 T。F(n)=T。但我想编写一个程序，它将 T 作为输入并返回 n，这意味着它在系列中是哪个术语（假设 T 总是一个斐波那契数。）我想找出是否有一种有效的方法来找到它.

4

2 回答 2

2

简单的方法是简单地开始生成斐波那契数，直到 F(i) == T，如果正确实施（阅读：非递归），其复杂度为 O(T)。此方法还允许您确保 T 是有效的斐波那契数。

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

看起来很复杂，其实不然。要点是：从某一点开始，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 是 Ratio。通过调整早期数字的不准确性，我们甚至不必选择断点（如果你这样做：它对于 i > 17 是正确的）。

该比率约为 1.618034。取 6765 (= F(20)) 的 log(1.618034)，我们得到的值为 18.3277。对于任何更高的斐波那契数，精度保持不变，因此只需向下舍入并加 2 即可为我们提供准确的斐波那契“等级”（假设 F(1) = F(2) = 1）。

于 2012-11-19T13:08:49.433 回答
0

第一步是以非递归方式实现 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 个种子编号，它们是序列更靠后的连续 fib 编号。然后将 startIndex 设置为下一个索引，并通过适当调整 stopIndex 进行计算。我建议根据机器性能和最大预期输入将序列分成几个部分，以最小化运行时间。

于 2012-12-03T22:05:17.567 回答