問題描述
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。

錦囊1 使用數組來保存F序列，只保存除10007的餘數。
錦囊2 先令F[1]=1, F[2]=1，然後用F[i]=(F[i-1]+F[i-2])%10007來計算F[i]。

錯誤的答案：
#include <stdio.h>

//這是老師上課講的遞歸法。。。
int F(int n)
{
    if (n <= 2)
        return 1;
    else
        return F(n - 1) + F(n - 2);
}

int main()
{
    int n;
    int reminder;
    scanf("%d", &n);
    reminder = F(n) % 10007;
    printf("%d\n", reminder);
    return 0;
}

評測結果  運行超時
得分  30  
CPU使用  運行超時  
內存使用  62.62MB  

正確的答案：
#include <stdio.h>

int main()
{
    int n, i;
    int F[3] = {1, 1, 1};
    scanf("%d", &n);
    if (n >= 3)
    {
        for (i = 3; i <= n; i++)
        {
            F[2] = (F[1] + F[0]) % 10007;
            F[0] = F[1];
            F[1] = F[2];
        }
    }
    printf("%d\n", F[2]);
    return 0;
}

評測結果  正確
得分  100  
CPU使用  0ms  
內存使用  1.597MB  

遞歸法寫出的函數雖然簡單，但是很耗系統資源。

輸入：1000000
輸出：114

--------------------------------
Process exited after 11.82 seconds with return value 0
Press any key to continue . . .

2樓的程序，即便是輸入50，都無法得出計算結果。不過輸入40的話：
40
2573

--------------------------------
Process exited after 2.181 seconds with return value 0
Press any key to continue . . .

其實，應該不需要判斷n>=3：
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, i;
    int F[3] = {1, 1, 1};
    scanf_s("%d", &n);
    for (i = 3; i <= n; i++)
    {
        F[2] = (F[0] + F[1]) % 10007;
        F[0] = F[1];
        F[1] = F[2];
    }
    printf("%d\n", F[2]);
    system("pause");
    return 0;
}

仍然是前兩個數相加得到新數，只不過數組只存儲三個元素，且都是存儲的都是餘數。