小文’s blog–Fibonacci数列 –《蓝桥杯代码笔记3》

这几天忙于拜年，很久没更新文章了。对不住大家0.0。

今天给大家带来的是一个非常基础的题，可是博主刚开始写的算法超出运行时间了。

Fibonacci数列

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

数据规模与约定

1 <= n <= 1,000,000。

由于博主刚开始忽略的n的取值，直接用递归，后面当n值过大是导致程序卡死。

可能习惯用递归了而不喜欢用循环了。

#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\n", f(n)); return 0; }

由于题目太简单，博主就不仔细讲解，希望大家引以为戒。一定要看清题目的要求。