[编程] 斐波那契数列

[编程] 斐波那契数列

分值：250

程序执行时限: 600 ms

假设n为正整数，斐波那契数列定义为： 

f(n) = 1, n < 3; 

f(n) = f(n-1) + f(n-2), n>=3 

现在请你来计算f(n)的值，但是不需要给出精确值，只要结果的后六位即可。 

输入：一行，包含一个正整数n，且0<n<1000 

输出：一行，f(n)的后6位（十进制，不足6位不补零）

public class U442p6 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
	    int n = Integer.parseInt(scanner.nextLine());
	    BigInteger count = getCount(n);
	    String string = count.toString();
	    if(string.length()>6){
	    	string = string.substring(string.length()-6);
	    }
		System.out.println(string);
	}
	
	// 递归实现方式  （效率低）
	public static BigInteger digui(int n){
	  if(n<3){
		  return new BigInteger("1");
	  }else{
		  return digui(n-1).add(digui(n-2));
	  }
	
	}
	
	// 递推实现方式  （效率高）
	public static BigInteger getCount(int n){
		if(n<3) return new BigInteger("1");
		
		BigInteger  a = new BigInteger("1");
		BigInteger  b = new BigInteger("1");
		BigInteger  c = new BigInteger("0");
		for(int i=3;i<=n;i++){
			c = a.add(b);
			a = b;
			b = c;
		}
		return c;
	}
}