确定一个数是否为斐波那契数的java

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

如果我理解正确，你需要做的（不是写出第一个n斐波那契数）是确定n是否是斐波那契数

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

更新：由于@Moron一再声称基于公式的算法在性能上优于上面简单的算法，我实际上做了一个基准比较——具体地说是雅格布的解决方案作为生成器算法和史蒂文的上一个版本作为基于公式的算法。以下是准确的代码供参考：

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值相加），公式开始变快的转换点约为10000000000L，即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的生成器速度更快）。毫无疑问，将sqrt调用替换为@Moron建议的调用将进一步降低切换点

我（和IVlad）的观点很简单，总是会有一个转换点，低于这个转换点，生成器算法会更快。因此，关于哪一个表现更好的说法在总体上没有意义，只是在一定的背景下

Answer 2

有许多方法可以用来确定给定的数字是否在斐波那契序列中，可以在wikipedia上看到其中的一个选择

然而，考虑到你已经做过的事情，我可能会使用一种更暴力的方法，例如：

1. 生成斐波那契数
2. 如果小于目标值，则生成下一个斐波那契并重复
3. 如果是目标数字，那么就成功了
4. 如果大于目标值，则失败

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

Answer 3

阅读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]

或者，你可以继续生成斐波那契数，直到其中一个等于你的数：如果是，那么你的数就是斐波那契数，如果不是，这些数最终会大于你的数，你可以停止。然而，这是相当低效的