递归相关题型

BraumAce2024年7月29日约 2172 字大约 7 分钟

递归相关题型

1. 92. 递归实现指数型枚举

题目描述

从 $1 \sim n$ 这 $n$ 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 $n$ 。

输出格式

每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 $1$ 个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

$1 \leqslant n \leqslant 15$

输入样例：

输出样例：

思路

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;

int n;
int st[N];  // 0表示还没考虑，1表示已选，2表示未选

void dfs(int u)
{
    if (u == n) 
    {
        for (int i = 0; i < n; i++)
            if (st[i] == 1)
                cout << i + 1 << ' ';
        cout << endl;
        return;
    }
    
    st[u] = 2;
    dfs(u + 1);
    st[u] = 0;
    
    st[u] = 1;
    dfs(u + 1);
    st[u] = 0;
}

int main()
{
    cin >> n;
    
    dfs(0);
    
    return 0;
}

2. 94. 递归实现排列型枚举

题目描述

把 $1 \sim n$ 这 $n$ 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数 $n$ 。

输出格式

按照从小到大的顺序输出所有方案，每行 $1$ 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

$1 \leqslant n \leqslant 9$

输入样例：

输出样例：

思路

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;

int n;
int st[N];    // 0表示还没放数，1~n表示放的哪些数
bool vis[N];  // 标记是否使用过

void dfs(int u)
{
    if (u > n)
    {
        for (int i = 1; i <= n; i++)  // 输出方案
            cout << st[i] << ' ';
        puts("");
        
        return;
    }
    
    // 依次枚举每个分支，即当前位置能填哪些数
    for (int i = 1; i <= n; i++){
        if (!vis[i]){
            st[u] = i;
            vis[i] = true;
            dfs(u + 1);
            
            // 恢复现场
            st[u] = 0;
            vis[i] = false;
        }
    }
}

int main()
{
    cin >> n;
    
    dfs(1);
    
    return 0;
}

3. 93. 递归实现组合型枚举

题目描述

从 $1 \sim n$ 这 $n$ 个整数中随机选出 $m$ 个，输出所有可能的选择方案。

输入格式

两个整数 $n,m$ ，在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行 $1$ 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围

$n > 0$ ,
$0 \leqslant m \leqslant n$ ,
$n+(n−m) \leqslant 25$

输入样例：

5 3

输出样例：

思路

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;

int n, m;
int way[N];

void dfs(int u, int start)  // u表示第几位，i表示从哪个数开始
{
    if (u + n - start < m) return;  // 剪枝，若剩下可选的数字不能填满剩下的空位则回退
    
    if (u > m)
    {
        for (int i = 1; i <= m; i++)
            cout << way[i] << ' ';
        puts("");
        
        return;
    }
    
    for (int i = start; i <= n; i++)  // 从start开始枚举剩下的可选数字
    {
        way[u] = i;
        dfs(u + 1, i + 1);
        way[u] = 0;   // 恢复现场
    }
}

int main()
{
    cin >> n >> m;
    
    dfs(1, 1);
    
    return 0;
}

翰翰和达达饲养了 $N$ 只小猫，这天，小猫们要去爬山。
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为 $W$ ，而 $N$ 只小猫的重量分别是 $C_1$ 、 $C_2 …… C_N$ 。
当然，每辆缆车上的小猫的重量之和不能超过 $W$ 。
每租用一辆缆车，翰翰和达达就要付 $1$ 美元，所以他们想知道，最少需要付多少美元才能把这 $N$ 只小猫都运送下山？

输入格式

第 $1$ 行：包含两个用空格隔开的整数， $N$ 和 $W$ 。
第 $2 \sim N+1$ 行：每行一个整数，其中第 $i+1$ 行的整数表示第 $i$ 只小猫的重量 $C_i$ 。

输出格式

输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。

数据范围

$1 \leqslant N \leqslant 18$ ,
$1 \leqslant C_i \leqslant W \leqslant 10^8$

输入样例：

输出样例：

思路

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;

int n, m;
int c[N];       // 每只猫的重量
int s[N];       // 每辆车所搭载的重量
int res = N;    // 初始最坏情况下一只猫一辆车

