python - 如何找到给定斐波那契数的索引

Question

我尝试使用下面的公式

在编程问题中找到斐波那契数()的索引，所有较小的测试用例都通过了，但一些 F 接近 10^18 的情况失败了。我做了一些试运行，发现如果 F = 99194853094755497(第 82 个斐波那契数)，根据上面的公式，n 的值为 81。我用 Python 和 C++ 编写了这个代码，可以找到 here和 here分别。我想知道该公式是否适用于 F 的每个值或是否有一些限制？

注意:在做了更多测试后，我发现代码给出了正确的答案，直到第 52 个斐波那契数。

更新:问题有 t 个测试用例，这就是我使用 for 循环的原因。给定的数字 F 不一定是斐波那契数。例如，如果 F = 6，则它位于两个斐波那契数列 5 和 8 之间。现在斐波那契数列中“5”的索引为 4，因此答案为 4。

Answer 1

这个公式很好用:

import math
n = 99194853094755497
print math.log(n * math.sqrt(5) + 0.5) / math.log(1.61803398875) - 1

输出:

82.0

对您的代码的评论:

• 如果浮点结果非常接近 82.0，则使用 int(...) 舍入为整数可能会导致问题。数值问题可能会导致它稍微大一些，即使在数学上它会更小。