前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第二讲：递推【例题】
本篇博客所包含习题有：
👊简单斐波那契
👊费解的开关
递推【习题】详见博客：蓝桥杯第二讲–递推【习题】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
简单斐波那契
题目要求
题目描述：
以下数列 0 1 1 2 3 5 8 13 21 ... 被称为斐波纳契数列。
这个数列从第 3 项开始，每一项都等于前两项之和。
输入一个整数 N，请你输出这个序列的前 N 项。
输入格式：
一个整数 N。
输出格式：
在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。
数据范围：
0 < N < 46
输入样例：
5
输出样例：
0 1 1 2 3
思路分析
所谓递推其实就是递归的逆运算，递归是倒着去思考问题，比如我们计算斐波那契数列，递归的思想是，我们想要算出 f[n]，我们需要先知道 f[n - 1], f[n - 2]，如此递归到 f[1] 和 f[2]，递推的思维就是正向去推导问题，即我们知道 f[1], f[2]，我们可以得到 f[3]，进而得到 f[4]，最终叠加可以得到 f[n].
代码
#include <iostream> #include <algorithm> using namespace std; const int N = 50; int f[N]; int main() { int n; cin >> n; f[1] = 0, f[2] = 1; for (int i = 3; i <= n; i ++ ) f[i] = f[i - 1] + f[i - 2]; for (int i = 1; i <= n; i ++ ) cout << f[i] << ' '; return 0; }
对上述代码我们可以对其简单的进行优化，我们发现，在我们计算 f[i] 的时候，只会用到 f[i - 1] 和 f[i - 2]，故我们完全没必要把所有的 f[n] 都给存储下来，只需要存储两个值即可，边循环边输出，这也是所谓 动态数组 的思想：
#include <iostream> #include <algorithm> using namespace std; int main() { int n; cin >> n; int a = 0, b = 1; for (int i = 1; i <= n; i ++ ) { cout << a << ' '; int fn = a + b; a = b, b = fn; } return 0; }
费解的开关
题目要求
题目描述：
你玩过“拉灯”游戏吗？
25 盏灯排成一个 5×5 的方形。
每一个灯都有一个开关，游戏者可以改变它的状态。
每一步，游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。
下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。
输入格式：
第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。
以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式：
一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 −1。
数据范围：
0 < n ≤ 500
输入样例：
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
输出样例：
3
2
-1
思路分析
本题综合难度较高，先讲解几个常用知识点：位运算；偏移量的定义：int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 1, 0, -1, 0};，我们用如上代码去巧妙的计算偏移量：
然后来介绍如何思考这个题目：显然，对于每一个格子我们都最多只会按下它一次，因为按下两次和没有按下的效果是一致的且我们要求步数最少，我们假设第一行已经按完了，接下来我们去按第二行，因为我们要求所有的灯都必须最后是亮着的，故现在能够影响到第一行的只有第二行，且是一一对应关系的，比如我们的第一行第三列的灯在操作完第一行之后是灭着的，我们要把它点亮，那么我们必须按下第二行第三列的灯，因为只有这个灯才会影响到第一行第三列的灯，所以，在我们第一行已经确定的情况下，我们的按法是唯一固定的，即：本题的按法由第一行的按法所唯一决定，然后我们来讨论第一行的按法，第一行的按法我们可以暴力去枚举，第一行有五盏灯，每盏灯无外乎只有两种操作摆在我们面前：按或者不按。我们用二进制的思路去构造它：0 是不按，1 是按，故我们第一行的五盏灯的按或不按的情况就可以构成一个五位的 01 串，我们把它想象为一个二进制串，这个二进制的范围就为：0 ~ 20 + 21 + 22 + 23 + 24 = 31，故我们执行 for 循环：for (int i = 0; i < 32; i ++ )，然后按照二进制的方式去判断是否操作：if (i >> j & 1)，注意，因为我们对于一个表格对应 32 次操作，每次操作都会改变原表格，故我们需要用一个 backup 操作存储 g，每次在 backup 上操作。最终判断操作是否合法：因为操作第二行可以使得第一行的灯都是亮着的，操作第三行可以使得第二行的灯都是亮着的，操作第四行可以使得第三行的灯都是亮着的，操作第五行的灯可以使得第四行的灯都是亮着的，即我们在操作完第五行之后，前四行的灯必然都是亮着的，故我们只需要枚举第五行的灯，看看是否为全部亮着的，全部亮即操作合法，更新一下步数的最小值，否则操作不合法，进行下一种操作的判断。
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 6; int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 1, 0, -1, 0}; char g[N][N], backup[N][N]; void turn(int x, int y) { for (int i = 0; i < 5; i ++ ) { int a = x + dx[i], b = y + dy[i]; if (a < 0 || a > 4 || b < 0 || b > 4) continue; if (backup[a][b] == '0') backup[a][b] = '1'; else backup[a][b] = '0'; } } int main() { int n; cin >> n; while (n -- ) { for (int i = 0; i < 5; i ++ ) // 读入字符串 cin >> g[i]; int res = 7; // res的最大值为6,记录的是每种情况的最小值 // 第一行要暴力枚举每一种情况 // 对于每个灯都有按或者不按的选择,我们用1去表示按,0表示不按 for (int i = 0; i < 32; i ++ ) { memcpy(backup, g, sizeof g); // 把g备份一份给backup int step = 0; // 记录的是当前按法的最终按的次数 for (int j = 0; j < 5; j ++ ) // 暴力枚举 if (i >> j & 1) // 是1就按下 { step ++; turn(0, 4 - j); // 按下操作 } // 开始按照第一行的按法枚举2,3,4,5行 for (int j = 1; j < 5; j ++ ) for (int k = 0; k < 5; k ++ ) if (backup[j - 1][k] == '0')// 上一行灯是灭的,就点亮这行 { step ++; turn(j, k); // 按下操作 } bool flag = false; // 枚举最后一行灯的亮灭情况判断操作是否合法 for (int j = 0; j < 5; j ++ ) if (backup[4][j] == '0') // 如果还有没有灭的灯,操作不合法 { flag = true; break; } if (!flag) // 全部的灯都是亮着的 res = min(res, step); } if (res > 6) res = -1; cout << res << endl; } return 0; }
