蓝桥杯练习题 Fibonacci数列的递推公式为：Fn=Fn

如何快速调整电脑屏幕亮度：点击键盘上的'Fn'键+对应功能键（如F5/F6） #生活技巧# #数码产品使用技巧# #电脑操作教程#

比较不错的学习人工智能学习网站，各个知识点也讲的很不错：人工智能学习教程

题目：
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。 当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

样例输入
10
样例输出
55

样例输入
22
样例输出
7704

两种方式解决：

第一种递归，但是对于较大的数可能会超时
第二种使用迭代，对于时间复杂度为O(n)

第一种使用递归：

#include <iostream> using namespace std; int fib(int n) {if(n==1) //第一个出口return 1;else if(n==2) //第二个出口return 1;else return fib(n-1)%10007+fib(n-2)%10007; //因为递推公式为Fn=Fn-1+Fn-2，所以出口会有两个//但是会有大量的重复运算，导致大数据运算会超时 } int main() {int n;cin>>n;cout<<fib(n);return 0; } 1234567891011121314151617181920

注意：使用递归的话，内存空间不会占太大，但是时间复杂度会很大，很容易输入n过大而导致超时，复杂度为O(2^n)。

第二种使用迭代：

#include <iostream> using namespace std; int main() {int n;cin>>n;long long a[n];a[0] = 1,a[1] = 1;//直接使用迭代这样的话时间复杂度为O(n)，这样的话不会超时，但是如果n大的话，空间复杂度会更大，以空间换时间//数组存储的话下标 0 1 2 3 4 5 6 7 8 9//分别对应数为 1 1 2 3 5 8 13 21 34 55for(int i=2;i<n;i++){a[i] = (a[i-2]+a[i-1])%10007;}cout<<a[n-1]<<endl;return 0; } 1234567891011121314151617

注意：这里是创建了数组并且不断保存之前的数据，而不像递归那样有着大量的重复运算，空间换取时间，时间复杂度为O(n)。

题目总结：
对于这道题，更好解决方法应当使用迭代，而不是用递归，递归用于解决较复杂问题会产生更好的效果

我是长路，感谢您的收看。
欢迎关注我的公众号：长路Java，其中会包含软件安装等其他一些资料，包含一些视频教程以及学习路径分享。
也可以加群：891507813 我们可以一起探讨学习

网址：蓝桥杯练习题 Fibonacci数列的递推公式为：Fn=Fn https://www.yuejiaxmz.com/news/view/437527

相关内容

数学归纳法全讲解（第一、第二、弱、强、双变量）带示例
第六章摩擦专题知识讲座.pptx
智能窗户和门的控制：提高家庭安全1.背景介绍 随着人工智能技术的发展，智能家居已经成为现代生活中不可或缺的一部分。智能窗
生态文明建设视野中的绿色技术
智能健康管理系统：如何帮助患者更好地管理自己的健康
智能家电与家庭教育：互动模式1.背景介绍 随着科技的不断发展，智能家电已经成为了人们生活中不可或缺的一部分。智能家电不仅
智能健康管理系统：如何帮助患者更好地管理自己的健康1.背景介绍 随着人口寿命的延长和生活质量的提高，健康管理变得越来越重
6.4生活中的圆周运动 教学设计 高一下学期物理人教版（2019）必修第二册
Javascript基础第六天知识点以及案例：作用域、JS预解析、对象
电脑硬件使用技巧

随便看看