c++斐波那契数列求第n项最快方法是什么

斐波那契数列求第n项的最快方法是使用矩阵快速幂。

斐波那契数列可以表示为如下的递推关系式：F(n) = F(n-1) + F(n-2)，其中F(0)=0，F(1)=1。

将关系式转换成矩阵形式：{{F(n), F(n-1)}, {F(n-1), F(n-2)}} = {{1, 1}, {1, 0}} ^ n * {{F(1), F(0)}, {F(0), F(-1)}}。

其中，^ 表示矩阵的乘方运算。

利用矩阵快速幂，可以在O(logn)的时间复杂度内计算出斐波那契数列的第n项的值。

下面是使用矩阵快速幂计算斐波那契数列第n项的代码：

#include <iostream>
#include <vector>
using namespace std;

// 矩阵乘法
vector<vector<long long>> matrixMultiply(vector<vector<long long>>& A, vector<vector<long long>>& B)
{
    int m = A.size();
    int n = B[0].size();
    vector<vector<long long>> C(m, vector<long long>(n, 0));
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            for(int k = 0; k < A[0].size(); k++)
            {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

// 矩阵快速幂
vector<vector<long long>> matrixPow(vector<vector<long long>>& A, int n)
{
    vector<vector<long long>> ans = {{1, 0}, {0, 1}}; // 单位矩阵
    while(n > 0)
    {
        if(n & 1)
            ans = matrixMultiply(ans, A);
        A = matrixMultiply(A, A);
        n >>= 1;
    }
    return ans;
}

// 斐波那契数列第n项
long long fib(int n)
{
    if(n == 0)
        return 0;
    vector<vector<long long>> A = {{1, 1}, {1, 0}};
    vector<vector<long long>> B = {{1}, {0}};
    vector<vector<long long>> C = matrixMultiply(matrixPow(A, n-1), B);
    return C[0][0];
}

int main()
{
    int n;
    cout << "请输入n的值: ";
    cin >> n;
    cout << "斐波那契数列第" << n << "项的值为: " << fib(n) << endl;
    return 0;
}

该方法的时间复杂度为O(logn)，比递归和循环方法都要快。