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 将超过正常值（Fib.Seq. 中的第 50 个数字）？代码将被运行。有什么建议吗？

Answer 1

50 或略低于 50 是直接递归实现的极限。如果你想比这更高，你可以切换到迭代或动态编程 (DP) 方法。我建议从中了解这些：https://www.javacodegeeks.com/2014/02/dynamic-programming-introduction.html。并且不要忘记在 David 的评论中查看解决方案，真正有效。 links 显示了如何使用 DP 方法即时计算 n = 500000。 link 还解释了 "memoization" 的概念，即通过存储中间（但稍后可重新调用）结果来加速计算。

Answer 2

这种求解方法称为动态规划

在这个方法中我们记住了之前的结果

所以当递归发生时，cpu 不需要做任何工作来一次又一次地重新计算相同的值

class fibonacci
{
static int fib(int n)
 {
/* Declare an array to store Fibonacci numbers. */
   int f[] = new int[n+1];
   int i;

   /* 0th and 1st number of the series are 0 and 1*/
   f[0] = 0;
   f[1] = 1;

   for (i = 2; i <= n; i++)
   {
       /* Add the previous 2 numbers in the series
        and store it */
       f[i] = f[i-1] + f[i-2];
    }

    return f[n];
  }

public static void main (String args[])
    {
       int n = 9;
       System.out.println(fib(n));
    }
}

Answer 3

是的，您可以做的一项改进是 getFibonacciSum()：您可以做与 isInFibonacci 正在做并一次获得总和，例如：

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

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

Answer 4

有一种方法可以使用比奈公式

即时计算斐波那契数列

算法：

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)

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

The complexity of this solution is O(1).

Answer 5

public static long getFib(final int index) {
        long a=0,b=0,total=0;
        for(int i=0;i<= index;i++) {
                if(i==0) {
                     a=0;
                     total=a+b;
                 }else if(i==1) {
                     b=1;
                     total=a+b;
                 }

            else if(i%2==0) {
                total = a+b;
                a=total;                
            }else {
                total = a+b;
                b=total;
            }

        }
        return total;
    }

Answer 6

好吧，我的解决方案是使用 Map 和 { { F(2k) = F(k)[2F(k+1)−F(k)] }, { F(2k+1) = F (k+1)^2+F(k)^2 } }。（公式来源：https://www.nayuki.io/page/fast-fibonacci-algorithms）

也可以使用列表而不是地图来实现它，但这只是重新发明轮子。

使用Iteration解决方案时，我们不用担心运行内存不足，但是获取fib(1000000)需要很多时间，例如。在这个解决方案中，对于非常非常非常大的输入（比如 100000 亿，idk），我们可能运行内存不足，但它要快得多。

public BigInteger fib(BigInteger n) {
    if (n.equals(BigInteger.ZERO))
        return BigInteger.ZERO;
    if (n.equals(BigInteger.ONE) || n.equals(BigInteger.valueOf(2)))
        return BigInteger.ONE;
    
    BigInteger index = n;
    
    //we could have 2 Lists instead of a map
    Map<BigInteger,BigInteger> termsToCalculate = new TreeMap<BigInteger,BigInteger>();
    
    //add every index needed to calculate  index n
    populateMapWhitTerms(termsToCalculate, index);
    
    termsToCalculate.put(n,null); //finally add n to map
    
    Iterator<Map.Entry<BigInteger, BigInteger>> it = termsToCalculate.entrySet().iterator();//it 
    it.next(); //it = key number 1, contains fib(1);
    it.next(); //it = key number 2, contains fib(2);
    
    //map is ordered
    while (it.hasNext()) {
        Map.Entry<BigInteger, BigInteger> pair = (Entry<BigInteger, BigInteger>)it.next();//first it = key number 3
        index = (BigInteger) pair.getKey();
        
        if(index.remainder(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
            //index is divisible by 2
            //F(2k) = F(k)[2F(k+1)−F(k)]
            pair.setValue(termsToCalculate.get(index.divide(BigInteger.valueOf(2))).multiply(
                    (((BigInteger.valueOf(2)).multiply(
                            termsToCalculate.get(index.divide(BigInteger.valueOf(2)).add(BigInteger.ONE)))).subtract(
                                    termsToCalculate.get(index.divide(BigInteger.valueOf(2)))))));
        }
        else {
            //index is odd
            //F(2k+1) = F(k+1)^2+F(k)^2
            pair.setValue((termsToCalculate.get(index.divide(BigInteger.valueOf(2)).add(BigInteger.ONE)).multiply(
                    termsToCalculate.get(index.divide(BigInteger.valueOf(2)).add(BigInteger.ONE)))).add(
                            (termsToCalculate.get(index.divide(BigInteger.valueOf(2))).multiply(
                            termsToCalculate.get(index.divide(BigInteger.valueOf(2))))))
                    );
        }
    }
    
    // fib(n) was calculated in the while loop
    return termsToCalculate.get(n);
}

private void populateMapWhitTerms(Map<BigInteger, BigInteger> termsToCalculate, BigInteger index) {
    if (index.equals(BigInteger.ONE)) { //stop
        termsToCalculate.put(BigInteger.ONE, BigInteger.ONE);
        return;
        
    } else if(index.equals(BigInteger.valueOf(2))){
        termsToCalculate.put(BigInteger.valueOf(2), BigInteger.ONE);
        return;
        
    } else if(index.remainder(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
        // index is divisible by 2
        // FORMUMA: F(2k) = F(k)[2F(k+1)−F(k)]
                    
        // add F(k) key to termsToCalculate (the key is replaced if it is already there, we are working with a map here)
        termsToCalculate.put(index.divide(BigInteger.valueOf(2)), null);
        populateMapWhitTerms(termsToCalculate, index.divide(BigInteger.valueOf(2)));

        // add F(k+1) to termsToCalculate
        termsToCalculate.put(index.divide(BigInteger.valueOf(2)).add(BigInteger.ONE), null);
        populateMapWhitTerms(termsToCalculate, index.divide(BigInteger.valueOf(2)).add(BigInteger.ONE));
        
    } else {
        // index is odd
        // FORMULA: F(2k+1) = F(k+1)^2+F(k)^2

        // add F(k+1) to termsToCalculate
        termsToCalculate.put(((index.subtract(BigInteger.ONE)).divide(BigInteger.valueOf(2)).add(BigInteger.ONE)),null);
        populateMapWhitTerms(termsToCalculate,((index.subtract(BigInteger.ONE)).divide(BigInteger.valueOf(2)).add(BigInteger.ONE)));

        // add F(k) to termsToCalculate
        termsToCalculate.put((index.subtract(BigInteger.ONE)).divide(BigInteger.valueOf(2)), null);
        populateMapWhitTerms(termsToCalculate, (index.subtract(BigInteger.ONE)).divide(BigInteger.valueOf(2)));
    }
    
}

Answer 7

我检查了所有解决方案，对我来说，最快的方法是使用流，并且可以轻松修改此代码以收集所有斐波那契数。

 public static Long fibonaciN(long n){
    return Stream.iterate(new long[]{0, 1}, a -> new long[]{a[1], a[0] + a[1]})
            .limit(n)
            .map(a->a[0])
            .max(Long::compareTo)
            .orElseThrow();
}

Java斐波那契数列快速方法

Java Fibonacci Sequence fast method

java

fibonacci