blocks|key|1089950|text|一个非常好的测试是，当且仅当5+N%5E2+%2B+4或5N%5E2+–+4是平方数时，N是斐波那契数。有关如何有效地测试数字是否为平方的想法，请参阅SO+discussion。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1089951|希望这能有所帮助|1089952|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer^0|E|9|O|8|1X|D|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@$9|Q|A|R|B|C]|$9|S|A|T|B|C]]|D|@$9|U|A|V|1|W]]|E|$]]|$1|F|3|G|5|6|7|X|8|@]|D|@]|E|$]]|$1|H|3|-4|5|6|7|Y|8|@]|D|@]|E|$]]]|I|$J|$5|K|L|M|E|$N|O]]]]

A very nice test is that N is a Fibonacci number if and only if <code>5 N^2 + 4</code> or <code>5N^2 – 4</code> is a square number. For ideas on how to efficiently test that a number is square refer to the <a href="https://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer">SO discussion</a>.

Hope this helps

blocks|key|1090133|text|#!/bin/bash
victim="144"
curl+http://aux.planetmath.org/files/objects/7680/fib.txt+%7C+sed+'s/%5E[0-9]*//;s/[+\t]//g'+%7C+grep+"%5E$victim$"+>/dev/null+2>/dev/null
if+[[+$?+-eq+0+]]+;+then
++++echo+"$victim+is+a+fibonacci+number"
else
++++echo+"$victim+aint"
fi|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1090134|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

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

blocks|key|1090118|text|请参阅wikipedia+article+about+the+Fibonacci+numbers上的“识别斐波那契数”一节。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1090119|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers^0|3|19|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

See the section "Recognizing Fibonacci numbers" on the <a href="http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers" rel="noreferrer">wikipedia article about the Fibonacci numbers</a>.

blocks|key|1305221|text|由于Fibonacci数呈指数增长，因此您建议的方法非常快。另一个是this。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1305222|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers^0|Y|4|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

Since Fibonacci numbers grow exponentially, the method you suggest is pretty fast.
Another is <a href="http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers" rel="noreferrer">this</a>.

blocks|key|1305435|text|基于我和psmears之前的回答，我写了这段C#代码。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1305436|它通过缓慢的步骤，它可以清楚地减少和优化：|1305437|//+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+%2B+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+%2B=+0.5;
++++a+=+Math.Floor(a);
++++idx+=+(Int32)a;

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

++++if+(u+==+T)
++++{
++++++++return+true;
++++}
++++else
++++{
++++++++idx+=+0;
++++++++return+false;
++++}
}|code-block|syntax|javascript|1305438|测试显示，这在前69个斐波纳契数上有效，但在第70个斐波纳契数上表现不佳。|1305439|F(69)+=+117,669,030,460,994+-+Works
F(70)+=+190,392,490,709,135+-+Fails|1305440|总而言之，除非您正在使用某种类型的BigInt库，否则最好有一个简单的斐波那契数查找表并进行检查，而不是运行算法。|1305441|前300个号码的列表很容易在网上找到。|1305442|但这段代码确实概述了一个可行的算法，前提是您有足够的精度，并且不会使您的数字表示系统溢出。|1305443|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|V|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|W|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|X|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|Y|8|@]|9|@]|A|$G|H]]|$1|M|3|N|5|6|7|Z|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|10|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|11|8|@]|9|@]|A|$]]|$1|S|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|T|$]]

Based on earlier answers by me and psmears, I've written this C# code.

It goes through the steps slowly, and it can clearly be reduced and optimized:

<pre><code>// 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;
 }
}
</code></pre>

Testing reveals this works for the first 69 Fibonacci numbers, but breaks down for the 70th.

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

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.

A list of the first 300 Numbers is readily available online.

But this code does outline a workable algorithm, provided you have enough precision, and don't overflow your number representation system.

blocks|key|1305640|text|Re:+Ahmad的代码-一种更简单的方法，没有递归或指针，相当天真，但除了真正的泰坦尼克数之外，几乎不需要任何计算能力(大约2N次加法来验证第N个fib数，在现代机器上最坏情况下需要几毫秒)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1305641|//如果找到任何东西，则返回pos，如果没有，则返回0+(C/C%2B%2B将任何值!=0视为true，因此最终结果相同)|1305642|int+isFib+(long+n)
{
++++int+pos+=+2;
++++long+last+=+1;
++++long+current+=+1;
++++long+temp;

++++while+(current+<+n)
++++{
++++++++temp+=+last;
++++++++last+=+current;
++++++++current+=+current+%2B+temp;
++++++++pos%2B%2B;
++++}

++++if+(current+==+n)
++++++++return+pos;
++++else
++++++++return+0;

}|code-block|syntax|javascript|1305643|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Re: Ahmad's code - a simpler approach with no recursion or pointers, fairly naive, but requires next to no computational power for anything short of really titanic numbers (roughly 2N additions to verify the Nth fib number, which on a modern machine will take milliseconds at worst)

