蓝桥杯备赛 Java 每日刷题（1）_蓝桥杯java dfs全排列

今天复习递归

第一道  Acwing 1209.带分数

思路：暴力枚举的方式（dfs全排列）， n = a + b / c，n已知，枚举a，b，c即可求解。

import java.util.Scanner;
 
public class Main {
 
    static final int N = 10;
    static int n; // 输入的目标数
    static int cnt; // 最后的结果数
    static int[] num = new int[N]; // 保存全排列的结果
    static boolean[] used = new boolean[N]; // 标记数字状态 true表示已使用，false表示未使用
    static Scanner sc = new Scanner(System.in);
 
    public static void main(String[] args) {
        n = sc.nextInt();
        dfs(0);
        System.out.print(cnt);
    }
 
    private static void dfs(int u) {
        
        if (u == 9) {
            // 两层循环将数组分成三段
            for (int i = 0; i < 7; i++) {
                for(int j = i + 1; j < 8; j++) {
                    int a = calc(0, i);
                    if (a >= n) return; // 优化：如果a比n还大 说明无解 直接return
                    int b = calc(i + 1, j);
                    int c = calc(j + 1, 8);
                    if (a * c + b == c * n) { // n = a + b / c 化为 c·n = c·a + b
                        cnt++;
                    }
                }
            }
            return;
        }
        // 全排列模板
        for (int i = 1; i <= 9; i++) {
            if (!used[i]) {
                used[i] = true;
                num[u] = i;
                dfs(u + 1);
                used[i] = false; // 恢复现场
            }
        }
    }
    // 在数组中计算某一区间的数
    private static int calc(int l, int r) {
        int res = 0;
        for (int i = l; i <= r; i++) {
            res = res * 10 + num[i];
        }
        return res;
    }
}

也可以从1开始递归，符合之前我的训练逻辑,代码如下（也可以通过全部测评）：

import java.util.Scanner;
 
public class Main {
    static final int N = 10;
    static int n, cnt;
    static int[] num = new int[N];
    static boolean[] used = new boolean[N];
    static Scanner sc = new Scanner(System.in);
    
    public static void main(String[] args) {
        n = sc.nextInt();
        dfs(1); //数字1-9，一共九位，从第一位开始递归
        System.out.print(cnt);
    }
    
    private static void dfs(int u) {
        //全排列模板
        if(u == 10){ //触发边界条件，说明已经递归了前面九位，此时可以根据公式进行判断
            for(int i = 1;i <= 7; i++) {
                for(int j = i + 1;j <= 8;j++) {
                    int a = calc(1, i);
                    if(a > n) return;
                    int b = calc(i + 1, j);
                    int c = calc(j + 1, 9);
                    if(a * c + b == c * n) {
                        cnt++;
                    }
                }
            }
            return;
        }
        for(int i = 1; i <= 9; i++) {
            if(!used[i]) {
                num[u] = i;
                used[i] = true;
                dfs(u + 1);
                used[i] = false;
            }
        }
    }
    
    private static int calc(int l, int r) {
        //计算一个区间之内的数
        int res = 0;
        for(int i = l; i <= r; i++) {
            res = res * 10 + num[i];
        }
        return res;
    }
}

今天再复习一下前期的递归

递归实现指数型枚举（每个位置都有x个选择，共有n个位置，枚举完共有x^n种可能的结果）AcWing 92. 递归实现指数型枚举

import java.util.Scanner;
 
public class Main {
    static int n, N = 16;
    static int[] st = new int[N]; // 状态，记录每个位置当前的状态：0表示还没考虑，1表示选它，2表示不选它
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(1);
    }
    private static void dfs(int u) {
        if (u > n) {
            for (int i = 1; i <= n; i++) {
                if (st[i] == 1) {
                    System.out.print(i + " ");
                }
            }
            System.out.println();
            return;
        }
 
        st[u] = 2;
        dfs(u + 1); // 第一个分支：不选
        // 这两行恢复现场加不加都一样的 
        // 因为递归时会被下面的值给覆盖掉 所以不用手动恢复 这里加上是让代码看起来更加圆滑 更加还原算法本身
        st[u] = 0; // 恢复现场
 
        st[u] = 1;
        dfs(u + 1); // 第二个分支：选
        st[u] = 0;
    }
}

排列型枚举（所给的位置与所供选择的数字数目一致）Acwing 94. 递归实现排列型枚举

//本题考查枚举
//输出n个数所有排列的次序，题目所说是按照字典序排列
//思想：依次枚举每个数放到哪个位置or依次枚举每个位置放哪个数（本题代码）
 
//对于n = 3，每个位置会划分出三个分支
import java.util.Scanner;
 
public class Main {
    static int n, N = 10;
    static int[] state = new int[N]; //0表示还没放数字，1-n表示放了哪个数
    static boolean[] used = new boolean[N];//true表示这个数用过了，false表示还没用过
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(1);
    }
    
    private static void dfs(int u) {
        if (u > n) { //如果已经到了边界，也就是到了最后一个位置
            for(int i = 1; i <= n; i++) {
                System.out.print(state[i] + " ");
            }
            System.out.println();
            return;
        }
        //接下来依次枚举每个分支，即当前位置可以填哪些数
        for(int i = 1; i <= n; i++) {
            if(!used[i]) {
                state[u] = i;
                used[i] = true;
                dfs(u + 1);
                
                //恢复现场
                state[u] = 0;
                used[i] = false;
            }
        }
    }
}

组合型枚举（位置比数字少）AcWing 93. 递归实现组合型枚举