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

在这里插入图片描述

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C++

文章目录

💯前言
💯题目描述
- 输入格式
- 输出格式
- 输入输出样例
- - 输入
  - 输出
💯思路分析
- **题目本质**
💯代码实现与对比
- **我的代码实现**
- - 代码展示
  - 思路解析
  - 优点
  - 不足
- **老师的代码实现**
- - 代码展示
  - 思路解析
  - 优点
  - 不足
💯优化方法
- **优化方案：查表法**
- - 优化代码
  - 优化分析
💯扩展与总结
- **斐波那契数列的优化方法**
💯 **小结**

在这里插入图片描述

💯前言

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

💯题目描述

B2064 斐波那契数列
在这里插入图片描述

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

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

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

输入格式

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

输出格式

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

输入输出样例

输入

输出

💯思路分析

题目本质

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

如何高效计算第 $a$ 项？
- 如果直接计算每个 $a$ ，复杂度较高，尤其是当 $n$ 和 $a$ 较大时，会有很多重复计算。
- 如果提前计算好数列的所有值，后续直接查表，则可以显著优化。
如何处理边界情况？
- 当 $a = 1$ 或 $a = 2$ 时，不需要递推，直接输出 1。
代码的简洁性与可读性
- 变量的命名是否语义化，代码逻辑是否清晰。

💯代码实现与对比

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

我的代码实现

代码展示

#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;
}

在这里插入图片描述

思路解析

边界条件处理：
- 当 $a = 1$ 或 $a = 2$ 时，直接输出结果 1，无需循环计算。
递推计算：
- 从 $F (3)$ 开始循环，通过变量 prev1 和 prev2 保存前两项的值，计算当前项。
变量使用：
- 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;
}

在这里插入图片描述

思路解析

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

优点

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

不足

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

💯优化方法

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

优化方案：查表法

由于题目中 $a$ 的范围固定（ $\leq a \leq 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;
}

在这里插入图片描述

优化分析

时间复杂度
- 预处理：计算前 30 项的复杂度为 $O (30)$ 。
- 查询：每个输入直接查表，复杂度为 $O (1)$ 。
- 总复杂度为 $O (30 + n)$ ，相较于直接递推的 $\cdot a_{\text{max}})$ 大大降低。
空间复杂度
- 需要额外的数组存储 30 项结果，但空间开销可以忽略不计。
优点
- 避免了重复计算，运行效率显著提升。
- 代码结构更简洁，易于维护。