斐波那契数列在数学上，斐波那契数列以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n≥3，n∈N*）【注意：n<=80】
#include <stdio.h>
long long fib(int n);
int main(void) {
int n;
scanf("%d",&n);
printf("fib(%d)=%lld",n,fib(n));
return 0;
}
/*提交以下代码*/
long long fib(int n) {
}
输入
1行，第几项n
输出
见样例
样例输入 Copy
5
样例输出 Copy
fib(5)=5
提示
递推求解的时间复杂度比较低，是O（N）
#include <iostream>
int fib(int n) {
if (n == 1 && n == 2)
return 1;
int fn1 = 1;
int fn2 = 1;
int res = 0;
for (int i = 3; i <= n; i++)
{
res = fn1 + fn2;
fn1 = fn2;
fn2 = res;
}
return res;
}
int main()
{
int n;
std::cin >> n;
int ans = fib(n);
std::cout << ans;
}
long long fib(int n) {
if(n<=2)
return 1;
return fib(n-1)+fib(n-2);
}