藍橋杯練習題（1）——斐波那契數列

最近參加了藍橋杯比賽，将收集一些我練習的題，題目來源有練習系統和往年例題等。

題目如下：

問題描述

Fibonacci數列的遞推公式為：Fn=Fn-1+Fn-2，其中F1=F2=1。

當n比較大時，Fn也非常大，現在我們想知道，Fn除以10007的餘數是多少。

輸入格式

輸入包含一個整數n。

輸出格式

輸出一行，包含一個整數，表示Fn除以10007的餘數。

說明：在本題中，答案是要求Fn除以10007的餘數，是以我們隻要能算出這個餘數即可，而不需要先計算出Fn的準确值，再将計算的結果除以10007取餘數，直接計算餘數往往比先算出原數再取餘簡單。

樣例輸入

10

樣例輸出

55

樣例輸入

22

樣例輸出

7704

資料規模與約定

1 <= n <= 1,000,000。

這個題目與我之前做的劍指offer上的題幾乎一樣，這裡要注意的是，每一次算值的時候F(n+1)直接寫成%10007後的值可以防止他過大。

另外我當時在練習系統上犯了個小錯誤，這種線上編譯的題（像藍橋杯，公司的面試題等等）一般都不能有pakage語句，類一般都叫Main。當時還找了好久。。。。。

import java.util.Scanner;

public class Main{


public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		new String("fsfsda").indexOf("fafsd");
		int n = scanner.nextInt();
		int result = 0;
		int resultOne = 0;		//F(n-1)
		int resultTwo = 1;		//F(n-2)
		
		if (n == 1 || n == 2) {
			System.out.println(1 % 10007);
		}else{	
			for (int i = 2; i <= n; i++) {
				result = (resultOne + resultTwo) % 10007;
				resultOne = resultTwo;
				resultTwo = result;		
			}		
			System.out.println(result );		
		}
		
}
}