确定N是否为斐波那契，如果没有找到最大的斐波那奇数小于N

-3

如何确定给定的数字N是否为斐波纳契数，如果该数不是斐波那契数，我如何确定最大的斐波那奇数字小于N？确定N是否为斐波那契，如果没有找到最大的斐波那奇数小于N

我通过生成限制N的一系列斐波纳契数找到了解决方案。

有没有更好的方法在Python中做到这一点？

家伙考虑下投票，我接受了这里提供的解决方案。我不认为这是值得的，因为我发布了我需要的东西，并从你们那里得到了解决方案。

谢谢。

来源

2012-08-09 sam

这功课吗？ – 2012-08-09 07:49:53

这不是关于如何在Python（或任何其他编程语言）中执行此操作，而是关于正确的算法的问题。 – 2012-08-09 07:51:22

nop，我想到了这个问题并试图获得解决方案。我用传统的方式做了这件事，即用限制N_生成一系列斐波纳契数。我需要一些优化或更好的方式在PYTHON中做同样的事情。 – sam 2012-08-09 07:52:45

一些整数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-09 08:02:56

下面是一个通用算法：天真的方法是用递归来解决它 - 但就运行时复杂性而言，它根本没有用处。创建一个新的数组，我们称之为FibArr。将1,1插入到数组中。然后，数组中第i个索引的值为fibArr [i-1] + fibArr [i-2]（i> = 3）在每次迭代中检查插入到fibArr == N中的新值。如果为true，则返回。否则，检查插入值是否大于N. 如果为true，假定现在fibArr具有k个值，则返回（k-1）值。否则，继续迭代:)

*使用python更容易做到 - 但请注意，在python中没有数组，但列表。 python更容易，因为你不必设置列表长度，就像在java中一样。

来源

2012-08-09 07:56:39 Itamar

确定N是否为斐波那契，如果没有找到最大的斐波那奇数小于N

回答

相关问题