C++|斐波那契数列

斐波那契数列是一个非常著名的数列，它的定义如下：

• ( F(0) = 0 )
• ( F(1) = 1 )
• ( F(n) = F(n-1) + F(n-2) ) 对于 ( n \geq 2 )

这个数列的前几项是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

斐波那契数列可以通过多种方法计算，包括递归、迭代和动态规划。下面我将提供几种不同的实现方式：

1. 递归实现（不推荐，效率低下）

递归是实现斐波那契数列的直观方法，但是它的时间复杂度是指数级的，因为有很多重复计算。

#include <iostream>

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

int main() {
    int n;
    std::cin >> n;
    std::cout << fibonacci(n) << std::endl;
    return 0;
}

2. 迭代实现

迭代方法的时间复杂度是线性的，空间复杂度也是线性的，因为它只需要存储前两个数。

#include <iostream>

int fibonacci(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n;
    std::cin >> n;
    std::cout << fibonacci(n) << std::endl;
    return 0;
}

3. 动态规划（空间优化）

动态规划方法与迭代方法类似，但是可以进一步优化空间复杂度到常数级别。

#include <iostream>

int fibonacci(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n;
    std::cin >> n;
    std::cout << fibonacci(n) << std::endl;
    return 0;
}

4. 矩阵快速幂方法（高级）

斐波那契数列还可以通过矩阵快速幂方法来计算，这种方法的时间复杂度是 ( O(\log n) )。

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

// 矩阵乘法
vector<vector<ll>> multiply(const vector<vector<ll>>& a, const vector<vector<ll>>& b) {
    vector<vector<ll>> result(2, vector<ll>(2, 0));
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                result[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return result;
}

// 矩阵快速幂
vector<vector<ll>> power(vector<vector<ll>> base, ll exponent) {
    vector<vector<ll>> result = {{1, 0}, {0, 1}};
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = multiply(result, base);
        }
        base = multiply(base, base);
        exponent /= 2;
    }
    return result;
}

ll fibonacci(int n) {
    if (n <= 1) return n;
    vector<vector<ll>> base = {{1, 1}, {1, 0}};
    vector<vector<ll>> result = power(base, n - 1);
    return result[0][0];
}

int main() {
    int n;
    std::cin >> n;
    std::cout << fibonacci(n) << std::endl;
    return 0;
}

这些方法展示了如何计算斐波那契数列的不同方式，从简单的递归到高效的矩阵快速幂方法。您可以根据需要选择合适的方法。

原文地址：https://blog.csdn.net/weixin_42964413/article/details/143481845

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！