确定数字是否是斐波纳契数

Question

我需要编写一个Java代码来检查用户输入的数字是否在Fibonacci序列中.

我没有问题写Fibonacci序列输出,但(可能是因为它深夜)我正在努力想到"是否"它是斐波纳契数的序列.我一遍又一遍地开始.它确实在我的脑海里.

我现在拥有的是第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

阅读维基百科上标题为"识别斐波纳契数字"的部分.

或者,正整数z是斐波那契数,当且仅当5z ^ 2 + 4或5z ^ 2-4中的一个是完美平方时.[17]

或者,您可以继续生成斐波纳契数,直到一个等于您的数字:如果是,那么您的数字是斐波纳契数,如果不是,数字最终会变得比您的数字大,您可以停止.然而,这是非常低效的.

Answer 2

如果我理解正确,你需要做的是(而不是写出前n个斐波纳契数)是确定n是否是斐波那契数.

所以你应该修改你的方法以保持生成Fibonacci序列,直到你得到一个数> = 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 ¹².

Update2:正如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 3

n编写一个接受限制的函数,而不是传递索引,并使其生成斐波那契数字,直至并包括此限制.让它返回一个布尔值,具体取决于它是命中还是跳过限制,你可以使用它来检查该值是否在序列中.

既然是家庭作业,这样的推动可能就是我们应该给你的全部......