0.1 基本算法--递推与递归

2118字约7分钟

2024-11-06

《算法竞赛进阶指南/李煜东》0x00 章节基本算法——递推与递归。

本节知识点：递推与递归宏观描述、简单应用、分治、分形、递归的机器实现。

递推与递归

一个实际问题的各种可能情况构成的集合通常称为“状态空间”，而程序的运行则是对于状态空间的遍历，算法和数据结构则通过划分、归纳、提取、抽象来帮助提高程序遍历状态空间的效率。递推和递归就是程序遍历状态空间的两种基本方式。

递推与递归的宏观描述

对于一个待求解的问题，当它处于某处边界、某个小范围或者某种特殊情形下时，其答案往往是已知的。如果能够将该解答的应用场景扩大到原问题的状态空间，且扩展过程的每个步骤具有相似性，就可以考虑使用递推或递归求解。

从已知的边界为起点向原问题正向推导的扩展方式就是递推。然而很多时候递推的路线难以确定，这时候以原问题为起点尝试寻找把状态空间缩小到已知的问题边界的路线，再通过该路线反向回溯的遍历方式就是递归。

缩小问题状态空间的规模。这意味着程序尝试寻找在“原问题”与“问题边界”之间的变换路线，并向正在探索的路线上迈出一步。
尝试求解规模缩小以后的问题，结果可能是成功，也可能是失败。
如果成功，即找到了规模缩小后的问题的答案，那么将答案扩展到当前问题。如果失败，那么重新回到当前问题，程序可能会继续寻找当前问题的其他变换路线，直至最终确定当前问题无法求解。

在以上三个操作中有两点颇为关键一是“如何尝试求解规模缩小以后的问题”。因为规模缩小以后的问题是原问题的一个子问题，所以我们可以把它视为一个新的“原问题”由相同的程序（上述三个操作）进行求解，这就是所谓的“自身调用自身”。二是如果求解子问题失败，程序需要重新回到当前问题去寻找其他的变换路线，因此把当前问题缩小为子问题时所做的对当前问题状态产生影响的事情应该全部失效，这就是所谓的“回溯时还原现场”。

递推与递归的简单应用

使用枚举算法暴力遍历整个状态空间时通常需要递归。按照规模大小，有如下集中常见的枚举形式和遍历方式：

枚举形式	状态空间规模	一般遍历方式
多项式	$n^k$ ， $k$ 为常数	for 循环、递推
指数	$k^n$ ， $k$ 为常数	递归、位运算
排列	$n!$	递归、next_permutation
组合	$C^m_n$	递归+剪枝

递归实现指数型枚举

递归实现指数型枚举^[1]：从 $1\text{～}n$ 这 $n(n<20)$ 个整数中随机选取任意多个，输出所有可能的选择方案。

这等价于每个整数可以选或者不选，即在每次递归若选择则将选择的整数放入数组中，然后求解子问题。

#include <iostream>
#include <vector>

std::vector<int> temp;
void chose(int n, int i) {
    if (i > n) {
        for (auto num: temp) {
            std::cout << num << ' ';
        }
        std::cout << std::endl;
        return;
    }
    // not chose.
    chose(n, i+1);
    // chose.
    temp.emplace_back(i);
    chose(n, i+1);
    temp.pop_back();
}

int main() {
    int n;
    std::cin >> n;
    chose(n, 1);
}

递归实现组合型枚举

AcWing'93^[2]

组合型即边界为“已经选满了”或者“剩余的不够选满”。

注意要求字典序，所以小的需要先选。

#include <iostream>
#include <vector>

std::vector<int> temp;

void chose(int n, int m, int i) {
    if (temp.size() == m) {
        for (auto val: temp) std::cout << val << ' ';
        std::cout << std::endl;
        return;
    }
    if (i > n || (n-i+1) + temp.size() < m) {
        // 不能选 或 不够选，其实只要后者就行了
        return;
    }
    // chose. 字典序排序，小的先选
    temp.emplace_back(i);
    chose(n, m, i+1);
    temp.pop_back();
    // not chose.
    chose(n, m, i+1);
}

int main() {
    int n, m;
    std::cin >> n >> m;
    chose(n, m, 1);
}

递归实现排列型枚举

递归实现排列型枚举^[3]：把 $\text{～}$ 这 $n(n<10)$ 个整数排成一排后随机打乱顺序，输出所有可能的次序。

这道题的问题是，选 n 次 1-n 的数，选了不能再选，子问题就是选第几个数。

#include <iostream>
#include <vector>

std::vector<bool> chosen(10);
std::vector<int> temp;
void chose(int n, int i) {
    if (i > n) {
        for (auto val: temp) std::cout << val << ' ';
        std::cout << std::endl;
        return;
    }
    for (int j = 1; j <= n; ++j) {
        if (!chosen[j]) {
            chosen[j] = true;
            temp.emplace_back(j);
            chose(n, i+1);
            temp.pop_back();
            chosen[j] = false;
        }
    }
}

