Java斐波那契数列快速方法

Question

我需要为我的 Java 独立项目找到斐波那契数列的任务。以下是查找方法。

private static long getFibonacci(int n) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return (getFibonacci(n-1)+getFibonacci(n-2));
    }
}

private static long getFibonacciSum(int n) {
    long result = 0;

    while(n >= 0) {
        result += getFibonacci(n);
        n--;
    }
    return result;
}

private static boolean isInFibonacci(long n) {
    long a = 0, b = 1, c = 0;

    while (c < n) {
        c = a + b;
        a = b;
        b = c;
    }

    return c == n;
}

主要方法如下:

    long key = getFibonacciSum(n);
    System.out.println("Sum of all Fibonacci Numbers until Fibonacci[n]: "+key);

    System.out.println(getFibonacci(n)+" is Fibonacci[n]");

    System.out.println("Is n2 in Fibonacci Sequence ?: "+isInFibonacci(n2));

代码已完全完成并可以运行。但是如果 n 或 n2 大于正常值(斐波那契数列中的第 50 个数字)？代码将被耗尽。有什么建议吗？

Answer 1

有一种方法可以使用比奈公式即时计算斐波那契数

算法:

function fib(n):
   root5 = squareroot(5)
   gr = (1 + root5) / 2
   igr = 1 - gr
   value = (power(gr, n) - power(igr, n)) / root5

   // round it to the closest integer since floating 
   // point arithmetic cannot be trusted to give
   // perfect integer answers. 
   return floor(value + 0.5) 

完成此操作后，您需要了解您正在使用的编程语言及其行为方式。这可能会返回浮点十进制类型，而可能需要整数。

The complexity of this solution is O(1).