计算Fibonacci的第5000项

Fibonacci数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)（n>=4，n∈N*）。（引用自百度百科）

如何实现

实现该问题的关键点在于如何将第5000项存下来？
通过计算，第5000项大概有超过1000位数。这里我们用两种方式来解决。

1. 将数用数组来表示，进行加减。
2. 使用Java语言提供的BigInteger类来实现。

代码如下：

import java.math.BigInteger;
public class Demo {//用数组来是实现。该函数返回的是Fibonacci的第1项到第N项（以字符串表示）public static StringBuilder[] FibonacciByArray(int N){//Fibonacci的第5000项大约有1150位，故初始化为数组为int[5001][1101]int[][] temp = new int[5001][1101];temp[1][1100] = 1;temp[2][1100] = 1;//temp[3][1100] = 2;for (int i = 3; i <= N; i++) {for (int j = 1100; j >=0 ; j--) {//如果相加大于10就进位if(temp[i - 1][j]+temp[i - 2][j] >= 10){temp[i][j - 1] =temp[i][j - 1] + 1;}temp[i][j] = temp[i][j]+(temp[i - 1][j]+temp[i - 2][j])%10;//判断是否进位if(temp[i][j] == 10){temp[i][j - 1] += 1;temp[i][j] = 0;}}}//对temp数组进行处理，并转换成字符串。StringBuilder[] s = new StringBuilder[5001];for (int i = 1; i <= N; i++) {int j=0;while(temp[i][j]==0)j++;StringBuilder sb = new StringBuilder();for (int k = j; k < 1101; k++) {sb.append(temp[i][k]);}s[i] = sb;}return s;}//用BigInteger来实现public static BigInteger FibonacciByBigInteger(int n){BigInteger bi1 = new BigInteger("1");BigInteger bi2 = new BigInteger("1");BigInteger bi3 = new BigInteger("-1");if(n == 1){return bi1;}else if(n == 2){return bi2;}for (int i = 3; i <= n; i++) {bi3 = bi1.add(bi2);bi1 = bi2;bi2 = bi3;}return bi3;}public static void main(String[] args) {int N = 5000;for (int i = 1; i <= N; i++) {System.out.println("第" + i + "项："+FibonacciByBigInteger(i));}StringBuilder[] sbs = FibonacciByArray(N);int i = 1;for (int j = 1; j <= N; j++) {System.out.println("第" + j + "项："+sbs[j]);}}
}

点击这里查看BigInteger的用法