C++ 测试一个数字是否为斐波那契数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2432669/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Test if a number is fibonacci
提问by VaioIsBorn
I know how to make the list of the Fibonacci numbers, but i don't know how can i test if a given number belongs to the fibonacci list - one way that comes in mind is generate the list of fib. numbers up to that number and see if it belongs to the array, but there's got to be another, simpler and faster method.
我知道如何制作斐波那契数列，但我不知道如何测试给定数是否属于斐波那契数列——我想到的一种方法是生成 fib 列表。数字到那个数字，看看它是否属于数组，但必须有另一种更简单、更快的方法。
Any ideas ?
有任何想法吗 ？
回答by Il-Bhima
A very nice test is that N is a Fibonacci number if and only if 5 N^2 + 4or 5N^2 – 4is a square number. For ideas on how to efficiently test that a number is square refer to the SO discussion.
一个非常好的测试是 N 是斐波那契数当且仅当5 N^2 + 4或5N^2 – 4是平方数。有关如何有效测试数字是否为平方的想法，请参阅SO 讨论。
Hope this helps
希望这可以帮助
回答by JRL
A positive integer ω is a Fibonacci number if and only if one of 5ω2+ 4 and 5ω2- 4 is a perfect square.
正整数 ω 是斐波那契数，当且仅当 5ω 2+ 4 和 5ω 2- 4 之一是完全平方数。
See The Faboulous Fibonacci Numbersfor more.
有关更多信息，请参阅神奇的斐波那契数列。
回答by abelenky
While several people point out the perfect-square solution, it involves squaring a Fibonacci number, frequently resulting in a massiveproduct.
虽然有几个人指出完美平方解决方案，但它涉及对斐波那契数进行平方，通常会产生大量产品。
There are less than 80 Fibonacci numbers that can even be held in a standard 64-bit integer.
甚至可以用标准 64 位整数表示的斐波那契数也不到 80 个。
Here is my solution, which operates entirely smallerthan the number to be tested.
(written in C#, using basic types like doubleand long. But the algorithm should work fine for bigger types.)
这是我的解决方案，它的运行完全小于要测试的数量。
（用 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 年多之后，一位评论者询问了第二个参数，通过
outout.Parameter #2 is the "Index" into the Fibonacci sequence.
If the value to be tested, Tis a Fibonacci number, then idxwill be the 1-based index of that number in the Fibonacci sequence. (with one notable exception)
参数#2 是斐波那契数列的“索引”。
如果要测试的值T是斐波那契数，idx则将是该数在斐波那契数列中的从 1 开始的索引。（有一个明显的例外）
The Fibonacci sequence is 1 1 2 3 5 8 13, etc.
3 is the 4th number in the sequence: IsFib(3, out idx);will return trueand value 4.
8 is the 6th number in the sequence: IsFib(8, out idx);will return trueand value 6.
13 is the 7th number; IsFib(13, out idx);will return trueand value 7.
斐波那契数列是1 1 2 3 5 8 13等
。3 是序列中的第四个数字：IsFib(3, out idx);将返回true和值4。
8 是序列中的第 6 个数字：IsFib(8, out idx);将返回true和值6。
13 是第 7 个数字；IsFib(13, out idx);将返回true和值7。
The one exception is IsFib(1, out idx);, which will return 2, even though the value 1 appears at both index 1 and 2.
一个例外是IsFib(1, out idx);，它会返回2，即使值 1 出现在索引 1 和 2 处。
If IsFibis passed a non-Fibonacci number, it will return false, and the value of idxwill be the index of the biggest Fibonacci number less than T.
如果IsFib传递了一个非斐波那契数，它将返回false，并且 的值idx将是小于 的最大斐波那契数的索引T。
16 is not a Fibonacci value.IsFib(16, out idx);will return falseand value 7.
You can use Binet's Formulato convert index 7 into Fibonacci value 13, which is the largest number less than 16.
16 不是斐波那契值。IsFib(16, out idx);将返回false和值7。
您可以使用比奈公式将索引 7 转换为斐波那契值 13，即小于 16 的最大数。
回答by Shizzmo
#!/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
回答by jkff
If your numbers are of bounded size, than simply putting all fibonacci numbers below the upper bound into a hashtable and testing containment will do the trick. There are very few fibonacci numbers (for example, only 38 below 5mln), since they grow exponentially.
如果您的数字是有界大小，那么简单地将所有低于上限的斐波那契数字放入哈希表并测试遏制就可以解决问题。斐波那契数很少（例如，只有 500 万以下的 38 个），因为它们呈指数增长。
If your numbers are notof bounded size, then the suggested trick with square testing will almost surely be slower than generating the fibonacci sequence until the number is found or exceeded.
如果您的数字不是有界大小，那么在找到或超过该数字之前，建议的平方测试技巧几乎肯定会比生成斐波那契数列慢。
回答by abelenky
Towards a solution, take a look at Binet's Formula.
(Look for "Closed-Form Expression" under Fibonacci Numberon Wikipedia)
对于解决方案，请查看比奈公式。
（在维基百科的斐波那契数下寻找“闭式表达式” ）
It says that the sequence of Fibonacci Number's is created by a simple closed formula:
它说斐波那契数列是由一个简单的封闭公式创建的：
I believe if you solve for n, and test if nis an integer, you'll have your answer.
我相信如果你解决n，并测试它是否n是一个整数，你就会有答案。
EditAs @psmears points out, the same Wikipedia article also has a section on detecting Fibonacci numbers. Wikipedia is an excellent source.
编辑正如@psmears 指出的那样，同一篇维基百科文章也有一个关于检测斐波那契数的部分。维基百科是一个很好的来源。
回答by Pratik Deoghare
Positive integer ω is a Fibonacci number
正整数 ω 是斐波那契数
If and only if one of5ω2+ 4 and 5ω2- 4 is a perfect square
当且仅当一个5ω 2+ 4和5ω 2- 4是完全平方
from The (Fabulous) FIBONACCI Numbers by Alfred Posamentier and Ingmar Lehmann
来自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) ;
}
Snippet that prints Fibonacci numbers between 1kand 10k.
在1k和之间打印斐波那契数列的代码段10k。
for (int i = 1000; i < 10000; i++)
{
if (isFibonacci(i))
Console.Write(" "+i);
}
OMG There are only FOUR!!!
OMG 只有四个！！！
With other method
用其他方法
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)]
回答by psmears
See the section "Recognizing Fibonacci numbers" on the wikipedia article about the Fibonacci numbers.
请参阅维基百科关于 Fibonacci 数的文章中的“识别 Fibonacci 数”部分。
回答by lhf
回答by abelenky
Based on earlier answers by me and psmears, I've written this C# code.
根据我和 psmears 的早期答案，我编写了此 C# 代码。
It goes through the steps slowly, and it can clearly be reduced and optimized:
它慢慢地通过这些步骤，它可以明显地减少和优化：
// 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;
}
}
Testing reveals this works for the first 69 Fibonacci numbers, but breaks down for the 70th.
测试表明这适用于前 69 个斐波那契数列，但在第 70 个时失效。
F(69) = 117,669,030,460,994 - Works
F(70) = 190,392,490,709,135 - Fails
In all, unless you're using a BigInt library of some kind, it is probably better to have a simple lookup table of the Fibonacci Numbers and check that, rather than run an algorithm.
总之，除非您使用某种 BigInt 库，否则最好有一个简单的斐波那契数查找表并进行检查，而不是运行算法。
A list of the first 300 Numbers is readily available online.
前 300 个号码的列表可在线获取。
But this code does outline a workable algorithm, provided you have enough precision, and don't overflow your number representation system.
但是这段代码确实概述了一个可行的算法，前提是您有足够的精度，并且不会溢出您的数字表示系统。
