斐波那契数列2-递推方法

Question

斐波那契数列在数学上，斐波那契数列以递推的方法定义：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）

Answer 1

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