int main() {
    int n;
    std::cin >> n;
    chose(n, 1);
}

费解的开关

费解的开关^[4]：在一个 5*5 的 01 矩阵中，点击任意一个位置，该位置以及它上、下、左、右四个相邻的的位置的数字都会发生翻转。问：最少需要多少次点击可以把一个给定的 01 矩阵变成全 0 矩阵？

最少翻转多少次，因为翻转 2 次等于没翻转，所以每个位置要么翻转，要么不翻转。这道题的状态空间实则是第一行的开关情况，如果第一行确定了开关，那么需要第二行的开关才能决定全 1，所以第二行也确定了，依次类推。

注意这里用一个位图表示初始 light，一个位图表示开关情况 turn_on，

如果是本层的那么 light 经过 turn_on 后的位图则是 $(\text{light} \oplus (\text{turn\_on}) \oplus (\text{turn\_on}>>1) \oplus (\text{turn\_on}<<1))\&\text{0x5f}$
如果是上层影响则是 $\text{light} \oplus \text{turn\_on}$
根据本层灯光情况决定下一层开关情况为 $\text{～}\text{light}$ ，即如果是 1 则不需要开灯，如果是 0 则需要开灯。
利用 low_bit 计算位图中 1 的个数。

#include <cstring>
#include <cstdio>
#include <iostream>
#include <tuple>
#include <vector>

int count_one(int val) {
    int ret = 0;
    while (val) {
        ++ret;
        val -= val&(-val);
    }
    return ret;
}

inline int this_line_turn_on(int light_line, int turn_on) {
    return (light_line ^ (turn_on) ^ (turn_on << 1) ^ (turn_on >> 1)) & 0x1f;
}

int turn_on(int lights[5]) {
    int turn_on_count = 7;
    for (int turn_on = 0; turn_on < 1<<5; ++turn_on) {
        int temp_count = count_one(turn_on);
        int updated_line = this_line_turn_on(lights[0], turn_on);
        int next_line_turn_on = (~updated_line) & 0x1f;
        int last_turn_on = turn_on;
        for (int i = 1; i < 5; ++i) {
            temp_count += count_one(next_line_turn_on);
            updated_line = this_line_turn_on(lights[i] ^ last_turn_on, next_line_turn_on);
            last_turn_on = next_line_turn_on;
            next_line_turn_on = (~updated_line) & 0x1f;
        }
        if (updated_line != 0x1f) continue;
        turn_on_count = std::min(temp_count, turn_on_count);
    }
    return turn_on_count < 7 ? turn_on_count : -1;
}

inline int str2bits(const char str[5]) {
    int ret = 0;
    for (int i = 0; i < 5; ++i) {
        if (str[i] == '1') ret |= 1<<i;
    }
    return ret;
}

int main() {
    int n;
    scanf("%d\n", &n);
    for (int i = 0; i < n; ++i) {
        int lights[5];
        for (int j = 0; j < 5; ++j) {
            char temp[20]; // 溢出
            scanf("%s\n", temp);
            lights[j] = str2bits(temp);
        }
        std::cout << turn_on(lights) << std::endl;
    }
}

四塔汉诺塔

四塔汉诺塔问题^[5]：解出 $n$ 个盘子 4 座塔的汉诺塔问题至少需要多少步？

首先考虑三塔汉诺塔问题，最小步数为 $d[n]=2d[n-1]+1$ ，即把前 $n-1$ 个盘子从 A 柱移到 B 柱，再将最后一个盘子从 A 柱移到 C 柱，最后把 B 柱的 $n-1$ 个盘子移到 C 柱。

那么扩展到四塔，若 $f(n)$ 表示 4-塔问题的最小值，

那么 $f(n)=\min\set{2*f(i)+d[n-i]}$ 即将面上的 $i$ 个盘子从 A 柱移到 B 柱，剩下的 $n-i$ 个盘子在 A, C, D 形成了三塔汉诺塔问题即 $d[n-i]$ ，最后将 B 柱的 $i$ 个盘子从 B 柱移到 D 柱（四塔）。边界为 $f(1)=1$ 。

#include <cstring>
#include <iostream>

int main() {
    int d[13];
    d[1] = 1;
    for (int i = 2; i <= 12; ++i) {
        d[i] = d[i-1]*2 + 1;
    }
    int f[13];
    memset(f, 0x3f, sizeof(f));
    f[1] = 1;
    for (int i = 2; i <= 12; ++i) {
        for (int j = 1; j < i; ++j) {
            f[i] = std::min(f[i], 2*f[j] + d[i-j]);
        }
    }
    for (int i = 1; i <= 12; ++i) {
        std::cout << f[i] << std::endl;
    }
}

apple

Apple

int

banana

Banana

orange

Orange