// returns pos if it finds anything, 0 if it doesn't (C/C++ treats any value !=0 as true, so same end result)

<pre><code>int isFib (long n)
{
 int pos = 2;
 long last = 1;
 long current = 1;
 long temp;

 while (current &lt; n)
 {
 temp = last;
 last = current;
 current = current + temp;
 pos++;
 }

 if (current == n)
 return pos;
 else
 return 0;

}
</code></pre>

blocks|key|1305563|text|斐波那契数的一般表达式是F(n)+=[+(1%2Bsqrt(5))/2+sup+n%2B1+-+(1-+sqrt(5)+)/2+sup+n%2B1+]/+sqrt(5)+.....(*)对于大的n，第二个指数变为零，并进行数值运算，我们得到F(n)+=+(1.618)+sup+n%2B1+/+2.236|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1305564|如果K是要测试的数字log(k*2.2336)，/log(1.618)应该是一个整数！|1305565|例如，K等于13，我的计算器给出的答案是7.00246，K等于14，答案是7.1564。|1305566|您可以通过采用与答案最接近的整数并替换为(*)来确认结果为K，从而提高结果的置信度|1305567|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

The general expression for a Fibonacci number is
F(n) = [ [(1+sqrt(5))/2] sup n+1 - [(1-sqrt(5))/2] sup n+1 ]/ sqrt(5) ..... (*)
The second exponential goes to zero for large n and carrying out the
numerical operations we get F(n) = [ (1.618) sup n+1 ] / 2.236

If K is the number to be tested log(k*2.2336)/log(1.618) should be an integer!

Example for K equal to 13 my calculator gives the answer 7.00246
For K equal 14 the answer is 7.1564.

You can increase the confidence in the result by taking the closest integer to the
answer and substitute in (*) to confirm that the result is K

blocks|key|1305316|text|你要处理的数字有多大？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1305317|查找表可以为您工作吗？(可以搜索的预先计算的数字列表)|1305318|还有一个closed-form+expression，我猜你可以倒过来分析得到答案(虽然我不是数学家，所以我不能保证这个建议是有意义的)|offset|length|1305319|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression^0|0|0|4|M|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@$F|S|G|T|1|U]]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

How big are the numbers you're dealing with?

Could a lookup table work for you? (a precomputed list of numbers you can search in)

There's also a <a href="http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression" rel="nofollow noreferrer">closed-form expression</a> that I guess you could invert to get at the answer analytically (though I'm no mathematician, so I can't promise this suggestion makes sense)

blocks|key|1090260|text|我在这里介绍的方法上运行了一些基准测试，以及简单的加法、预计算一个数组和在哈希表中记录结果。至少对于Perl来说，平方方法比对数方法要快一点，可能快20%25。正如abelenky所指出的，这是一个权衡，你是否有空间来平方位数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1090261|当然，最快的方法是对域空间中的所有斐波那契数进行散列。按照阿贝伦基提出的另一个观点，这些吸盘中只有94个小于2%5E64。|1090262|您只需预先计算它们，并将它们放入Perl散列、Python字典或其他任何地方。|1090263|Fibonacci数的性质非常有趣，但使用它们来确定计算机程序中的某个整数是否为1，就像编写了一个子例程，在每次程序启动时计算π。|1090264|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

I ran some benchmarks on the methods presented here along with simple addition, pre-computing an array, and memoizing the results in a hash. For Perl, at least, the squaring method is a little bit faster than the logarithmic method, perhaps 20% faster. As abelenky points out, it's a tradeoff between whether you've got the room for squaring bit numbers.

Certainly, the very fastest way is to hash all the Fibonacci numbers in your domain space. Along the lines of another point that abelenky makes, there are only 94 of these suckers that are less than 2^64.

You should just pre-compute them, and put them in a Perl hash, Python dictionary, or whatever.

The properties of Fibonacci numbers are very interesting, but using them to determine whether some integer in a computer program is one is kind of like writing a subroutine to compute pi every time the program starts.

blocks|key|1305710|text|一个Scala版本-|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1305711|def+isFib(n:+Int):+Boolean+=+{

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

if(n+==+f1+%7C%7C+n+==+f2)+true
else+if(n+<+f2)+false
else+checkFib(f2,+f1%2Bf2)

}

checkFib()

}|code-block|syntax|javascript|1305712|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

A Scala version-

