【藍橋杯】BEGIN-4 Fibonacci數列

• 2019 年 11 月 8 日
• 筆記

版權聲明：本文為部落客原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。

本文鏈接：https://blog.csdn.net/weixin_42449444/article/details/86562090

題目描述：

Fibonacci數列的遞推公式為：Fn=Fn-1+Fn-2，其中F1=F2=1。

當n比較大時，Fn也非常大，現在我們想知道，Fn除以10007的餘數是多少。

輸入格式：

輸入包含一個整數n（1 <= n <= 1,000,000）。

輸出格式：

輸出一行，包含一個整數，表示Fn除以10007的餘數。

說明：在本題中，答案是要求Fn除以10007的餘數，因此我們只要能算出這個餘數即可，而不需要先計算出Fn的準確值，再將計算的結果除以10007取餘數，直接計算餘數往往比先算出原數再取余簡單。

輸入樣例1：

10

輸出樣例1：

55

輸入樣例：

22

輸出樣例：

7704

解題思路：

這TM不就是一道無腦遞歸的水題嗎？誒？！提交之後居然TLE 對不起 是我小瞧這道題了。沒那麼簡單~ 既然不能無腦遞歸，就老老實實地按照題目意思來吧。

AC程式碼：TLE程式碼：

#include <bits/stdc++.h>  using namespace std;    int Fib(int n)  {      if(n == 1 || n == 2)      {          return 1;      }      return Fib(n-1)+Fib(n-2);  }    int main()  {      int n;      scanf("%d",&n);      printf("%dn",Fib(n)%10007);      return 0;  }

AC程式碼：

#include <bits/stdc++.h>  using namespace std;    int Fib(int n)  {      //a作為f(n),b作為f(n+1)      int a = 1, b = 1;      for (int i = 1; i < n; i++)      {          swap(a,b);  //更新f(n)          b = (a+b)%10007;  //更新f(n+1)      }      return a;  }    int main()  {      int n;      scanf("%d",&n);      printf("%dn",Fib(n));      return 0;  }