c++ - 我们如何在 C++ 中快速求解斐波那契数列？

Question

是否可以在少于 N 次的时间内确定某个整数是否是斐波那契数，其中 N 是第 N 个斐波那契数？我正在尝试优化解决方案，这将有很大帮助。

我也在尝试排除所有外部库（因此下面答案中的 Math.sqrt() 之类的内容不适用于我的目的）。任何其他建议都会很棒。

谢谢你。

Answer 1

也许你可以使用这个属性：

N 是斐波那契数当且仅当5 N^2 + 4或5N^2 – 4是平方数。

并查看这篇文章以获得平方问题的有效解决方案。

希望这可以帮助

Answer 2

将斐波那契数预先计算到某个界限，然后您可以比使用线性搜索更有效地在列表中搜索您的数字。

斐波那契数字增长得如此之快，以至于我怀疑存储它们会构成问题。我的意思是，如果您愿意保存前 100 个左右，那将涵盖 3.5e+20 之前的所有数字。

假设您存储了第一个M斐波那契数。那么使用二分查找的最坏情况是log(M). 有计算M给定斐波那契数的公式M；您可以使用它来近似M给定M第 斐波那契数，以根据数字（N而不是列表大小M）获得界限。我认为这使它最终成为类似的东西log(log(N))，但你应该检查我。