题目描述

输入一个整数 n ，求斐波那契数列的第 n 项。

假定从0开始，第0项为0。(n<=39)

样例

输入整数 n=5 

返回 5

算法

(简单模拟)

1. 求这个的方法很多，此题数据小，所以简单模拟，比如n = 5，所以当n= 5的时候，a更新为第一项(a初值为第0项)，然后n–，当n=0的时候，a刚好更新道第5项，输出a即可。
2. 还有其他方法针对数据比较大的情况，戳这里

时间复杂度

$O(n)$
因为如果求第n项，那么就要求n次，所以是$O(n)$

C++ 代码

class Solution {
public:
    int Fibonacci(int n) {
        int a = 0, b = 1;
        while(n --)
        {
            int c = a + b;
            a = b, b = c;
        }
        return a;
    }
};