[每日一題] 64. 斐波那契鳳尾(fib數列、setw與setfill函數)

1. 題目來源

連結：斐波那契鳳尾

來源：牛客網

2. 題目說明

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

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

輸入描述：

輸入有多組資料。

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

輸出描述：

對應每一組資料，輸出在給定的日期範圍（包含開始和結束日期）内能賺多少錢。

示例：

輸入

1

2

3

4

100000

輸出

62

29

3. 題目解析

題目要求輸出斐波那契數列的第n項，最容易寫的方法就是用循環求出每一項了。而它要求的是後六位，那麼我們 隻需要存儲後六位就行了。在此先求斐波那契數列在100000以内的每一項的後六位，然後需要的時候直接輸出數組裡的對應值即可。

以下代碼用通常的循環法解決。值得注意的一點，C++在輸出位數上的設定要用到C++的兩個輸出控制，setw(位數)，和setfill(指定字元)。

4. 代碼展示

// write your code here cpp
#include <bits/stdc++.h>

using namespace std;

int main() {
    int fib[100001];
    fib[0] = 1;
    fib[1] = 1;
    // 提前計算斐波那契數列，隻保留後6位
    for (int i = 2; i <= 100000; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
        fib[i] = fib[i] % 1000000;  // 由于隻是相加，是以隻要後六位不影響下一個數的結果
    }
    
    int n;
    while (cin >> n) {
        if (n < 29)
            cout << fib[n] << endl;
        else
            // printf("%06d\n", fib[n]);
            cout << setw(6) << setfill('0') << fib[n] <<  endl;
    }
    return 0;
}