藍橋杯-入門基礎 Fibonacci數列 Java版

大神：https://blog.csdn.net/sihai12345/article/details/79252575

問題描述

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。

package OneChapter;

import java.io.BufferedReader;  

import java.io.IOException;  

import java.io.InputStreamReader; 

public class Fibonacci {  

    //你的main函數程式段裡有代碼會跑出IOException，此時可以選擇try catch捕獲自己編寫代碼處理，也可以像上面那樣抛出，throws 直接給java虛拟機

    public static void main(String[] args) throws IOException{  

        //輸出的預設為字元串

        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));  

        String s=reader.readLine();  

        int n=Integer.valueOf(s);  

        int f1=1,f2=1,f3=0;  

        if(n<3){  

            System.out.print("1");  

            return;

            }  

        for(int i=3;i<=n;i++)  

        {

            if(f1>10007)f1=f1%10007;  

            if(f2>10007)f2=f2%10007;  

            f3=f1+f2;  

            f1=f2;  

            f2=f3;  

        }  

        System.out.print(f3%10007);  

    }  

}