acwing算法基础03-递归,枚举

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

1.排序 考虑顺序
2. 组合 不考虑顺序



参数 -核心

递归 模板 1.指数型 选/不选 2. 排列 -考虑顺序 （判重数组 不知道哪个数有有没有用过）3.组合 不考虑顺序

数据范围 从n个数里选m个数 组合数中间点 取范围

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

const int N = 30;

int n,m;
int way[N];//表示方案

void dfs(int u,int start){
    //1边界考虑 
    if(u==m+1){
    //已经枚举完最后一个数 u =1 没选 u=2选了一个数字
        for(int i=1;i<=m;i++) printf("%d ",way[i]);
        puts("");//回车换行
        return;
    }
    
    for(int i=start;i<=n;i++){
        way[u]=i;//把当前这个数放入way
        dfs(u+1,i+1);//递归到下一层
        way[u]=0;//回复现场
    }
    
}

int main(){
    scanf("%d%d",&n,&m);
    dfs(1,1);//第一个数开始枚举，第一个数从数字1开始枚举
    return 0;
}

优化 剪 （判断）
假如正在选第u个数 说明已经选了u-1个数
后面可以选start 到n 就算把start到n全部悬赏都不够 剪掉

空的个数 <m

提前退出 -减枝

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

const int N = 30;

int n,m;
int way[N];//表示方案

void dfs(int u,int start){
    //减掉不合理情况
    if(u+n-start<m) return;
    //1边界考虑 
    if(u==m+1){
    //已经枚举完最后一个数 u =1 没选 u=2选了一个数字
        for(int i=1;i<=m;i++) printf("%d ",way[i]);
        puts("");//回车换行
        return;
    }
    
    for(int i=start;i<=n;i++){
        way[u]=i;//把当前这个数放入way
        dfs(u+1,i+1);//递归到下一层
        way[u]=0;//回复现场
    }
    
}

int main(){
    scanf("%d%d",&n,&m);
    dfs(1,1);//第一个数开始枚举，第一个数从数字1开始枚举
    return 0;
}

AcWing
1209. 带分数
1.暴力

优化：根据题目本身的性质 刚刚没有用到n的信息 暴力枚举abc 自变量只有两个 除法换成乘法

还有n的范围是有限的 只有6位 a<=n 所以 a最大也只有6位 所以可以判断在枚举的过程中是不是大于n 如果a大于n 也可以退出

先枚举a 在之后枚举c 直接算出b 嵌套的树



1.把b里每个数字抠出来看有没有和a c 相同的

memset()
memcpy

1.枚举a
if (a) dfs_c(u,a,0);对于每个枚举的a 都枚举c
if (check(a,c))ans++; 对于每一个ac 判断b

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>

using namespace std;

const int N = 30;
bool st[N], backup[N]; // st保证原样，backup用来修改
int ans;
int n;

bool check(int a, int c) {
    // 如果 a 为 0，直接返回 false
    if (!a) return false;

    int b = (n - a) * c;  // 修正公式
    if (b <= 0) return false;  // b 应该大于零才是有效的

    // 逐位检查 b 的数字
    memcpy(backup, st, sizeof st);
    while (b) {
        int x = b % 10;  // 取个位
        b /= 10;  // 删个位
        if (!x || backup[x]) return false;  // 不能有重复或 0
        backup[x] = true;
    }

    // 检查所有数字 1~9 是否都有
    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;
    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); // 修正 c 的传递
            st[i] = false;
        }
    }
}

void dfs_a(int u, int a) {
    if (a >= n) return;
    if (a) dfs_c(u, a, 0);  // 传递给 dfs_c
    for (int i = 1; i <= 9; i++) {
        if (!st[i]) {
            st[i] = true;
            dfs_a(u + 1, a * 10 + i);  // 递归选择数字
            st[i] = false;
        }
    }
}

int main() {
    cin >> n;
    dfs_a(0, 0);  // 当前已经用了多少数字
    cout << ans << endl;
    return 0;
}

