测试数字是否为斐波那契

Question

我知道如何制作斐波那契数字列表，但我不知道如何测试给定数字是否属于斐波那契列表-一种想到的方法是生成fib列表。直到该数字为止，然后查看它是否属于数组，但是必须有另一个更简单，更快的方法。

任何想法？

Answer 1

[非常好的测试是，当且仅当5 N^2 + 4或5N^2 – 4是平方数时，N是斐波那契数。有关如何有效测试数字是否为平方的想法，请参考SO discussion。

希望这会有所帮助

Answer 2

基于我和psmears的较早答案，我已经编写了此C＃代码。

它逐步执行，可以明显地减少和优化它：

Answer 3

来自维基百科：http://en.wikipedia.org/wiki/Fibonacci_number

正整数z是斐波那契当且仅当5z ^ 2 + 4之一时为数字或5z ^ 2 − 4是一个完美的正方形。

Answer 4

[Re：Ahmad的代码-一种比较简单的方法，没有递归或指针，相当幼稚，但是几乎不需要任何计算能力来处理除泰坦尼克号之外的任何数字（大约2N的加法来验证第N个fib数，这在现代机器上将是最坏时需要毫秒）

//如果发现任何东西，则返回pos；否则，则返回0（C / C ++将任何值！= 0都视为true，因此最终结果相同）]

Answer 5

斐波那契数的一般表达式是F（n）= [[（（1 + sqrt（5））/ 2] sup n + 1-[（1-sqrt（5））/ 2] sup n + 1] / sqrt（5）..... （*）对于大n，第二个指数变为零，然后执行数值运算，我们得到F（n）= [（1.618）sup n + 1] / 2.236

如果K是要测试的数字，log（k * 2.2336）/ log（1.618）应该是整数！

Answer 6

您要处理的数字有多大？

查找表对您有用吗？ （您可以搜索的预先计算的数字列表）

Answer 7

我对此处介绍的方法进行了一些基准测试，并进行了简单加法，预先计算数组并​​将结果存储在哈希中。至少对于Perl而言，平方方法比对数方法快一点，也许快20％。正如abelenky指出的那样，这是在您是否有空间平方位之间的权衡。

当然，最快的方法是对域空间中的所有斐波那契数进行散列。按照abelenky提出的另一点，这些吸盘中只有94个小于2 ^ 64。

Answer 8

这是我的解决方案，我不确定它是否为基准。希望对您有所帮助！

def is_fibonacci?(i)
  a,b=0,1
    until b >= i
        a,b=b,a+b
        return true if b == i
    end
end

Answer 9

def isFib(n: Int): Boolean = {

def checkFib(f1: Int = 1, f2: Int = 1): Boolean = {

if(n == f1 || n == f2) true
else if(n < f2) false
else checkFib(f2, f1+f2)

}

checkFib()

}

Answer 10

以下解决方案适用于

Answer 11

怎么样？

Answer 12

[且仅当5ω² + 4和5ω²-4之一是理想平方时，正整数ω是斐波那契数。

请参阅The Faboulous Fibonacci Numbers以了解更多。

Answer 13

这项工作会吗？

Answer 14

[虽然有几个人指出了完美平方解决方案，但它涉及对斐波那契数进行平方运算，这经常会产生massive乘积。

甚至有少于80个斐波那契数，甚至可以保存在标准的64位整数中。

这是我的解决方案，它的操作完全比要测试的数字小。（用C＃编写，使用double和long等基本类型。但是该算法对于较大的类型应该可以正常工作。）

static bool IsFib(long T, out long idx)
{
    double root5 = Math.Sqrt(5);
    double phi = (1 + root5) / 2;

    idx    = (long)Math.Floor( Math.Log(T*root5) / Math.Log(phi) + 0.5 );
    long u = (long)Math.Floor( Math.Pow(phi, idx)/root5 + 0.5);

    return (u == T);
}

---

在我写下此答案的4年后，一个评论者询问了out传递的第二个参数。

参数2是斐波纳契数列的“索引”。如果要测试的值T是斐波纳契数，则idx将是斐波那契序列中该数字从1开始的索引。 （一个明显的例外）

斐波那契数列为1 1 2 3 5 8 13，依此类推。3是序列中的第4个数字：IsFib(3, out idx);将返回true和值4。8是序列中的第六个数字：IsFib(8, out idx);将返回true和值6。13是第七个数字； IsFib(13, out idx);将返回true和值7。

一个例外是IsFib(1, out idx);，即使值1出现在索引1和2上，也会返回2。

如果IsFib传递了非斐波纳契数，它将返回false，并且idx的值将是小于T的最大斐波那契数的索引。

16不是斐波那契值。IsFib(16, out idx);将返回false和值7。您可以使用Binet's Formula将索引7转换为斐波那契值13，这是小于16的最大数字。]

Answer 15

#!/bin/bash
victim="144"
curl http://aux.planetmath.org/files/objects/7680/fib.txt | sed 's/^[0-9]*//;s/[ \t]//g' | grep "^$victim$" >/dev/null 2>/dev/null
if [[ $? -eq 0 ]] ; then
    echo "$victim is a fibonacci number"
else
    echo "$victim aint"
fi

Answer 16

如果您的数字是有限大小的，那么，简单地将所有低于上限的斐波那契数字放到哈希表中，然后进行测试包含就可以了。斐波那契数很少（例如，低于5百万的斐波那契数只有38），因为它们呈指数增长。

Answer 17

[寻求解决方案，请参阅Binet的公式。（在Wikipedia上的Fibonacci Number下查找“闭式表达式”）

Answer 18

正整数ω是斐波那契数

当且仅当

其中之一

Answer 19

请参见wikipedia article about the Fibonacci numbers上的“识别斐波纳契数”部分。

Answer 20

由于斐波那契数呈指数增长，因此您建议的方法非常快。另一个是this。