递推与递归

1. 算法分析

1.1 递推

    递推强调当前状态与前一个状态的关系,一种考察类似动态规划的思维处理,另一种考察思维:当前状态确定后,后继的所有状态全部确定。

1.2 递归

    递归的处理思路就算当前状态取决于子状态的情况,求当前状态需要先计算出子状态后才能决定。

2. 例题

2.1 递推

2.1.1 思维递推

acwing95费解的开关
题意: 25盏灯排成一个5x5的方形。每一个灯都有一个开关,游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。用数字“1”表示一盏开着的灯,用数字“0”表示关着的灯。给定n次游戏的初始状态,编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。(sum_{}n) <= 500
题解: 通过分析可以知道当前行的状态取决于下一行的按灯方式,而下一行的按灯方式却决于当前行的状态。也就是说一旦当前行的状态确定了,下一行怎么按灯也决定了,往后递推,那么所有灯的状态也决定了。因此,只需要遍历第一行可能出现的情况,然后就可以发现所有的状态,然后判断第5行是否全为1即可。
代码:

#include <bits/stdc++.h>

using namespace std;

int dx[] = {0, -1, 0, 1, 0}, dy[] = {0, 0, 1, 0, -1};
int n;
char g[10][10], backup[10][10];

// 模拟按键
void turn (int x, int y ) {
    for (int i = 0; i < 5; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
        g[nx][ny] ^= 1;
    }
    return;
}

int main() {
    cin >> n;
    while (n--) {
        for (int i = 0; i < 5; ++i) scanf("%s", g[i]);
        int ans = 100000;
        for (int op = 0; op < 32; ++op) {  // 遍历第一行的按灯状态
            memcpy(backup, g, sizeof g);
            int step = 0;
            for (int i = 0; i < 5; ++i) if (op >> i & 1) turn(0, i), step++;  // 按下第一行的灯
            
            for (int i = 0; i < 4; ++i) {  // 遍历整个矩阵,如果当前行的第j个位置为0,那么按下下一行的对应位置
                for (int j = 0; j < 5; ++j) {
                    if (g[i][j] == '0') turn(i + 1, j), step++;
                }
            }
            
            // 判断最后一行是否全为1
            bool is_success = true;
            for (int i = 0; i < 5; ++i) 
                if (g[4][i] == '0') {
                    is_success = false;
                    break;
                }
            
            // 全为1,则更新答案
            if (is_success) ans = min(ans, step);
            memcpy(g, backup, sizeof backup);
        }
        if (ans <= 6) cout << ans << endl;
        else cout << -1 << endl;
    }
    return 0;
}

Codeforces Round #658 (Div. 2) B. Sequential Nim
题意: 两个人玩博弈论游戏,有许多堆石头,每堆石头的数目都大于等于1,每次只能从第一堆石头取,可以取任意个正整数的石头,一旦不能取石头那么就输了。一开始第一个人先取,如果第一个人最后能赢,输出First;如果第二个人最后能赢,输出Second。(sum_{}n) <= 10^5^
题解: 如果当前石头数大于1,那么当前这个人可以选择是否交换先后手;如果当前石头数位1,那么当前这个人必须交换先后手。因此,一旦出现第一个大于n的石头数目,当前这个人就可以根据后面的石头数,找到最优策略,然后取胜(当前如果是k>1,那么可以根据后面的石头确定一种获胜状态),因此只需要计算出现第一个大于1的石头前面1的个数,如果是奇数,那么Second,否则First(奇数说明到Second拿这堆石头);如果全为1,那么奇数个1输出First,否则Second(奇数说明一直交换先后手,然后又回到First)
代码

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 10;
int T, a[N];
int n;

int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        int k = 1, cnt = 0;
        while (a[k] == 1 && k <= n) cnt++, k++;
        if (cnt == n) cout << (cnt & 1? "First": "Second") << endl;
        else cout << (cnt & 1? "Second": "First") << endl;
    }
    return 0;
}

2.2.4 思维最小步数

acwing1208. 翻硬币
题意: 一开始给定两个字符串a和b,字符串由'*'和'o'组成。每次变化可以将相邻的两个字符同时变化(*->0, 0->*),问最少多少次变化可以将a变成b?字符串a、b的长度均小于等于100.
题解: 题目咋一看是最小步数模型,但是n能到达100,bfs最小步数必然超时。考虑每次变化的关系:每次变化将相邻的两个字符反转,相当于异或操作。对于异或操作来说,异或奇数次可以规约到1次,异或偶数次可以规约到0次,同时异或没有先后顺序之分。因此,对于所有的变化来说,相当于有n个开关,每个开关控制a[i]和a[i+1]。每个开关只有按和不按两种情况,要求最小的步数,只需要奇数次都规约到1次,偶数次都规约到0次,然后按下的开关是必须的即可。因此,从前往后扫描,如果a[i]!=b[i],那么需要按下开关i,然后把a[i]和a[i+1]反转,这样每次按下都是必须的,也就是最少的步数。
代码:

#include <bits/stdc++.h>

using namespace std;

string s, e;

void turn(int x) {
    if (s[x] == '*') s[x] = 'o';
    else s[x] = '*';
}

int main() {
    cin >> s >> e;
    int res = 0;
    for (int i = 0; i < s.size() - 1; ++i) {
        if (s[i] != e[i]) res++, turn(i), turn(i + 1);
    }
    cout << res << endl;
    return 0;
}

2.1.2 dp类递推

2.2 递归

acwing 92递归实现指数型枚举
题意: 从 1 ~ n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。1 ≤ n ≤ 15
题解: n只有15,使用二进制表示每个数字是否被选即可
代码:

#include <bits/stdc++.h>

using namespace std;

int n;

void dfs(int cur, int num) {
    if (cur == n) {
        for (int i = 0; i < n; ++i) {
            if (num & (1 << i)) cout << i + 1 << " ";
        }
        cout << endl;
        return;
    }
    dfs(cur + 1, num << 1);
    dfs(cur + 1, num << 1 | 1);
    return;
}

int main() {
    cin >> n;
    dfs(0, 0);
    return 0;
}
内容来源于网络如有侵权请私信删除