1. 全局变量和初始化
cpp
const int N = 30;
bool st[N], backup[N];  // st 用来标记数字是否被使用，backup 用于在 check 时备份
int ans;
int n;
st[N]：布尔数组，st[i]表示数字i是否已被使用。通过这个数组来确保每个数字只使用一次。
backup[N]：用来在check函数中备份st数组的状态，确保在递归调用过程中状态不会互相干扰。
ans：存储满足条件的方案总数。
n：目标数字，输入的数字。dfs_a和dfs_c都会用到这个目标。
2. check函数：
cpp
bool check(int a, int c) {
    if (!a) return false;  // 如果 a 为 0，则返回 false
    int b = (n - a) * c;  // 计算 b
    if (b <= 0) return false;  // b 应该大于 0

    memcpy(backup, st, sizeof st);  // 备份 st 数组的当前状态
    while (b) {
        int x = b % 10;  // 取 b 的个位
        b /= 10;  // 移除个位
        if (!x || backup[x]) return false;  // 不能有重复或是 0
        backup[x] = true;  // 标记数字 x 已经使用过
    }

    for (int i = 1; i <= 9; i++) {
        if (!backup[i]) return false;  // 检查 1 到 9 的所有数字是否都有
    }

    return true;  // 如果满足条件，返回 true
}
check函数的目的是验证给定的a和c是否满足题目中要求的条件。
首先检查 a 是否为 0，如果是，直接返回 false。
然后计算 b = (n - a) * c，这个计算的目的是生成一个新的数字 b，并检查 b 的每一位数字。
如果b有重复的数字，或者其中包含数字0，check返回 false。
使用 backup数组来备份当前的 st 数组状态，避免递归过程中的状态冲突。
最后，确认 1~9 之间的数字是否都被使用过（即 backup[i] == true）。
3. dfs_c函数：
cpp
void dfs_c(int u, int a, int c) {
    if (u == n) return;  // 如果深度达到目标，结束递归
    if (check(a, c)) ans++;  // 如果满足条件，增加答案数
    for (int i = 1; i <= 9; i++) {
        if (!st[i]) {
            st[i] = true;  // 标记数字 i 已经被使用
            dfs_c(u + 1, a, c * 10 + i);  // 递归调用，生成新的 c
            st[i] = false;  // 回溯，取消标记
        }
    }
}
dfs_c 是一个递归函数，用来生成数字的组合。
u 是当前递归的深度。
a 是在递归过程中生成的数字的一部分（原始的部分）。
c 是用来拼接数字的另一部分。
u == n 时，表示递归已经达到目标的深度，直接返回。
check(a, c) 用来检查当前的数字组合是否满足条件。如果满足，答案数量ans增加。
接着通过循环遍历 1~9 之间的数字，逐步生成数字 c，并递归调用dfs_c继续生成。
st[i] = true 标记数字 i 已经使用过。
st[i] = false 是回溯的操作，表示取消对数字 i 的使用。
4. dfs_a函数：
cpp
void dfs_a(int u, int a) {
    if (a >= n) return;  // 如果 a 超过 n，停止递归
    if (a) dfs_c(u, a, 0);  // 如果 a 不为 0，则调用 dfs_c
    for (int i = 1; i <= 9; i++) {
        if (!st[i]) {
            st[i] = true;  // 标记数字 i 已使用
            dfs_a(u + 1, a * 10 + i);  // 递归调用，继续生成 a
            st[i] = false;  // 回溯
        }
    }
}
dfs_a 是另一个递归函数，用来生成数字 a 的组合。它的作用是生成一个基础数字 a，然后通过调用 dfs_c 生成与其相关的数字 c。
a >= n 时，停止递归。
如果 a 非零，则调用 dfs_c，将当前的 a 和 0（空的 c）传递给 dfs_c，生成相关的组合。
接着用递归生成所有 a 的可能组合，并在每次递归后回溯，确保每个数字只使用一次。
5. main函数：
cpp
int main() {
    cin >> n;  // 输入目标数字 n
    dfs_a(0, 0);  // 从 0 开始递归生成所有组合
    cout << ans << endl;  // 输出答案数量
    return 0;
}
main函数首先读取输入的数字 n。
然后调用 dfs_a(0, 0) 开始递归，0 表示从数字 a 开始为空。
最后输出 ans，即满足条件的组合数量。

递归：f(n) 调用f（1） f（2）
递推f（1） f（2） 返回到f（n）

滚动数组