测试一个数字是否为斐波那契数列。

Question

我知道如何生成斐波那契数列，但我不知道如何检测给定数字是否属于斐波那契数列。一种方法是生成斐波那契数列直到该数字，并查看该数字是否在数组中，但肯定有另一种更简单更快的方法。

有什么想法吗？

- VaioIsBorn

---

这看起来像是作业，因此我添加了作业标签。 - Gerco Dries

请参考相关问题，网址为 https://dev59.com/z3I_5IYBdhLWcg3wF_F3。 - mtrw

请允许原作者自行添加"作业"标签（如需澄清，请随时提问）。很多事情看起来像是作业，但实际上并不是。 - danben

请不要仅仅因为“看起来很合适”就添加标签。根据我的理解，楼主想在Brainf*ck中完成这个任务，我应该添加这个标签吗？ - IVlad

请注意，您的请求已被重复提交。请在稍后再试。 - sdcvvc

Answer 1

一个非常好的测试方法是：当且仅当5 N^2 + 4或者5N^2 – 4为完全平方数时，N是一个斐波那契数。如果你想了解如何有效地检测一个数是否为完全平方数，请参考Stack Overflow讨论。

- Il-Bhima

---

+1 是因为说“或”比说“其中之一”加上“和”的更清晰。在我读其他答案的前四次，我认为它们在说不同的事情，因为我没有看到“其中之一”的部分。 - Davy8

我对这个解决方案持怀疑态度，因为它涉及到平方斐波那契数。斐波那契数增长非常迅速，大多数都非常大。将它们平方不会变得计算成本很高吗？ - abelenky

嗯...如果命题A和B中只有一个需要成立（但不能同时成立！），那么你不能写成"A或者B"，因为这个复合语句在A为真且B为假、A为假且B为真以及A和B都为真时都是真的。所以你需要明确地写成"只有一个"，或者使用逻辑运算符"xor"而不是"or"。 - Andreas Rejbrand

看起来，“或”确实是正确的运算符。为此，将N = 1。那么N是一个斐波那契数，并且5 * N ^ 2 + 4和5 * N ^ 2 - 4都是完全平方数。“如果我们有一个异或运算符，则'A xor B'将是false，即使1是Fibonacci，我们也会产生矛盾。(在这里，我假设定理使用“或”或“xor”都是正确的。) - Andreas Rejbrand

你可以通过检查N是_奇数_(+4)还是_偶数_(-4)来决定使用哪个测试请参见这里。 - Heiko Schäfer

Answer 2

一个正整数ω是斐波那契数，当且仅当5ω²+4或5ω²-4是一个完全平方数。

更多信息请参见神奇的斐波那契数列。

- JRL

Answer 3

虽然有一些人提出了完美平方解决方案，但它涉及到对斐波那契数进行平方运算，这通常会导致一个巨大的乘积。

甚至有不到80个斐波那契数可以在标准64位整数中存储。

这是我的解决方案，它完全在比要测试的数字小的范围内操作。
（使用基本类型如double和long编写的C#代码。但是该算法对于更大的类型也应该可以正常工作。）

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);
}

四年前我写下了这个答案，现在有一个评论者问到了第二个参数，由out传递。

参数#2是斐波那契数列中的“索引”。如果要测试的值T是斐波那契数，则idx将是该数在斐波那契数列中的基于1的索引（有一个显著的例外）。

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

唯一的例外是IsFib(1, out idx);，它将返回2，即使值1出现在索引1和2处。

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

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

- abelenky

---

简洁实现。我在比赛中使用了这个函数：https://www.hackerrank.com/contests/codesprint5/challenges/is-fibo :) - Mars Robertson

谢谢。看起来像魔法。@Michal 我也在Hackerrank比赛中使用了这个函数。 - kushdilip

非常好 - 谢谢！我用它来获取最接近的斐波那契数 :) 但在实际情况中，我认为没有必要计算这些数字，而是将它们存储在数据库中（就像您在其他帖子中建议的那样）。 - Prokurors

只有一个问题，第二个参数到底是什么，为什么要通过引用传递它？ - Moha the almighty camel

只是出于好奇，你是怎么想到这个的？ - user3450695

这只是直接使用闭式形式或Binet公式，解决N并测试结果的简单应用。全部来自wikipedia页面。 - abelenky

Answer 4

#!/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

- Shizzmo

---

外包。喜欢它！ - Michael Cole

Answer 5

当且仅当下列条件之一成立时，正整数 ω 是斐波那契数：

5ω² + 4 或者 5ω² - 4 中有一个是完全平方数。

