代码之家 › 专栏 › 技术社区 › ArkhamWarfare

Java Fibonocci序列BigInteger

fibonacci biginteger java

ArkhamWarfare · 技术社区 · 7 年前

我试图运行一个程序,找到斐波那契级数中的第n个序列;然而,问题是,我想在其中实现BigInteger,这样它可以运行1000甚至更多的值。

有什么方法可以有效地添加它吗?

import java.util.*;
import java.math.*;
public class fib {   
//Arkham
    /*public static BigInteger fibonacci2(int n) {
    if (n == 0 || n == 1) {
        return BigInteger.ONE;
    }
    return fibonacci2(n - 2).add(fibonacci2(n-1));
}*/

    public static int Fibonacci(int n) {

        int num = Math.abs(n);
        if (num == 0) {
            return 0;
        }
        else if (num <= 2) {
            return 1;
        }

        int[][] number = { { 1, 1 }, { 1, 0 } };
        int[][] result = { { 1, 1 }, { 1, 0 } };

        while (num > 0) {
            if (num%2 == 1) result = MultiplyMatrix(result, number);
            number = MultiplyMatrix(number, number);
            num/= 2;
        }
        return result[1][1]*((n < 0) ? -1:1);
    }

    public static int[][] MultiplyMatrix(int[][] mat1, int[][] mat2) {
        return new int[][] {
                { mat1[0][0]*mat2[0][0] + mat1[0][1]*mat2[1][0], 
                  mat1[0][0]*mat2[0][1] + mat1[0][1]*mat2[1][1] },
                { mat1[1][0]*mat2[0][0] + mat1[1][1]*mat2[1][0], 
                  mat1[1][0]*mat2[0][1] + mat1[1][1]*mat2[1][1] }
        };
    }

    public static void main(String[] args) {

        Scanner reader = new Scanner(System.in);  // Reading from System.in
        System.out.println("Enter a number: ");
        int n = reader.nextInt();

        System.out.println("\n" + Fibonacci(n));
    }
}

2 回复 | 直到 7 年前

Ð¼ÏÑÏÐ°Ð²ÑÖÐ¼o 7 年前

int 通过 BigInteger 您应该做一些更改,但是,我更改了您的代码,并提出了如下内容:

   public static BigInteger FibonacciB(int n) {
    final BigInteger one = BigInteger.ONE;
    final BigInteger zero = BigInteger.ZERO;
    final BigInteger two = new BigInteger(String.valueOf(2));
    final BigInteger minusOne = one.negate();

    BigInteger num = new BigInteger(String.valueOf(n));

    if (num.equals(zero)) {
        return zero;
    } else if (num.compareTo(two) <= 0) {
        return one;
    }

    BigInteger[][] number = {{one, one}, {one, zero}};
    BigInteger[][] result = {{one, one}, {one, zero}};

    while (num.compareTo(zero) > 0) {
        if (num.mod(two).equals(one)) result = MultiplyMatrixB(result, number);
        number = MultiplyMatrixB(number, number);
        num = num.divide(two);
    }

    if (num.compareTo(zero) < 0)
        return result[1][1].multiply(minusOne);
    return result[1][1];

}

//矩阵多乘子方法:

  public static BigInteger[][] MultiplyMatrixB(BigInteger[][] mat1, BigInteger[][] mat2) {

    return new BigInteger[][]{
            {(mat1[0][0].multiply(mat2[0][0])).add((mat1[0][1].multiply(mat2[1][0]))),
                    (mat1[0][0].multiply(mat2[0][1])).add((mat1[0][1].multiply(mat2[1][1])))
            },
            {
                    (mat1[1][0].multiply(mat2[0][0])).add((mat1[1][1].multiply(mat2[1][0]))),
                    (mat1[1][0].multiply(mat2[0][1])).add((mat1[1][1].multiply(mat2[1][1])))
            }
    };
}

-1

Andreas 7 年前

java是正确的工具吗?可能 Kotlin

  tailrec fun fibonacci(i:BigInteger, current:BigInteger=zero, next:BigInteger=one):BigInteger {
    return if (i == zero) current else iterate(i - one, next, current + next)
  }

(摘自 https://github.com/russel/Fibonacci/blob/master/Kotlin/src/main/kotlin/uk/org/winder/maths/fibonacci/fibonacci.kt )