斐波那契鳳尾（Java）

牛客連結

斐波那契鳳尾

題目

NowCoder号稱自己已經記住了1-100000之間所有的斐波那契數。

為了考驗他，我們随便出一個數n，讓他說出第n個斐波那契數。當然，斐波那契數會很大。是以，如果第n個斐波那契數不到6位，則說出該數；否則隻說出最後6位。

輸入描述

輸入有多組資料。

每組資料一行，包含一個整數n (1≤n≤100000)。

輸出描述

對應每一組輸入，輸出第n個斐波那契數的最後6位。

解題思路

按理說求斐波那契數時，不使用遞歸的算法的複雜度會低，但是在牛客運作後還是會逾時，但是如果提前将1-100000的斐波那契數存儲到數組中，直接根據輸入的資料查詢就可以通過了（可能是因為牛客從輸入開始算的複雜度，畢竟查詢數組取出資料比計算快），大于六位數的時候直接将後六位存儲進去，運算下一個斐波那契數時不影響後六位的值。需要注意的是如果和100000取餘後是5位數呢?也就是倒數第六位數剛好是0的情況，例如：假設有一個斐波那契數是1024568，那麼和100000取餘後的數為24568了，但是如果取後六位則應該補0，是以直接将大于等于6位數的斐波那契數（n >= 29）進行%06d的格式輸出即可。

代碼實作

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] fib = new int[100001];
        fib[0] = 1;
        fib[1] = 1;
        for (int i = 2;i<fib.length;i++) {
            fib[i] = (fib[i-1] + fib[i-2])%1000000;
        }
        while (sc.hasNext()) {
            int num = sc.nextInt();
            if (num<29) {
                System.out.println(fib[num]);
            }else {
            System.out.printf("%06d\n",fib[num]);
             }
        }
    }
}