用 fn�� 表示斐波那契数列的第 n� 项，则有：f1=f2=1�1=�2=1 ，fn=fn−1+fn−2(n>2)��=��−1+��−2(�>2) 。 ​ 输入一个n�, 求出fn��。

这道题可以使用递归或迭代的方式来求解斐波那契数列的第 n 项。下面分别介绍这两种方法。

1. 递归

斐波那契数列的递推公式为 `fn=fn−1+fn−2(n>2)`，因此可以使用递归的方式来求解。递归的边界条件为 `f1=f2=1`，递归过程中不断调用自身来计算 `fn-1` 和 `fn-2` 的值。

#include <iostream>
using namespace std;

int Fibonacci(int n)
{
    if (n <= 2) {
        return 1;
    }
    return Fibonacci(n-1) + Fibonacci(n-2);
}

int main()
{
    int n;
    cin >> n;
    cout << Fibonacci(n) << endl;
    return 0;
}

2. 迭代

另一种求解斐波那契数列的方法是使用迭代的方式。我们可以定义两个变量 `f1` 和 `f2` 来依次计算每一项的值。初始时，`f1` 和 `f2` 的值都为 1，然后我们不断更新 `f1` 和 `f2` 的值，直到计算出第 n 项的值。

#include <iostream>
using namespace std;

int Fibonacci(int n)
{
    if (n <= 2) {
        return 1;
    }
    int f1 = 1, f2 = 1;
    for (int i = 3; i <= n; i++) {
        int fn = f1 + f2;
        f1 = f2;
        f2 = fn;
    }
    return f2;
}

int main()
{
    int n;
    cin >> n;
    cout << Fibonacci(n) << endl;
    return 0;
}

这两种方法的时间复杂度都为 O(n)，但是递归方法由于需要不断调用自身，会产生大量的函数调用开销，因此在实际应用中不太适用。迭代方法则没有这个问题，因此更加高效。