这几天忙于拜年,很久没更新文章了。对不住大家0.0。
今天给大家带来的是一个非常基础的题,可是博主刚开始写的算法超出运行时间了。
Fibonacci数列
Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。
当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。
数据规模与约定
1 <= n <= 1,000,000。
由于博主刚开始忽略的n的取值,直接用递归,后面当n值过大是导致程序卡死。
可能习惯用递归了而不喜欢用循环了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#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; } |
由于题目太简单,博主就不仔细讲解,希望大家引以为戒。一定要看清题目的要求。