判断一个数是否是斐波那契数

Question

我需要编写一段Java代码来检查用户输入的数字是否在斐波那契数列中。

我在将斐波那契数列写入输出时没有任何问题，但是（可能是因为已经是深夜了）我正在努力思考“是否”是斐波那契数列。我不断地一遍又一遍地开始。这真的让我很头疼。

我目前拥有的是第 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;
}

Answer 1

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

Answer 2

如果我的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;
}

Answer 3

尝试利用您已经编写的代码，我会首先提出以下建议，因为它是最简单的解决方案（但不是最有效的）：

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

我会在生成斐波那契数时提出一个更优雅的解决方案，它利用递归，如下所示：

public static long fib(int n) 
{
   if (n <= 1) 
      return n;
   else 
      return fib(n-1) + fib(n-2);
}

<强>有关额外学分，请阅读： http://en.wikipedia.org/ wiki/Fibonacci_number#Recognizing_Fibonacci_numbers

您将看到有一些更有效的方法来测试数字是否在斐波那契系列中，即：(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;    
}

Answer 4

我不知道是否有一个实际的公式可以应用于用户输入，但是，您可以生成斐波那契序列并根据用户输入进行检查，直到它小于最后生成的数字。

int userInput = n;
int a = 1, b = 1;

while (a < n) {
  if (a == n)
    return true;

  int next = a + b;
  b = a;
  a = next;
}

return false;

Answer 5

您可以通过两种方式来完成此操作：递归方式和数学方式。
递归方式
开始生成斐波那契数列，直到您达到数字或通过它
这里很好地描述了数学方法......
http://www.physicalsforums.com/showthread.php?t=252798

祝你好运。

Answer 6

考虑斐波那契数列 1,1,2,3,5,8,13,21 等。需要构建 3 个堆栈，每个堆栈容量为 10，包含上述序列中的数字，如下所示：

堆栈 1：前 10 个数字从序列中。
堆栈 2：序列中的前 10 个素数。
堆栈 3：序列中的前 10 个非素数。

(i) 给出流程图的算法
(ii) 编写一个程序（用 BASIC、C++ 或 Java）来实现这一点。

输出：当堆栈操作发生时，您应该以任何方便的形式显示 3 个堆栈以及其中保存的值。

Answer 7

根据公式判断一个数是否为斐波那契数：

public static boolean isNumberFromFibonacciSequence(int num){

    if (num == 0 || num == 1){
        return true;
    }

    else {
        //5n^2 - 4 OR 5n^2 + 4 should be perfect squares
        return isPerfectSquare( 5*num*num - 4) || isPerfectSquare(5*num*num - 4);
    }
}

private static boolean isPerfectSquare(int num){
        double sqrt = Math.sqrt(num);
        return sqrt * sqrt == num;
}

Answer 8

以为这很简单，直到我不得不绞尽脑汁思考几分钟。它与生成斐波那契数列完全不同。如果是斐波那契，该函数返回 1，否则返回 0

public static int isFibonacci (int n){
  int isFib = 0;
  int a = 0, b = 0, c = a + b; // set up the initial values
  do 
   {
    a = b;
    b = c;
    c = a + b;
    if (c == n)
    isFib = 1;
    } while (c<=n && isFin == 0)
  return isFib;
}

public static void main(String [] args){
  System.out.println(isFibonacci(89));
}

Answer 9

阅读 wikipedia 上标题为“识别斐波那契数”的部分。

或者，当且仅当 5z^2 + 4 或 5z^2 − 4 之一是完全平方数时，正整数 z 才是斐波那契数。[17]

或者，您可以继续生成斐波那契数，直到 1 等于您的数字：如果是，那么您的数字是斐波那契数，如果不是，数字最终将变得比您的数字大，您可以停止。然而，这是相当低效的。

Answer 10

如果我理解正确的话，您需要做的（而不是写出前 n 个斐波那契数）是确定 n 是否是斐波那契数。

因此，您应该修改您的方法以继续生成斐波那契数列，直到得到一个数字 >= n。如果相等，n 是斐波那契数，否则不是。

更新： @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;
}

结果甚至让我感到惊讶：

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

简而言之，生成器算法方式在所有正 int 值上都优于基于公式的解决方案 - 即使接近最大 int 值，它的速度也快两倍以上！
基于信念的性能优化就这么多；-)

根据记录，修改上述代码以使用 long 变量而不是 int，生成器算法变得更慢（正如预期的那样，因为现在必须将 long 值相加），公式开始变得更快的转换点约为 1000000000000L，即 10¹²。

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

这将转换点降低到大约。 10⁸（对于 long 版本 - 对于所有 int 值，具有 int 的生成器仍然更快）。毫无疑问，用 @Moron 建议的内容替换 sqrt 调用会进一步降低切换点。

我（和 IVlad）的观点很简单，那就是总会有一个切换点，低于该点生成器算法会更快。因此，关于谁表现更好的说法在一般情况下没有意义，只有在特定背景下才有意义。

Answer 11

不要传递索引 n，而是编写一个接受限制的函数，并让它生成达到并包括该限制的斐波那契数。让它根据是否达到或跳过限制返回一个布尔值，您可以使用它来检查该值是否在序列中。

因为这是家庭作业，所以我们应该给你这样的推动......

Answer 12

好的。由于人们声称我只是在空谈（“事实”与“猜测”），没有任何数据支持，因此我编写了自己的基准。

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

这是输出

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

当 n=50 本身时，sqrt 方法击败了朴素方法，这可能是由于我的机器上存在硬件支持。即使它是 10^8（如 Peter 的测试），在该截止值下最多有 40 个斐波那契数，可以轻松地将其放入查找表中，并且对于较小的值仍然击败朴素版本。

另外，Peter 对 SqrtVersion 的实现很糟糕。他实际上并不需要使用 Math.Pow 计算两个平方根或计算幂。在发布基准结果之前，他至少可以尝试改进这一点。

无论如何，我会让这些事实来说明一切，而不是所谓的“猜测”。

Answer 13

正整数 x 是斐波那契数当且仅当 5x^2 + 4 和 5x^2 - 4 其中之一是完全平方数

Answer 14

有多种方法可用于确定给定数字是否在斐波那契数列中，可以在 维基百科。

然而，考虑到您已经完成的工作，我可能会使用更暴力的方法，例如以下内容：

1. 生成斐波那契数
2. 如果它小于目标数，则生成下一个斐波那契数并重复
3. 如果它是目标数 。
4. 如果大于目标数，则失败

我可能会使用递归方法，传入当前的 n 值（即计算第 n 个斐波那契数）和目标数。