java 判断一个数是否为斐波那契数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3139645/
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
Determining whether a number is a Fibonacci number
提问by Emily
I need to to write a Java code that checks whether the user inputed number is in the Fibonacci sequence.
我需要编写一个 Java 代码来检查用户输入的数字是否在斐波那契数列中。
I have no issue writing the Fibonacci sequence to output, but (probably because its late at night) I'm struggling to think of the sequence of "whether" it is a Fibonacci number. I keep starting over and over again. Its really doing my head in.
我将斐波那契数列写入输出没有问题，但是（可能是因为深夜）我正在努力思考“是否”是斐波那契数的序列。我一遍又一遍地重新开始。它真的让我着迷。
What I currently have is the nth.
我目前拥有的是第n个。
public static void main(String[] args)
{
ConsoleReader console = new ConsoleReader();
System.out.println("Enter the value for your n: ");
int num = (console.readInt());
System.out.println("\nThe largest nth fibonacci: "+fib(num));
System.out.println();
}
static int fib(int n){
int f = 0;
int g = 1;
int largeNum = -1;
for(int i = 0; i < n; i++)
{
if(i == (n-1))
largeNum = f;
System.out.print(f + " ");
f = f + g;
g = f - g;
}
return largeNum;
}
回答by IVlad
Read the section titled "recognizing fibonacci numbers" on wikipedia.
阅读维基百科上标题为“识别斐波那契数”的部分。
Alternatively, a positive integer z is a Fibonacci number if and only if one of 5z^2 + 4 or 5z^2 ? 4 is a perfect square.[17]
或者，正整数 z 是斐波那契数，当且仅当 5z^2 + 4 或 5z^2 之一？4 是一个完美的正方形。 [17]
Alternatively, you can keep generating fibonacci numbers until one becomes equal to your number: if it does, then your number is a fibonacci number, if not, the numbers will eventually become bigger than your number, and you can stop. This is pretty inefficient however.
或者，您可以继续生成斐波那契数，直到一个数字等于您的数字：如果是，那么您的数字就是斐波那契数，否则，数字最终会变得大于您的数字，您可以停止。然而，这是非常低效的。
回答by Péter T?r?k
If I understand correctly, what you need to do (instead of writing out the first nFibonacci numbers) is to determine whether nis a Fibonacci number.
如果我理解正确，您需要做的（而不是写出前n 个斐波那契数）是确定n是否为斐波那契数。
So you should modify your method to keep generating the Fibonacci sequence until you get a number >= n. If it equals, nis a Fibonacci number, otherwise not.
所以你应该修改你的方法以继续生成斐波那契数列，直到你得到一个 >= n 的数字。如果等于，则n是斐波那契数，否则不是。
Update:bugged by @Moron's repeated claims about the formula based algorithm being superior in performance to the simple one above, I actually did a benchmark comparison - concretely between Jacopo's solution as generator algorithmand StevenH's last version as formula based algorithm. For reference, here is the exact code:
更新：@Moron 反复声称基于公式的算法在性能上优于上面的简单算法，我实际上做了一个基准比较 - 具体是在 Jacopo 的作为生成器算法的解决方案和 StevenH 作为基于公式的算法的最后一个版本之间。作为参考，这里是确切的代码：
public static void main(String[] args) {
measureExecutionTimeForGeneratorAlgorithm(1);
measureExecutionTimeForFormulaAlgorithm(1);
measureExecutionTimeForGeneratorAlgorithm(10);
measureExecutionTimeForFormulaAlgorithm(10);
measureExecutionTimeForGeneratorAlgorithm(100);
measureExecutionTimeForFormulaAlgorithm(100);
measureExecutionTimeForGeneratorAlgorithm(1000);
measureExecutionTimeForFormulaAlgorithm(1000);
measureExecutionTimeForGeneratorAlgorithm(10000);
measureExecutionTimeForFormulaAlgorithm(10000);
measureExecutionTimeForGeneratorAlgorithm(100000);
measureExecutionTimeForFormulaAlgorithm(100000);
measureExecutionTimeForGeneratorAlgorithm(1000000);
measureExecutionTimeForFormulaAlgorithm(1000000);
measureExecutionTimeForGeneratorAlgorithm(10000000);
measureExecutionTimeForFormulaAlgorithm(10000000);
measureExecutionTimeForGeneratorAlgorithm(100000000);
measureExecutionTimeForFormulaAlgorithm(100000000);
measureExecutionTimeForGeneratorAlgorithm(1000000000);
measureExecutionTimeForFormulaAlgorithm(1000000000);
measureExecutionTimeForGeneratorAlgorithm(2000000000);
measureExecutionTimeForFormulaAlgorithm(2000000000);
}
static void measureExecutionTimeForGeneratorAlgorithm(int x) {
final int count = 1000000;
final long start = System.nanoTime();
for (int i = 0; i < count; i++) {
isFibByGeneration(x);
}
final double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9;
System.out.println("Running generator algorithm " + count + " times for " + x + " took " +elapsedTimeInSec + " seconds");
}
static void measureExecutionTimeForFormulaAlgorithm(int x) {
final int count = 1000000;
final long start = System.nanoTime();
for (int i = 0; i < count; i++) {
isFibByFormula(x);
}
final double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9;
System.out.println("Running formula algorithm " + count + " times for " + x + " took " +elapsedTimeInSec + " seconds");
}
static boolean isFibByGeneration(int x) {
int a=0;
int b=1;
int f=1;
while (b < x){
f = a + b;
a = b;
b = f;
}
return x == f;
}
private static boolean isFibByFormula(int num) {
double first = 5 * Math.pow((num), 2) + 4;
double second = 5 * Math.pow((num), 2) - 4;
return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}
private static boolean isWholeNumber(double num) {
return num - Math.round(num) == 0;
}
The results surprised even me:
结果甚至让我感到惊讶：
Running generator algorithm 1000000 times for 1 took 0.007173537000000001 seconds
Running formula algorithm 1000000 times for 1 took 0.223365539 seconds
Running generator algorithm 1000000 times for 10 took 0.017330694 seconds
Running formula algorithm 1000000 times for 10 took 0.279445852 seconds
Running generator algorithm 1000000 times for 100 took 0.030283179 seconds
Running formula algorithm 1000000 times for 100 took 0.27773557800000004 seconds
Running generator algorithm 1000000 times for 1000 took 0.041044322 seconds
Running formula algorithm 1000000 times for 1000 took 0.277931134 seconds
Running generator algorithm 1000000 times for 10000 took 0.051103143000000004 seconds
Running formula algorithm 1000000 times for 10000 took 0.276980175 seconds
Running generator algorithm 1000000 times for 100000 took 0.062019335 seconds
Running formula algorithm 1000000 times for 100000 took 0.276227007 seconds
Running generator algorithm 1000000 times for 1000000 took 0.07422898800000001 seconds
Running formula algorithm 1000000 times for 1000000 took 0.275485013 seconds
Running generator algorithm 1000000 times for 10000000 took 0.085803922 seconds
Running formula algorithm 1000000 times for 10000000 took 0.27701090500000003 seconds
Running generator algorithm 1000000 times for 100000000 took 0.09543419600000001 seconds
Running formula algorithm 1000000 times for 100000000 took 0.274908403 seconds
Running generator algorithm 1000000 times for 1000000000 took 0.10683704200000001 seconds
Running formula algorithm 1000000 times for 1000000000 took 0.27524084800000004 seconds
Running generator algorithm 1000000 times for 2000000000 took 0.13019867100000002 seconds
Running formula algorithm 1000000 times for 2000000000 took 0.274846384 seconds
In short, the generator algorithm way outperforms the formula based solution on all positive int values - even close to the maximum int value it is more than twice as fast! So much for belief based performance optimization ;-)
简而言之，生成器算法的方式在所有正 int 值上都优于基于公式的解决方案 - 即使接近最大 int 值，它的速度也快两倍多！基于信念的性能优化到此为止；-)
For the record, modifying the above code to use longvariables instead of int, the generator algorithm becomes slower (as expected, since it has to add up longvalues now), and cutover point where the formula starts to be faster is around 1000000000000L, i.e. 1012.
作为记录，修改上面的代码以使用long变量而不是int，生成器算法变得更慢（正如预期的那样，因为它现在必须将long值相加），并且公式开始更快的转换点约为 1000000000000L，即 10 12.
Update2:As IVlad and Moron noted, I am not quite an expert in floating point calculations :-) based on their suggestions I improved the formula to this:
更新 2：正如 IVlad 和 Moron 所指出的，我不是浮点计算方面的专家 :-) 根据他们的建议，我将公式改进为：
private static boolean isFibByFormula(long num)
{
double power = (double)num * (double)num;
double first = 5 * power + 4;
double second = 5 * power - 4;
return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}
This brought down the cutover point to approx. 108(for the longversion - the generator with intis still faster for all int values). No doubt that replacing the sqrtcalls with something like suggested by @Moron would push down the cutover point further.
这将转换点降低到大约。10 8（对于long版本 -int对于所有 int 值，生成器仍然更快）。毫无疑问，用sqrt@Moron 建议的方法替换调用会进一步降低转换点。
My (and IVlad's) point was simply that there will always be a cutover point, below which the generator algorithm is faster. So claims about which one performs better have no meaning in general, only in a context.
我（和 IVlad）的观点很简单，总会有一个切入点，低于这个点，生成器算法会更快。因此，关于哪一个表现更好的说法一般没有意义，只有在上下文中才有意义。
回答by David M
Instead of passing the index, n, write a function that takes a limit, and get it to generate the Fibonacci numbers up to and including this limit. Get it to return a Boolean depending on whether it hits or skips over the limit, and you can use this to check whether that value is in the sequence.
不是传递索引，而是n编写一个接受限制的函数，并让它生成高达并包括此限制的斐波那契数列。根据它是否达到或跳过限制，让它返回一个布尔值，您可以使用它来检查该值是否在序列中。
Since it's homework, a nudge like this is probably all we should be giving you...
既然是家庭作业，像这样的轻推可能就是我们应该给你的全部……
回答by David M
Ok. Since people claimed I am just talking thin air ('facts' vs 'guesses') without any data to back it up, I wrote a benchmark of my own.
行。由于人们声称我只是空谈（“事实”与“猜测”）而没有任何数据支持，因此我编写了自己的基准。
Not java, but C# code below.
不是java，而是下面的C#代码。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SO
{
class Program
{
static void Main(string[] args)
{
AssertIsFibSqrt(100000000);
MeasureSequential(1);
MeasureSqrt(1);
MeasureSequential(10);
MeasureSqrt(10);
MeasureSequential(50);
MeasureSqrt(50);
MeasureSequential(100);
MeasureSqrt(100);
MeasureSequential(100000);
MeasureSqrt(100000);
MeasureSequential(100000000);
MeasureSqrt(100000000);
}
static void MeasureSequential(long n)
{
int count = 1000000;
DateTime start = DateTime.Now;
for (int i = 0; i < count; i++)
{
IsFibSequential(n);
}
DateTime end = DateTime.Now;
TimeSpan duration = end - start;
Console.WriteLine("Sequential for input = " + n +
" : " + duration.Ticks);
}
static void MeasureSqrt(long n)
{
int count = 1000000;
DateTime start = DateTime.Now;
for (int i = 0; i < count; i++)
{
IsFibSqrt(n);
}
DateTime end = DateTime.Now;
TimeSpan duration = end - start;
Console.WriteLine("Sqrt for input = " + n +
" : " + duration.Ticks);
}
static void AssertIsFibSqrt(long x)
{
Dictionary<long, bool> fibs = new Dictionary<long, bool>();
long a = 0;
long b = 1;
long f = 1;
while (b < x)
{
f = a + b;
a = b;
b = f;
fibs[a] = true;
fibs[b] = true;
}
for (long i = 1; i <= x; i++)
{
bool isFib = fibs.ContainsKey(i);
if (isFib && IsFibSqrt(i))
{
continue;
}
if (!isFib && !IsFibSqrt(i))
{
continue;
}
Console.WriteLine("Sqrt Fib test failed for: " + i);
}
}
static bool IsFibSequential(long x)
{
long a = 0;
long b = 1;
long f = 1;
while (b < x)
{
f = a + b;
a = b;
b = f;
}
return x == f;
}
static bool IsFibSqrt(long x)
{
long y = 5 * x * x + 4;
double doubleS = Math.Sqrt(y);
long s = (long)doubleS;
long sqr = s*s;
return (sqr == y || sqr == (y-8));
}
}
}
And here is the output
这是输出
Sequential for input = 1 : 110011
Sqrt for input = 1 : 670067
Sequential for input = 10 : 560056
Sqrt for input = 10 : 540054
Sequential for input = 50 : 610061
Sqrt for input = 50 : 540054
Sequential for input = 100 : 730073
Sqrt for input = 100 : 540054
Sequential for input = 100000 : 1490149
Sqrt for input = 100000 : 540054
Sequential for input = 100000000 : 2180218
Sqrt for input = 100000000 : 540054
The sqrt method beats the naive method when n=50 itself, perhaps due to the presence of hardware support on my machine. Even if it was 10^8 (like in Peter's test), there are at most 40 fibonacci numbers under that cutoff, which could easily be put in a lookup table and still beat the naive version for the smaller values.
当 n=50 本身时 sqrt 方法胜过天真的方法，这可能是由于我的机器上存在硬件支持。即使它是 10^8（就像在 Peter 的测试中），在该截止值下最多也有 40 个斐波那契数，可以很容易地将其放入查找表中，并且仍然击败了较小值的朴素版本。
Also, Peter has a bad implementation of the SqrtVersion. He doesn't really need to compute two square roots or compute powers using Math.Pow. He could have atleast tried to make that better before publishing his benchmark results.
此外，Peter 对 SqrtVersion 的实现也很糟糕。他实际上并不需要使用 Math.Pow 计算两个平方根或计算能力。在发布他的基准测试结果之前，他至少可以尝试做得更好。
Anyway, I will let these facts speak for themselves, instead of the so called 'guesses'.
无论如何，我会让这些事实不言自明，而不是所谓的“猜测”。
回答by Nithya
//Program begins
public class isANumberFibonacci {
public static int fibonacci(int seriesLength) {
if (seriesLength == 1 || seriesLength == 2) {
return 1;
} else {
return fibonacci(seriesLength - 1) + fibonacci(seriesLength - 2);
}
}
public static void main(String args[]) {
int number = 4101;
int i = 1;
while (i > 0) {
int fibnumber = fibonacci(i);
if (fibnumber != number) {
if (fibnumber > number) {
System.out.println("Not fib");
break;
} else {
i++;
}
} else {
System.out.println("The number is fibonacci");
break;
}
}
}
}
//Program ends
回答by Soufiane Hassou
A positive integer x is a Fibonacci number if and only if one of 5x^2 + 4 and 5x^2 - 4 is a perfect square
正整数 x 是斐波那契数当且仅当 5x^2 + 4 和 5x^2 - 4 中的一个是完全平方数
回答by Edd
There are a number of methods that can be employed to determine if a given number is in the fibonacci sequence, a selection of which can be seen on wikipedia.
可以采用多种方法来确定给定的数字是否在斐波那契数列中，其中一些可以在wikipedia 上找到。
Given what you've done already, however, I'd probably use a more brute-force approach, such as the following:
但是，鉴于您已经完成的工作，我可能会使用更暴力的方法，例如：
- Generate a fibonacci number
- If it's less than the target number, generate the next fibonacci and repeat
- If it is the target number, then success
- If it's bigger than the target number, then failure.
- 生成斐波那契数
- 如果它小于目标数字，则生成下一个斐波那契数并重复
- 如果是目标数，则成功
- 如果它大于目标数字，则失败。
I'd probably use a recursive method, passing in a current n-value (ie. so it calculates the nth fibonacci number) and the target number.
我可能会使用递归方法，传入当前的 n 值（即它计算第 n 个斐波那契数）和目标数。
回答by Iacopo
If my Java is not too rusty...
如果我的 Java 不是太生疏...
static bool isFib(int x) {
int a=0;
int b=1;
int f=1;
while (b < x){
f = a + b;
a = b;
b = f;
}
return x == f;
}
回答by holsee
Trying to leverage the code you have already written I would propose the following first, as it is the simplest solution (but not the most efficient):
尝试利用您已经编写的代码，我会首先提出以下建议，因为它是最简单的解决方案（但不是最有效的）：
private static void main(string[] args)
{
//This will determnine which numbers between 1 & 100 are in the fibonacci series
//you can swop in code to read from console rather than 'i' being used from the for loop
for (int i = 0; i < 100; i++)
{
bool result = isFib(1);
if (result)
System.out.println(i + " is in the Fib series.");
System.out.println(result);
}
}
private static bool isFib(int num)
{
int counter = 0;
while (true)
{
if (fib(counter) < num)
{
counter++;
continue;
}
if (fib(counter) == num)
{
return true;
}
if (fib(counter) > num)
{
return false;
}
}
}
I would propose a more elegant solution in the generation of fibonacci numbers which leverages recursion like so:
我会在斐波那契数的生成中提出一个更优雅的解决方案，它利用这样的递归：
public static long fib(int n)
{
if (n <= 1)
return n;
else
return fib(n-1) + fib(n-2);
}
For the extra credit read:http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers
对于额外的信用阅读：http : //en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers
You will see the that there are a few more efficient ways to test if a number is in the Fibonacciseries namely: (5z^2 + 4 or 5z^2 ? 4) = a perfect square.
您会看到有一些更有效的方法可以测试一个数字是否在斐波那契数列中，即：(5z^2 + 4 或 5z^2 ? 4) = 一个完美的正方形。
//(5z^2 + 4 or 5z^2 ? 4) = a perfect square
//perfect square = an integer that is the square of an integer
private static bool isFib(int num)
{
double first = 5 * Math.pow((num), 2) + 4;
double second = 5 * Math.pow((num), 2) - 4;
return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}
private static bool isWholeNumber(double num)
{
return num - Math.round(num) == 0;
}
回答by Stas
You can do this in two ways , the recursive and mathematical. the recursive way start generating fibonacci sequence until you hit the number or pass it the mathematical way nicely described here ... http://www.physicsforums.com/showthread.php?t=252798
您可以通过两种方式做到这一点，递归和数学。递归方式开始生成斐波那契数列，直到您命中数字或通过此处很好地描述的数学方式传递它... http://www.physicsforums.com/showthread.php?t=252798
good luck.
祝你好运。
