P8808 [蓝桥杯 2022 国 C] 斐波那契数组

Hello大家好，我是小亦，今天一大早就来更东西了嘿嘿，不知道现在大家有没有回老家的或去玩的，那有没有扎在家的，呜呜呜我就是宅在家的QWQ，唉没办法啊，好那么好不了这些了qwq，今天我来讲的题目是来自蓝桥杯2022年 国C题目也就是第三道题，名叫:斐波那契数组，其实这道题呢，嗯比较的难所以呢我也来特意的来讲一下这道题，话不多说看思路~：

我们先来看一下问题的描述：

给定一个数组 A=(a0,a1,…,an−1)，需要通过最少的修改次数将其转换成一个斐波那契数组。斐波那契数组满足以下条件：

1. 数组长度 n>2。
2. a0=a1​。
3. 对于所有的 i≥2，有 ai=ai−1+ai−2。

我们再来看看解题思路qwq:

1. 理解斐波那契数组：斐波那契数组的特点是，除了前两个元素外，每个元素都是前两个元素的和。这意味着一旦确定了前两个元素的值，整个数组的值就被确定了。

2. 固定前两个元素：由于斐波那契数组的第一个和第二个元素必须相等，我们可以固定这两个元素的值，然后计算出整个斐波那契数组。

3. 计算修改次数：对于每个可能的前两个元素的值，我们计算出整个斐波那契数组，然后与原数组进行比较，计算出需要修改的元素数量。

4. 找到最小修改次数：我们遍历所有可能的前两个元素的值，找到需要修改的最小元素数量。

看看算法步骤

1. 初始化最小修改次数：将最小修改次数初始化为一个非常大的数，以便后续更新。

2. 遍历所有可能的前两个元素的值：

   • 对于第一个元素 a0​，遍历从1到 A[0] 的所有可能值。
   • 对于第二个元素 a1​，遍历从1到 A[1] 的所有可能值。

3. 计算修改次数：

   • 对于每一对 (a0,a1)，如果 a0≠A[0]a0​=A[0] 或 a1≠A[1]a1​=A[1]，则需要修改前两个元素，因此修改次数至少为1或2。
   • 从数组的第三个元素开始，计算出基于a0​ 和 a1​ 的斐波那契数列，并与原数组进行比较，计算出需要修改的元素数量。

4. 更新最小修改次数：

   • 对于每一对 (a0,a1)，计算出的修改次数与当前的最小修改次数进行比较，取较小值作为新的最小修改次数。

5. 返回结果：

   • 在遍历完所有可能的 (a0​,a1​) 组合后，返回计算出的最小修改次数。

必须要看的注意事项

• 边界条件：如果数组长度小于3，则不需要修改，直接返回0。
• 正整数限制：斐波那契数组的元素必须是正整数，因此在遍历时，a0​ 和 a1​ 的值应该从1开始。

通过这种方法，我们可以找到将给定数组转换为斐波那契数组所需的最小修改次数，嗯思路已经给大家了，代码呢我就拿出来吧，但是我要提醒大家，每过一天我就来查看每一道题有没有类似我的代码或直接照搬，作者本人是会举报的，所以抄代码可耻，仅供参考

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

int minChangesToFibonacci(const vector<int>& A) {
    int n = A.size();
    if (n < 3) return 0; // 数组长度小于3，不需要修改

    int minChanges = INT_MAX;
    // 枚举a0和a1的所有可能值
    for (int a0 = 1; a0 <= A[0]; ++a0) {
        for (int a1 = 1; a1 <= A[1]; ++a1) {
            if (a0 != a1) continue; // a0和a1必须相等
            int changes = 0;
            int fib0 = a0, fib1 = a1;
            for (int i = 2; i < n; ++i) {
                int nextFib = fib0 + fib1;
                if (A[i] != nextFib) {
                    changes++;
                }
                fib0 = fib1;
                fib1 = nextFib;
            }
            minChanges = min(minChanges, changes + (a0 != A[0]) + (a1 != A[1]));
        }
    }
    return minChanges;
}

int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }

    cout << minChangesToFibonacci(A) << endl;
    return 0;
}

本人的注释也标了方便理解，所以放心食用~