时间复杂度 O(log⁡n)O(\log n)O(logn)，遥遥领先。

#include <iostream> using namespace std; int main() { // 定义一个数组来存储斐波那契数列的前40项 long long fib[41]; }

#include<bits/stdc++.h> using namespace std; int main(){ int n; double p5=pow(5,0.5); cin>>n; int ans=1.0/p5*(pow((1+p5)/2,n)-pow((1-p5)/2,n)); cout<<ans; return 0; }

用递归:时间复杂度高

#include<bits/stdc++.h> using namespace std; int a[50]; int main(){ a[0]=1;a[1]=1; int n; cin>>n; for(int i = 2;i<=n;i++){ a[i]=a[i-1]+a[i-2]; } cout<<a[n-1]; }

#include<iostream> using namespace std; int main() { int n; cin>>n; if(n1 || n2) { cout<<1<<endl; return 0; } int last1=1; int last2=1; int now=0; for(int i=3;i<=n;i++) { now=last1+last2; last2=last1; last1=now; } cout<<now<<endl; return 0; } //这里要注意那个if是一定要写的，并且要加return 0; | 头文件 |main | |- - -|-- -| | if | cout | 有问题可以找我（程序）。

#include<iostream> using namespace std; int main(){ int n,f,r,t; cin >> n; }

#include <bits/stdc++.h> using namespace std; int main() { int N; cin>>N; int a[41]={0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986}; cout<<a[N]; return 0; }

#include <bits/stdc++.h> using namespace std; int main(){ int n=0; cin>>n; int a[41]={0}; a[1]=1; a[2]=1; for(int i=3;i<=n;i++){ a[i]=a[i-1]+a[i-2]; } cout<<a[n]; return 0; }

#include <iostream> using namespace std; int f(int n){ if (n<=2){ return 1; } return f(n-1)+f(n-2); int main(){ int n; cin >> n; cout<<f(n); return 0; }

动态规划解法

是人都知道斐波那契数列 n₁+n₂=n₃以此类推

#include<bits/stdc++.h> using namespace std; int n,ans=0; int a[100]; int main(){ cin >> n; a[1]=1; a[2]=1; for(int i=2;i<=n;i++){ a[i]=a[i-1]+a[i-2] } cout << a[n]; return 0; }

#include<bits/stdc++.h> using namespace std; int a[100]; int main(){ int n; cin>>n; a[1]=1; a[2]=1; for(int i=3;i<=40;i++){ a[i]=a[i-1]+a[i-2];}//这里定义斐波那契数列，不用一个一个输 cout<<a[n]; return 0;}

以下是题解 #include<bits/stdc++.h> using namespace std; int a[40]; int f(int n){ if(n1||n2){ return 1;} if(a[n]!=0)return a[n]; return a[n]=f(n-1)+f(n-2);} int main(){ int n; cin>>n; cout<<f(n); return 0;}

#include <iostream> using namespace std; int main() { long long a[50]; long long b[50]; a[0]=1; a[1]=1; b[0]=1; b[1]=1; int n,m;cin>>n; for(int i=2;i<=n;i++) { a[i]=a[i-1]+a[i-2]; } cout<<a[n-1]; }