摘自《(神奇的)斐波那契数》Alfred Posamentier 和 Ingmar Lehmann著。

bool isFibonacci(int  w)
{
       double X1 = 5 * Math.Pow(w, 2) + 4;
       double X2 = 5 * Math.Pow(w, 2) - 4;

       long X1_sqrt = (long)Math.Sqrt(X1);
       long X2_sqrt = (long)Math.Sqrt(X2);   

       return (X1_sqrt*X1_sqrt == X1) || (X2_sqrt*X2_sqrt == X2) ;
}

我是从这个来源复制的

---

打印出介于1k和10k之间的斐波那契数列代码片段。

for (int i = 1000; i < 10000; i++)
{
         if (isFibonacci(i))
              Console.Write(" "+i);
}

天哪，只有四个！！！

使用其他方法

from math import *

phi = 1.61803399
sqrt5 = sqrt(5)

def F(n):
    return int((phi**n - (1-phi)**n) /sqrt5)

def isFibonacci(z):
    return F(int(floor(log(sqrt5*z,phi)+0.5))) == z

print [i for i in range(1000,10000) if isFibonacci(i)]

- Pratik Deoghare

---

不需要"? true:false"这部分：在此之前的表达式已经是一个布尔值。 - lhf

我用Python写了第二个方法，因为我不知道C#的Math.Log也适用于其他底数。你们想让我也写吗？哈哈 - Pratik Deoghare

Answer 6

如果你的数字的大小是有限制的，那么简单地将所有斐波那契数列中小于上限的数放入哈希表中并测试包含性质即可。由于斐波那契数列呈指数增长，因此斐波那契数目非常少（例如，在500万以下只有38个）。

如果你的数字没有大小限制，那么使用平方测试的建议方法几乎肯定比生成斐波那契序列直到找到或超过该数字要慢。

- jkff

---

我对你最后一句话持怀疑态度。我使用Python编程实现了两种方法，然后使用timeit模块在随机选择的1000位数上计时。基于平方的方法快了7倍。 - John Coleman

Answer 7

针对这个问题，可以看一下比涅公式。

(在维基百科的Fibonacci Number 页面下找 "Closed-Form Expression")

它说斐波那契数列是通过一个简单的闭合公式来创建的：

我相信如果你求解n并测试n是否为整数，你就可以得到答案。

编辑 正如@psmears指出的，同样在维基百科上还有一个关于检测斐波那契数的部分。 维基百科是一个很好的信息来源。

- abelenky

Answer 8

请参阅维基百科关于斐波那契数的文章中“识别斐波那契数”一节。 （链接）

- psmears

---

嘿，你是在林肯的P Smears吗？ - Steve Jessop

Answer 9

由于斐波那契数列增长呈指数级别，所以您提出的方法非常快速。 另一个方法请参考这里。

- lhf

---

我真的很喜欢闭区间解决方案，应该比检查平方要容易得多！ - Matthieu M.

Answer 10

根据我和psmears之前的回答，我写了这段C#代码。

它的步骤比较慢，可以明显地进行简化和优化：

// Input: T: number to test.
// Output: idx: index of the number in the Fibonacci sequence.
//    eg: idx for 8 is 6. (0, 1, 1, 2, 3, 5, 8)
// Return value: True if Fibonacci, False otherwise.
static bool IsFib(long T, out int idx)
{
    double root5 = Math.Sqrt(5);
    double PSI = (1 + root5) / 2;

    // For reference, IsFib(72723460248141) should show it is the 68th Fibonacci number

    double a;

    a = T*root5;
    a = Math.Log(a) / Math.Log(PSI);
    a += 0.5;
    a = Math.Floor(a);
    idx = (Int32)a;

    long u = (long)Math.Floor(Math.Pow(PSI, a)/root5 + 0.5);

    if (u == T)
    {
        return true;
    }
    else
    {
        idx = 0;
        return false;
    }
}

测试表明，这个方法可以适用于前69个斐波那契数列，但在第70个数时失效了。

F(69) = 117,669,030,460,994 - Works
F(70) = 190,392,490,709,135 - Fails

总的来说，除非你使用某种BigInt库，否则最好拥有一个简单的斐波那契数查找表，并检查它，而不是运行算法。

可以在网上轻松找到前300个数字的列表。

但是，只要你有足够的精度并且不会溢出你的数字表示系统，这段代码就概述了一种可行的算法。

- abelenky

---

Phi的问题在于它不能使用浮点数进行精确计算，所以你必须做出近似处理。 - Rubys