如何确定给定数字N是否为斐波那契数，如果该数字不是斐波那契数，我如何*确定小于的最大斐波那契数N？
我通过使用 limit 生成一系列斐波那契数找到了解决方案N。
在 Python 中有没有更好的方法来做到这一点？
伙计们在投票时考虑，我已经接受了这里提供的解决方案。我认为这不值得，因为我已经发布了我需要的内容并从你们那里得到了解决方案。
谢谢你。
问问题
1177 次
2 回答
3
一个整数N是否是斐波那契数的简单测试如下：
N is a Fibonacci number iff either (5 * n^2 + 4) or (5 * n^2 - 4) is a square number.
有关巧妙证明（第 417 页），请参见此处：http ://www.fq.math.ca/Scanned/10-4/advanced10-4.pdf
如果事实证明这N不是斐波那契数，那么最简单的方法就是不断尝试较小的数字，直到找到一个，尽管对于较大的N.
于 2012-08-09T08:02:56.980 回答
1
这是一个通用算法：天真的方法是用递归来解决它 - 但就运行时间复杂度而言，它根本没有用。创建一个新数组，我们称之为 FibArr 。将 1,1, 插入到数组中。那么，数组中第 i 个索引的值为 fibArr[i-1]+fibArr[i-2] (i>=3) 在每次迭代中检查是否有新值插入到 fibArr==N 中。如果为真，则返回。否则，检查插入的值是否大于 N。如果为 true ，假设现在 fibArr 有 k 个值，则返回 (k-1) 值。否则，继续迭代:)
*使用 python 更容易做到 - 但请注意，在 python 中没有数组，而是列表。使用 python 更容易，因为您不必像在 java 中那样设置列表长度。
于 2012-08-09T07:56:39.797 回答