Java斐波那契数列BigInteger

我试图运行一个程序,找到斐波那契数列中的第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)); } } 

当你用BigInteger替换int ,你应该做一些改变,但是,我改变了你的代码,并提出了这样的事情:

  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(BigInteger.ZERO)) { return BigInteger.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]; } 

//矩阵mutltiplier方法:

  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]))) } }; } 

我希望这会帮助你

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

Interesting Posts