小文’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; }

123456789101112131415161718192021

#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; }

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏趣学算法

ACM竞赛学习指南(算法工程师成长计划)

1061
来自专栏Pytorch实践

【NLP】三分钟带你看懂如何做网页搜索

01 — 搜索基本过程 对于网页搜索,传统的过程可以理解为:用户提交POST,搜索引擎返回RESPONSE。最开始的搜索过程,用户基本上是提供关键词,然...

3379
来自专栏python读书笔记

《算法图解》NOTE 1-算法的渐近表示法以及二分法1 .渐近表示法2.二分法

1216
来自专栏数据结构与算法

agc016B - Colorful Hats(智商题)

有$n$个人,每个人有一种颜色,第$i$个人说除了我之外有$a_i$种不同的颜色,问是否存在一组合法解

702
来自专栏前端儿

数数

我们平时数数都是喜欢从左向右数的,但是我们的小白同学最近听说德国人数数和我们有些不同,他们正好和我们相反,是从右向左数的。因此当他看到123时会说“321”。

763
来自专栏AI科技大本营的专栏

AI 技术讲座精选:数学不好,也可以学习人工智能(六)——巧用数学符号

【AI100 导读】欢迎阅读《数学不好,也可以学好人工智能》系列的第六篇文章。如果你错过了之前的五部分,一定记得把它们找出来看一下!这篇文章作者会帮你学习数学符...

3358
来自专栏BestSDK

知其所以然之永不遗忘的算法

image.png 相信大部分同学曾经都学习过快速排序、Huffman、KMP、Dijkstra等经典算法,初次学习时我们惊叹于算法的巧妙,同时被设计者的智慧所...

2287
来自专栏编程之旅

算法时间复杂度

很多程序员,做了很长时间的编程工作却始终都弄不明白算法的时间复杂度的估算,这是很可悲的一件事情。因为弄不清楚,所以也就从不深究自己写的代码是否效率底下,是不是可...

671
来自专栏章鱼的慢慢技术路

解救小哈——DFS算法举例

2118
来自专栏有趣的Python

算法与数据结构(一):导论篇-算法的重要性

算法与数据结构 算法相当的重要 & 算法无处不在 思考:编译器是如何理解你所写的程序的。 编译器的存在涉及着各种算法。搜索引擎:搜索算法加排序算法 遍历1亿...

2994

扫码关注云+社区