<pre><code>def isFib(n: Int): Boolean = {

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

if(n == f1 || n == f2) true
else if(n &lt; f2) false
else checkFib(f2, f1+f2)

}

checkFib()

}
</code></pre>

blocks|key|1090347|text|int+isfib(int+n+/*+number+*/,+int+&pos+/*+position+*/)
{
+++if+(n+==+1)
+++{
++++++pos=2;++//+1+1
++++++return+1;
+++}
+++else+if+(n+==+2)
+++{
++++++pos=3;++//+1+1+2
++++++return+1;
+++}
+++else
+++{
++++++int+m+=+n+/2;
++++++int+p,+q,+x,+y;
++++++int+t1=0,+t2+=0;
++++++for+(int+i+=+m;+i+<+n;+i%2B%2B)
++++++{
++++++++p+=+i;
++++++++q+=+n+-p;++++//+p+%2B+q+=+n
++++++++t1+=+isfib(p,+x);
++++++++if+(t1)+t2+=+isfib(q,+y);
++++++++if+(t1+&&+t2+&&+x+==+y+%2B1)
++++++++{
+++++++++++pos+=+x%2B1;
+++++++++++return+1;+//true
++++++++}
++++++}
++++++pos+=+-1;
++++++return+0;+//false
+++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1090348|这个怎么样？|unstyled|1090349|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|J|8|@]|9|@]|A|$]]|$1|G|3|-4|5|F|7|K|8|@]|9|@]|A|$]]]|H|$]]

<pre><code>int isfib(int n /* number */, int &amp;pos /* position */)
{
 if (n == 1)
 {
 pos=2; // 1 1
 return 1;
 }
 else if (n == 2)
 {
 pos=3; // 1 1 2
 return 1;
 }
 else
 {
 int m = n /2;
 int p, q, x, y;
 int t1=0, t2 =0;
 for (int i = m; i &lt; n; i++)
 {
 p = i;
 q = n -p; // p + q = n
 t1 = isfib(p, x);
 if (t1) t2 = isfib(q, y);
 if (t1 &amp;&amp; t2 &amp;&amp; x == y +1)
 {
 pos = x+1;
 return 1; //true
 }
 }
 pos = -1;
 return 0; //false
 }
}
</code></pre>

How about this?

blocks|key|1090421|text|#include+<stdio.h>
#include+<math.h>

int+main()
{
int+number_entered,+x,+y;

printf("Please+enter+a+number.\n");
scanf("%25d",+&number_entered);
x+=+y+=+5+*+number_entered%5E2+%2B+4;++++++++/*Test+if+5N%5E2+%2B+4+is+a+square+number.*/
x+=+sqrt(x);
x+=+x%5E2;
if+(x+==+y)
{
++++++++printf("That+number+is+in+the+Fibonacci+sequence.\n");
++++}
x+=+y+=+5+*+number_entered%5E2+-+4;++++++++/*Test+if+5N%5E2+-+4+is+a+square+number.*/
x+=+sqrt(x);
x+=+x%5E2;
if+(x+==+y)
{
++++printf("That+number+is+in+the+Fibonacci+sequence.\n");
}
else
{
++++printf("That+number+isn't+in+the+Fibonacci+sequence.\n");
}
return+0;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1090422|这样行得通吗？|unstyled|1090423|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|J|8|@]|9|@]|A|$]]|$1|G|3|-4|5|F|7|K|8|@]|9|@]|A|$]]]|H|$]]

<pre><code>#include &lt;stdio.h&gt;
#include &lt;math.h&gt;

int main()
{
int number_entered, x, y;

printf("Please enter a number.\n");
scanf("%d", &amp;number_entered);
x = y = 5 * number_entered^2 + 4; /*Test if 5N^2 + 4 is a square number.*/
x = sqrt(x);
x = x^2;
if (x == y)
{
 printf("That number is in the Fibonacci sequence.\n");
 }
x = y = 5 * number_entered^2 - 4; /*Test if 5N^2 - 4 is a square number.*/
x = sqrt(x);
x = x^2;
if (x == y)
{
 printf("That number is in the Fibonacci sequence.\n");
}
else
{
 printf("That number isn't in the Fibonacci sequence.\n");
}
return 0;
}
</code></pre>

Will this work?

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.

Any ideas ?

Test if a number is fibonacci

Python

Perl

我知道如何制作Fibonacci数的列表，但我不知道如何测试给定的数字是否属于fibonacci列表-我想到的一种方法是生成fib列表。数字直到这个数字，看看它是否属于数组，但肯定有另一种更简单，更快的方法。有什么想法吗？

问测试数字是否为斐波那契数
EN

回答 12

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问测试数字是否为斐波那契数EN

回答 12

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问测试数字是否为斐波那契数
EN