跳转至

3、斐波那契数列

斐波那契数的简介

​ 斐波那契数列（Fibonacci sequence），是指从0和1开始，后续每一项都是前面两项的和。其前几项为0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144……依次类推。

​ 斐波那契数列起源于意大利数学家斐波那契（Leonardo Fibonacci）的著作《算盘书》中，其数列描述了理想化的兔子繁殖问题，后来被广泛应用于数学、计算机科学、自然科学和金融等领域。

​ 斐波那契数列有很多有趣的性质和应用。例如，相邻两项的比值会无限接近黄金比例（约为1.618），而黄金比例在美学、艺术和建筑设计中有重要的应用；斐波那契数列还可以用于解决一些与数列相关的数学问题，例如求解最大公约数、判断一个数是否为斐波那契数等。在计算机科学中，斐波那契数列的应用也非常广泛，例如动态规划、搜索算法、图形设计等。

求斐波那契第n个数的解法

一、递归解法

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;

int Fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    else {
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}

int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;

    cout << "The " << n << "th Fibonacci number is " << Fibonacci(n) << endl;

    return 0;
}

​ 以上代码使用递归方式实现斐波那契数列的计算。首先判断输入的n是否等于0或1，如果是则直接返回n；否则，递归地调用Fibonacci函数来计算第n项的值。

​ 在主函数中，用户输入要计算的斐波那契数列的项数，然后输出该项的值。

二、迭代解法

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;

int Fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }

    int prev = 0;
    int current = 1;
    int result;
    for (int i = 2; i <= n; i++) {
        result = prev + current;
        prev = current;
        current = result;
    }
    return result;
}

int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;

    cout << "The " << n << "th Fibonacci number is " << Fibonacci(n) << endl;

    return 0;
}

​ 递归方式实现斐波那契数列的计算会导致大量重复计算，因此效率较低。可以使用循环的方式优化代码，避免重复计算。以上代码使用循环的方式实现斐波那契数列的计算。首先判断输入的n是否等于0或1，如果是则直接返回n；否则，使用循环来计算第n项的值。

​ 在循环中，需要定义三个变量：prev、current和result，分别表示前一个斐波那契数列的值、当前斐波那契数列的值和要计算的斐波那契数列的值。初始时，prev等于0，current等于1，result等于0。然后循环从i=2开始，一直到i=n，每次计算出result的值，并将prev和current分别更新为当前的值，以便下一次循环的计算。最后返回result即可。

三、动态规划解法

​ 动态规划也可以用来解决斐波那契数列问题。我们可以利用一个数组 \(dp\) 来记录每一项的值，从 \(dp[0]\) 和 \(dp[1]\) 开始递推计算后续的项。具体地，我们可以使用以下状态转移方程：

\[dp[i] = dp[i-1] + dp[i-2]\]

​ 时间复杂度为 \(O(n)\)，空间复杂度为 \(O(n)\)，其中 \(n\) 是斐波那契数列的项数。需要注意的是，当 \(n\) 较大时，动态规划的空间复杂度可能会变得比较大，可以使用滚动数组来优化空间。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
using namespace std;

long long Fibonacci(int n) {
    vector<long long> dp(n + 1, 0);
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;

    cout << "The " << n << "th Fibonacci number is " << Fibonacci(n) << endl;

    return 0;
}

四、递归剪枝优化的解法

​ 斐波那契数列的递归实现在计算某些项时会产生大量的重复计算，导致时间复杂度指数级增长。剪枝法可以避免这种重复计算，从而降低时间复杂度。

​ 具体实现方法是使用一个数组 \(memo\) 来记录已经计算过的项，如果要计算的项已经在 \(memo\) 中出现过，则直接返回 \(memo\) 中的值。否则，继续递归计算，并将结果存入 \(memo\) 数组中，以便后续使用。时间复杂度为 \(O(n)\)，空间复杂度为 \(O(n)\)，其中 \(n\) 是斐波那契数列的项数。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
using namespace std;

long long Fibonacci(int n, vector<long long>& memo) {
    if (memo[n] != -1) {
        return memo[n];
    }

    if (n == 0) {
        memo[n] = 0;
    } else if (n == 1) {
        memo[n] = 1;
    } else {
        memo[n] = Fibonacci(n - 1, memo) + Fibonacci(n - 2, memo);
    }

    return memo[n];
}

int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;

    vector<long long> memo(n + 1, -1);

    cout << "The " << n << "th Fibonacci number is " << Fibonacci(n, memo) << endl;

    return 0;
}

*五、矩阵快速幂解法

​ 矩阵快速幂的基本思想是将幂次拆分成二进制表示，然后通过幂次的二进制位来快速计算矩阵的幂次。在本例中，我们将斐波那契数列的递推式写成矩阵形式：

\(\(\begin{bmatrix}F(n) \\ F(n-1)\end{bmatrix}=\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^{n-1}\begin{bmatrix}F(1) \\ F(0)\end{bmatrix}\)\)其中，\(\begin{bmatrix}F(1) \\ F(0)\end{bmatrix}\) 表示斐波那契数列的初始状态，\(\begin{bmatrix}F(1) \\ F(0)\end{bmatrix}=\begin{bmatrix}1 \\ 0\end{bmatrix}\)，因为 \(F(1)=1,F(0)=0\)。我们可以通过计算矩阵 \(\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}\) 的 \(n-1\) 次幂来得到 \(\begin{bmatrix}F(n) \\ F(n-1)\end{bmatrix}\)。具体实现中，我们使用了矩阵乘法的优化，即在矩阵相乘时利用矩阵的结合律和分配律，避免冗余计算。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
using namespace std;

typedef vector<vector<long long>> matrix;

matrix multiply(matrix a, matrix b) {
    int n = a.size();
    int m = b[0].size();
    int l = a[0].size();
    matrix c(n, vector<long long>(m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < l; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }

    return c;
}

matrix power(matrix a, int n) {
    if (n == 1) {
        return a;
    }

    matrix half = power(a, n / 2);
    matrix result = multiply(half, half);

    if (n % 2 == 1) {
        result = multiply(result, a);
    }

    return result;
}

long long Fibonacci(int n) {
    if (n == 0) {
        return 0;
    }

    matrix base = {{1, 1}, {1, 0}};
    matrix result = power(base, n - 1);
    return result[0][0];
}

int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;

    cout << "The " << n << "th Fibonacci number is " << Fibonacci(n) << endl;

    return 0;
}

六、黄金分割法

​ 斐波那契数列还有一个黄金分割法，可以在 \(O(1)\) 的时间内计算第n项。这个公式称为斐波那契数列通项公式，可以表示为：

\[F(n)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n\]
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cmath>
using namespace std;

long long Fibonacci(int n) {
    double phi = (1 + sqrt(5)) / 2;
    double psi = (1 - sqrt(5)) / 2;
    return round((pow(phi, n) - pow(psi, n)) / sqrt(5));
}

int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;

    cout << "The " << n << "th Fibonacci number is " << Fibonacci(n) << endl;

    return 0;
}

F(n) = [φn - (1 - φ)n] / √5 其中，φ=(1+√5)/2 是黄金分割比例。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用