本篇简介：
本篇文章带你利用巧法解答洛谷的斐波那契数组问题，细节深入，满满干货。

一·斐波那契数列和斐波那契数组：
1.1斐波那契数列：
1.1.1定义：

斐波那契数列是一个经典的整数数列，通常用f(n)表示：

1.1.2数列的前几项数值：

按照上述定义，斐波那契数列的前几项依次为：0 1 1 2 3 5 8 ..... 。随着项数的增加，数字增长的速度逐渐加快，且呈现出一种独特的规律，即每个数都是前两个数之和。

1.1.3数学特性：

1.1.4算法实现（动态规划）：

include

include

using namespace std;

// 迭代函数计算斐波那契数列的第 n 项并存储在数组中
vector fibonacci_array(int n) {
vector fib(n + 1);
if (n >= 0) fib[0] = 0;
if (n >= 1) fib[1] = 1;
for (int i = 2; i <= n; ++i) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib;
}

int main() {
int n = 10; // 要计算的斐波那契数列的项数
vector result = fibonacci_array(n);
for (int num : result) {
cout << num << " ";
}
cout << endl;
return 0;
}

1.2斐波那契数组：
1.2.1定义与概念：

斐波那契数组是与斐波那契数列相关的数组结构。最常见的情况是将斐波那契数列的元素存储在一个数组中，以便于对这些元素进行访问、操作和分析。

1.2.2应用场景：
数据的查询和储存：在某些情况下，需要频繁地访问斐波那契数列中的特定项。将数列存储为数组后，可以通过数组的索引快速获取相应的值，时间复杂度为o(N) 。例如，在一个数学计算程序中，如果需要多次使用斐波那契数列的前 100 项进行不同的运算，将这些项存储在数组中可以大大提高计算效率，避免了每次都重新计算数列的值。
算法实现辅助：在一些复杂的算法中，斐波那契数组可以作为中间数据结构来辅助实现。例如，在解决某些动态规划问题时，可能需要根据斐波那契数列的规律来构建状态转移方程，此时使用斐波那契数组可以方便地获取数列中的值，简化算法的实现过程。又如，在图形绘制算法中，如果要绘制具有斐波那契螺旋性质的图形，使用斐波那契数组来确定螺旋线上的点的坐标，可以更加高效地实现图形的绘制，并且保证图形的准确性和美观性。
数据分析与统计：对于一些与斐波那契数列相关的数据分析任务，将数列存储为数组形式可以方便地进行数据的统计和分析。例如，研究斐波那契数列的分布特性、相邻项之间的关系变化等，通过对数组中的数据进行遍历和计算，可以得到各种统计信息，帮助深入了解斐波那契数列的数学性质和潜在规律，为进一步的理论研究提供数据支持。
上面的科普大家选看即可，下面就是解题重点了。

二·题目叙述：

测试用例：

输入：

5
1 2 2 4 8

输出：3

洛谷链接：[蓝桥杯 2022 国 C] 斐波那契数组 - 洛谷

三·思路简述：
首先，这道题，我们一看肯定是想把斐波那契数列都列举都来与它一一比较，但是我们下面一看数据范围：

此刻我们就想到了，我们可以只用列举到斐波那契数列值小于1e6即可；然后后面的就根据n的值来确定；当看到了n的范围就会发现可能会越界；如果超了1e6后面的值就一定要修改了。

下面请看图：

然后下面的思路就是，我们根据这点先填充标准斐波那契数组然后拿原数组与它比较即可。

然而，这样真的可以吗？ 我们就试试：

如果是这样，下面我们在找斐波那契数列的开始大于1e6的那项下标用flag标记一下，方便后面如果原数组的容量大于这个下标好统计后面要修改多少个。

for (int i = 1; i <= min(flag, n); i++) tmp += !(y[i] == f[i]);//统计未超过之前的
tmp += n - flag >= 0 ? n - flag : 0;//统计如果超了后面都要修改的多少个
这样我们就写出代码了，然后就迫不及待提交了：

include

using namespace std;
int y[100005]; int n; int f[100]; int flag; int tmp = 0;
int main() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> y[i];

    f[1] = f[2] = 1;
    for (int j = 3; j <= 31; j++) {
        if (f[j - 1] + f[j - 2] > 1e6) {
            flag = j;
            break;
        }
        f[j] = f[j - 1] + f[j - 2];
    }

    for (int i = 1; i <= min(flag, n); i++) tmp += !(y[i] == f[i]);
    tmp += n - flag >= 0 ? n - flag : 0;
cout << tmp << endl;
return 0;

}

但是兴高采烈后便发现了：

仅仅只有70分；于是想了半天；再此仔细去读读题便发现了：

它的规定好像和真正的斐波那契数列不太一样；斐波那契是从1开始的；而它可以从1~1e6；只需要满足前两个相同后面遵循斐波那契数列规律就好了；当然后面的最少修改也暗示了这点：比如：

原数组：4 4 8；但是我们如果按照之前的首项从1开始的斐波那契数列算是三次；但是真正它是0次；就是首项从4开始；故我们再套一层for循环，然后每次构建不同的斐波那契与原数组比较获得的次数取个min就好了；但是注意每次求的当前次数，下一次进行之前注意清除。

最后就也是通过了。

四·解答代码：

include

using namespace std;
//规律题：可以发现数组数据范围最大是1e6；而从1开始的斐波那契第31项才
//大于1e6；也就是说我们去拿原数组和斐波那契去一一比较，不同就改，这里的
//优化就是当斐波那契31项开始就不用列举了；因为真正值超过了数组最大值；
//也就是在这之后一定会修改。
//其次就是，这里所谓的斐波那契数组某种意义上包含了更广的斐波那契数列
//(从1开始)；而斐波那契数组的定义是首项可以从1~1e6开始--->要套一层for
int y[100005]; int n; int f[100]; int flag; int ret = INT_MAX; int tmp = 0;
int main() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> y[i];
for (int i = 1; i <= 1e6; i++) {
f[1] = f[2] = i;//构建斐波那契数组（首项不同）
for (int j = 3; j <= 31; j++) {
if (f[j - 1] + f[j - 2] > 1e6) {
flag = j;//找到某项大于1e6标记，构建好的特殊的斐波那契
break;
}
f[j] = f[j - 1] + f[j - 2];
}
//这里的比较判断：拿原数组和标准斐波比较；这里根据具体的原数组
//长度决定；如果原数组少就拿它遍历，如果多了就截止到对应的形成的斐波那契的
//前31项截止
for (int i = 1; i <= min(flag, n); i++) tmp += !(y[i] == f[i]);
tmp += n - flag >= 0 ? n - flag : 0;//如果超了直接必须修改
ret = min(ret, tmp);//每种方案的最小值
tmp = 0;
}
cout << ret << endl;
return 0;
}

五·本篇小结：
根据本题，发现大多数看似直接暴破解的解答方法大概率是行不通的，当然关键还是仔细看数据范围，以及题目的细节分析，可能会出现有周期性：这样就只需要求一个周期内就可以了，或者是根据数据范围推导结果范围落得具体范围，然后只用在这个范围思考就ok了。

本篇分享结束，感谢大家阅读！！！

                           风劲潮涌，自当扬帆起航，任重道远，更需策马加鞭。