前言

藍橋杯官網：藍橋杯大賽——全國大學生TMT行業賽事
?本博客講解 藍橋杯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 ~ 2⁰ + 2¹ + 2² + 2³ + 2⁴ = 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;
}