void dfs(int u, int k)    // u只猫，k辆车
{
    if (k >= res) return;
    
    if (u == n){
        res = k;
        return;
    }
    
    for (int i = 0; i < k; i++)   // 对每辆车进行枚举
    {
        if (s[i] + c[u] <= m)     // 若不超过最大载重
        {
            s[i] += c[u];
            dfs(u + 1, k);
            s[i] -= c[u];
        }
    }
    
    // 否则需要再加一辆车
    s[k] = c[u];
    dfs(u + 1, k + 1);
    s[k] = 0;
}

int main()
{
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) cin >> c[i];
    
    sort(c, c + n, greater());
    
    dfs(0, 0);    // 0只猫，0辆车
    
    cout << res << endl;
    
    return 0;
}

5. 1209. 带分数

题目描述

$100$ 可以表示为带分数的形式： $100 = 3 + \frac{69258}{714}$

还可以表示为： $100 = 82 + \frac{3546}{197}$

注意特征：带分数中，数字 $1 \sim 9$ 分别出现且只出现一次（不包含 0）。

类似这样的带分数， $100$ 有 $11$ 种表示法。

输入格式

一个正整数。

输出格式

输出输入数字用数码 $1∼9$ 不重复不遗漏地组成带分数表示的全部种数。

数据范围

$1 \leqslant N < 10^6$

输入样例1：

输出样例1：

输入样例2：

输出样例2：

思路

题目意思是说，用 $1 \sim 9$ 的 $9$ 个数，构造成一个整数和一个分数，每个数都要用到且只出现一次，分数不考虑约分的情况。可以理解为，构造成 $n = a + \frac{b}{c}$ 的形式，要求将 $9$ 个数划分给 $a, b, c$ 三个数， $9$ 个数必须不重不漏。

步骤：

枚举全排列
枚举位数， $a, b, c$ 三个数的位数可能都不一样
将 $a, b, c$ 转化为数字，带入等式中看是否成立

将 $n = a + \frac{b}{c}$ 转化为 $cn = ca + b$ ，只需要枚举 $a$ 和 $c$ 即可，最后判断 $b = cn - ca$ 是否成立。从 $a$ 开递递归枚举，每次递归的同时也对 $c$ 枚举，然后每次都 $check(a, c)$ 是否满足条件，若满足则答案 $+1$ 。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;

int n;
bool st[N], backup[N];
int ans;

bool check(int a, int c)
{
    int b = c * n - c * a;
    
    if (!a || !b || !c) return false;
    
    memcpy(backup, st, sizeof st);  // 备份
    
    while (b)
    {
        int x = b % 10;     // 取出b的每一位
        b /= 10;
        
        if (!x || backup[x])    // 判断每一位上的数字是否用过
            return false;       // 用过则不合法
        backup[x] = true;       // 没用过则标记
    }
    
    for (int i = 1; i <= 9; i++)
        if (!backup[i])        // 如果有一位没用上，则不合法
            return false;
    
    return true;
}

void dfs_c(int u, int a, int c)
{
    if (u >= n) return;
    
    // 判断当前a和c是否满足条件，若满足则答案+1
    if (check(a, c)) ans++;
    
    // 继续枚举
    for (int i = 1; i <= 9; i++){
        if (!st[i])
        {
            st[i] = true;
            dfs_c(u + 1, a, c * 10 + i);  // a不变，更新c
            st[i] = false;
        }
    }
}

void dfs_a(int u, int a)
{
    if (u >= n) return;
    
    // 对a提前判断一下，能更快一点点
    if (a) dfs_c(u, a, 0);  // 枚举c：用了几个数，a是几，当前加入的数字是几
    
    for (int i = 1; i <= 9; i++){
        if (!st[i])
        {
            st[i] = true;
            dfs_a(u + 1, a * 10 + i);  // 用的数字个数+1，加入i后更新当前a的值
            st[i] = false;
        }
    }
}

int main()
{
    cin >> n;
    
    dfs_a(0, 0);  // 枚举a：用了几个数，当前的值
    
    cout << ans << endl;
    
    return 0;
}

递归相关题型

递归相关题型

1. 92. 递归实现指数型枚举

2. 94. 递归实现排列型枚举

3. 93. 递归实现组合型枚举

4. 165. 小猫爬山

5. 1209. 带分数