定义

斐波那契数列是一个比较简单的数列，他们有递归式
f0 = 0
f1 = 1
fn = f(n - 1) + f(n - 2)定义

历史

斐波那契的研究文献最早由意大利天文学家卡西尼发表，卡西尼给出了关于斐波那契的一个古老的的恒等式
f(n + 1)f(n - 1) = (-1) ^ n

例题

http://acm.hdu.edu.cn/showproblem.php?pid=1715
Fibonacci数列，定义如下：
f(1)=f(2)=1
f(n)=f(n-1)+f(n-2) n>=3。
计算第n项Fibonacci数值。

import java.math.BigInteger;
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin = new Scanner(System.in);
		
		BigInteger[] nums = new BigInteger[1010];
		nums[1] = new BigInteger("1");
		nums[2] = new BigInteger("1");
		for(int i = 3; i <= 1000; i++)
			nums[i] = nums[i - 1].add(nums[i - 2]);
		
		int T = cin.nextInt();
		while(T > 0)
		{
			T--;
			int n = cin.nextInt();
			System.out.println(nums[n]);
		}

	}

}