题目描述

斐波那契数的定义为： F_0 = F_1 = 1 ， F_i = F_{i - 1} + F_{i - 2} (i \ge 2) 。本题要求计算第 n 项斐波那契数（注意 n 从 0 开始计数）。请尝试用递归和循环两种方法实现。

注意：由于斐波那契数呈指数级增长，所以对比较小的 n 也会得到很大的计算结果。这里假设输出在 long long 型整数范围内，即 n \le 91 。

输入格式

输入在一行中给出一个非负整数 n (\le 91) 。

输出格式

在一行中输出第 n 项斐波那契数。

输入样例

46

输出样例

2971215073

题意

给出递推关系和初始值： F_0 = F_1 = 1 ， F_i = F_{i - 1} + F_{i - 2} (i \ge 2)

计算出 F_n 并输出。

思路

按题意模拟。注意 F_0 = 1 ，而不是 0 。

代码

void solve(){
    int n;
    cin >> n;
    long long a[92];
    a[0] = a[1] = 1;
    for(int i = 2;i <= n;i++){
        a[i] = a[i - 1] + a[i - 2];
    }
    cout << a[n];
}