【C++】B2064 斐波那契数列

💯前言

• 斐波那契数列问题是算法学习中的经典例题。通过这一类问题，不仅可以巩固对递推关系和循环的理解，还能学习到如何通过预处理和查表优化代码效率。本次文章将通过一道具体的题目，从题目分析、代码实现、优化思路以及扩展应用四个部分，全面解析斐波那契数列问题的解决方法。
  C++ 参考手册
  

💯题目描述

B2064 斐波那契数列

题目要求是计算斐波那契数列的第 $a$ 项。数列的定义如下：

• 第一项和第二项均为 1：
  $$F(1)=1,F(2)=1$$
• 第 $n$ 项满足递推关系：
  $$F(n)=F(n-1)+F(n-2)\text{(n ≥ 3)}$$

题目的输入输出格式如下：

输入格式

• 第 1 行：测试数据的组数 $n$。
• 接下来 $n$ 行，每行包含一个正整数 $a$，表示要求出斐波那契数列的第 $a$ 项（$1\le a\le 30$）。

输出格式

• 输出 $n$ 行，每行对应一个输入 $a$ 的结果。

输入输出样例

输入

4
5
10
30
1

输出

5
55
832040
1

💯思路分析

题目本质

斐波那契数列是一个经典的递推问题，通过递推公式 $F(n)=F(n-1)+F(n-2)$ 可以不断计算出后续的项。对于这一问题，我们需要重点解决以下几点：

1. 如何高效计算第 $a$ 项？

   • 如果直接计算每个 $a$，复杂度较高，尤其是当 $n$ 和 $a$ 较大时，会有很多重复计算。
   • 如果提前计算好数列的所有值，后续直接查表，则可以显著优化。

2. 如何处理边界情况？

   • 当 $a=1$ 或 $a=2$ 时，不需要递推，直接输出 1。

3. 代码的简洁性与可读性

   • 变量的命名是否语义化，代码逻辑是否清晰。

💯代码实现与对比

以下我们对两种代码方案进行分析，一个是学生（你）的代码实现，另一个是老师提供的参考实现。

我的代码实现

代码展示

#include <iostream>
using namespace std;

int main() {
    int n;  // 测试数据组数
    cin >> n;

    while (n--) {  // 循环处理每组测试数据
        int a;
        cin >> a;

        // 边界情况
        if (a == 1 || a == 2) {
            cout << 1 << endl;
            continue;  // 直接输出后处理下一组测试数据
        }

        // 使用循环计算第 a 项
        int prev1 = 1, prev2 = 1;  // 前两项的值
        int current;  // 当前项的值
        for (int i = 3; i <= a; ++i) {  // 从第3项开始递推
            current = prev1 + prev2;  // 当前项等于前两项之和
            prev1 = prev2;  // 更新前两项的值
            prev2 = current;
        }

        cout << current << endl;  // 输出结果
    }

    return 0;
}

思路解析

1. 边界条件处理：
   • 当 $a=1$ 或 $a=2$ 时，直接输出结果 1，无需循环计算。
2. 递推计算：
   • 从 $F(3)$ 开始循环，通过变量 prev1 和 prev2 保存前两项的值，计算当前项。
3. 变量使用：
   • prev1 和 prev2 分别保存前两项，current 保存当前项。

优点

• 代码逻辑清晰，结构化程度高，适合扩展。
• 边界情况单独处理，减少不必要的计算。

不足

• 对每个输入 $a$ 都需要从头计算，重复计算较多，效率不高。
• 存在可以进一步优化的空间，例如使用查表法。

老师的代码实现

代码展示

#include <iostream>
using namespace std;

int main() {
    int n = 0;
    int a = 0;
    cin >> n;

    while (n--) {
        cin >> a;

        // 计算第 a 个斐波那契数
        int x = 1;
        int y = 1;
        int z = 1;
        while (a > 2) {
            z = x + y;
            x = y;
            y = z;
            a--;
        }

        cout << z << endl;
    }

    return 0;
}

思路解析

1. 变量初始化：
   • 定义了 x, y, 和 z 三个变量，分别表示前两项和当前项的值，初始值均为 1。
2. 递推逻辑：
   • 通过 while 循环，当 $a>2$ 时，不断更新 x、y 和 z 的值。
   • 每次循环结束后，z 表示当前的第 $a$ 项。
3. 边界条件：
   • 初始值的设置（均为 1）使得当 $a=1$ 或 $a=2$ 时，无需特殊处理。

优点

• 代码紧凑简洁，没有显式的边界条件分支。
• 循环逻辑简单直观。

不足

• 和你的代码一样，没有解决重复计算的问题。
• while 循环的使用虽然简化了逻辑，但对于大范围递推不如 for 循环明确。

💯优化方法

对于这类小范围的斐波那契问题，可以通过 查表法 显著优化计算效率。

优化方案：查表法

由于题目中 $a$ 的范围固定（$1\le a\le 30$），我们可以提前计算好斐波那契数列的前 30 项，存入数组中。这样对于每个输入 $a$，只需直接查表输出即可。

优化代码

#include <iostream>
using namespace std;

int main() {
    // 预处理：计算斐波那契数列的前30项
    int fib[31];
    fib[1] = 1;
    fib[2] = 1;
    for (int i = 3; i <= 30; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    int n;
    cin >> n;  // 输入测试组数

    while (n--) {
        int a;
        cin >> a;
        cout << fib[a] << endl;  // 查表输出
    }

    return 0;
}

优化分析

1. 时间复杂度

   • 预处理：计算前 30 项的复杂度为 $O(30)$。
   • 查询：每个输入直接查表，复杂度为 $O(1)$。
   • 总复杂度为 $O(30+n)$，相较于直接递推的 $O(n\cdot a_{\text{max}})$ 大大降低。

2. 空间复杂度

   • 需要额外的数组存储 30 项结果，但空间开销可以忽略不计。

3. 优点

   • 避免了重复计算，运行效率显著提升。
   • 代码结构更简洁，易于维护。

💯扩展与总结

斐波那契数列的优化方法

1. 矩阵快速幂

   • 斐波那契数列的递推可以转化为矩阵乘法，通过矩阵快速幂将时间复杂度降为 $O(\log n)$。

2. 递归优化

   • 使用记忆化递归（Memoization）缓存中间结果，避免重复计算。

💯 小结

• 题目解析：通过递推关系，明确了斐波那契数列的本质和边界条件。
• 代码实现：比较了两种代码方案，分别分析了它们的优缺点。
• 优化方法：通过查表法优化，解决了重复计算的问题，提高了效率。
• 扩展思路：探讨了更高效的算法实现方式。

通过本次题目的解析，相信读者对斐波那契数列的计算和优化有了更深入的理解。在实际问题中，选择合适的算法与优化方法，能够显著提升代码的性能与可维护性。