【蓝桥杯】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;  }