题意：
        输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
        
方法一：
直接遍历

思路：设初值第一项x=1，第二项y=1。
            每次都用x和y生成新的y(即前两项生成第三项)，并使原先的y 变为x。
            循环遍历。
class Solution {
public:
    int Fibonacci(int n) {
        int x=1,y=1,t;//设初值第一项x=1，第二项y=1
        for(int i=3;i<=n;i++){
            t=y;
            y=x+y;//x和y生成新的y
            x=t;//原先的y 变为x
        }
        return y;
    }
};
时间复杂度：
空间复杂度：
方法二：
公式推导

思路：
    
        将斐波那契数列展开，如下：

        这里的只能应用于偶数的情况，而奇数情况会计算错误。
        因此，我们需要将 n 分成奇数和偶数两种情况：

    






 

class Solution {
public:
    
    int Fibonacci(int n) {
        if(n<=2)
            return 1;
        if(n%2==0)//偶数
            return Fibonacci(n/2)*Fibonacci(n/2+1)+Fibonacci(n/2-1)*Fibonacci(n/2);
        else//奇数
            return Fibonacci((n+1)/2)*Fibonacci((n+1)/2)+Fibonacci((n-1)/2)*Fibonacci((n-1)/2);
    } 
};
时间复杂度：
空间复杂度：