小文’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 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

鸽巢原理(抽屉原理)的详解

抽屉原理 百科名片 ? 桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放两个苹果。这一现象就是我们所说的“抽屉原理”...

4797
来自专栏小詹同学

Leetcode打卡 | No.011 盛最多水的容器

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

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

2018.10.23NOIP模拟赛解题报告

比赛开场看T1一点思路都没有,不管怎么想都是\(O(n^2)\)的复杂度,做了好久终于发现自己傻逼了这就是个傻逼题。。

1043
来自专栏java 成神之路

高亮标红

3028
来自专栏数说工作室

统计师的Python日记【第七天:数据清洗(1)】

本文是【统计师的Python日记】第7天的日记 回顾一下: 第1天学习了Python的基本页面、操作,以及几种主要的容器类型。 第2天学习了python的函数、...

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

洛谷P1731 [NOI1999]生日蛋糕(爆搜)

设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i<M时,要求 R_i>R_{i+1}Ri​>Ri+1​ 且 H_i>H_{i+1}...

1051
来自专栏申龙斌的程序人生

参加steemit数学x程式大赛(第八回)

前一段时间参加了Steemit社区的两个活动,比如“接龙”创作大赛,五个人根据几张图片素材编出一篇小说,事先没有任何沟通,人员报名之后,顺序是随机指定的,我第一...

3106
来自专栏新智元

【看图识算法】这是你见过最简单的 “算法说明书”

【新智元导读】像阅读宜家的安装说明书一样学习算法,是怎样的体验?不伦瑞克工业大学的三名研究者制作了这份“算法说明书”,简明传神地解释了一些基本算法,一起来看图说...

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

42:出书最多

42:出书最多 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 假定图书馆新进了m(10 ≤ m ≤ 999)本图书,它们...

2875
来自专栏Laoqi's Linux运维专列

python3–装饰器

4186

扫码关注云+社区

领取腾讯云代金券