藍橋杯2014年以前JAVA曆年真題及答案整理——Fibonacci數列

問題描述

      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。

java實作：

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in) ;
        int num = scanner.nextInt() ;
        int[] a = new int[num+2] ;
        a[1] = a[2] = 1;
        if (num == 1) {
            a[num] = 1 ;
        }else if (num == 2) {
            a[num] = 1 ;
        }else {
            for (int i = 3; i <= num; i++) {
                a[i] = (a[i - 1] + a[i - 2]) % 10007 ;
            }
        }
        System.out.println(a[num]);
    }
}
           

C實作：

#include <stdio.h>

int F(int n)
{
    int i, s1 = 1, s2 = 1, s3 = 1;
    for (i = 3; i <= n; i++)
    {
        s3 = s1 + s2;
        if (s3 > 10007) 
            s3 -= 10007;
        s1 = s2;
        s2 = s3;
    }
    return s3;
}

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