当前位置：首页 > article >正文

《从入门到精通：蓝桥杯编程大赛知识点全攻略》（二）-递归实现组合型枚举、带分数问题

article 2025/1/7 23:38:59

在算法和编程中，组合型枚举问题常常出现在许多实际应用中。特别是在涉及到有限的选择、约束条件和分配问题时，递归算法能够以非常高效的方式求解这些问题。递归不仅提供了一个直观的思路，还能使得复杂的问题简化为多个子问题，从而逐步解决。

前言

递归实现组合型枚举

算法思路

代码如下

带分数

算法思路

代码如下

总结

前言

在算法和编程中，组合型枚举问题常常出现在许多实际应用中。特别是在涉及到有限的选择、约束条件和分配问题时，递归算法能够以非常高效的方式求解这些问题。递归不仅提供了一个直观的思路，还能使得复杂的问题简化为多个子问题，从而逐步解决。

在这篇博客中，我们将深入探讨递归在组合型枚举中的应用，特别是带分数的情况。我们将通过一个经典的递归处理问题——带分数问题来展示如何利用递归实现枚举过程。

无论您是初学者还是已经有一定算法基础的开发者，掌握递归的思维方式和技巧，将帮助您在解决复杂问题时更加得心应手，尤其是在需要枚举大量组合的情况下。

递归实现组合型枚举

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

输入格式

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

输出格式

按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围

n>0
0≤m≤n
n+(n−m)≤25

输入样例：

5 3

输出样例

算法思路

组合是从一组元素中选择若干个元素，不考虑顺序。

排列是从一组元素中选择若干个元素，考虑顺序。

如何从排列的过程中得到组合所需的数列避免重复？

我们可以人为的指定一种顺序，即数列的数字是从小到大排序，这样就可以避免获得重读数列。

用整型数组way来接收数列，先找到递归的出口，当当前位置u大于m个位置时（u > m），直接循环打印way数组，即可得到数列。当位置未填满时（u < m），我们可以知道当前位置最小为start，此时我们就可以从start一直枚举到最后一个数，然后让当前位置的数列等于此时的i即（way[u] = i），接着递归的处理下一个位置dfs(u+1,i+1)，再恢复现场即way[u] = 0即可。

代码如下



import java.io.*;

public class Main {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static int[] way = new int[30];
    static int n,m;


    public static void main(String[] args)throws IOException {
        n = nextInt();
        m = nextInt();

        dfs(1,1);
        pw.flush();
    }
    /*
    u表示当前枚举的位置
    start表示当前最小可以从哪枚举
     */
    public static void dfs(int u,int start){
        if(u > m){
            for(int i = 1;i <= m;i++){
                pw.print(way[i]+" ");
            }
            pw.println();
            return;
        }
        for(int i = start;i <= n;i++){
            way[u]=i;
            dfs(u+1,i+1);
            //将原位置恢复
            way[u]=0;
        }
    }

    public static int nextInt()throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
}

当然，还可以进行剪枝优化

package AcWingLanQiao;

import java.io.*;

public class 递归实现组合型枚举 {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static int[] way = new int[30];
    static int n,m;


    public static void main(String[] args)throws IOException {
        n = nextInt();
        m = nextInt();

        dfs(1,1);
        pw.flush();
    }
    /*
    u表示当前枚举的位置
    start表示当前最小可以从哪枚举
     */
    public static void dfs(int u,int start){
        //剪枝
        if(u - 1 + n - start + 1 < m){
            return;
        }
        if(u > m){
            for(int i = 1;i <= m;i++){
                pw.print(way[i]+" ");
            }
            pw.println();
            return;
        }
        for(int i = start;i <= n;i++){
            way[u]=i;
            dfs(u+1,i+1);
            //将原位置恢复
            way[u]=0;
        }
    }

    public static int nextInt()throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
}

就是当前位置是u，那么说明前u - 1个位置已经排好了，那么剩下还有 n - start + 1个数，如果 u - 1 + n - start + 1个数还是不够m即（u + n - start < m），那么就说明一定是无解情况，可以减小递归次数。

带分数

100 可以表示为带分数的形式：100=3+69258/714

还可以表示为：100=82+3546/197

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

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

输入格式

一个正整数。

输出格式

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

数据范围

$1\leqslant N < 10^{6}$

算法思路

我们可以通过dfs来对9个数字进行全排列得到所有的数字情况，得到每一种情况，然后再来枚举a b c的位数，因为知道a和b的位数，那么c的位数就知道了。然后对应每一种情况来计算等式是否成立，成立就说明该情况符合。

用整型数组arr来记录结果，布尔类型数组flag来表示1-9那位数组是否被用过，true表示已被使用，false表示未被使用。全排列的详情可参考https://mp.csdn.net/mp_blog/creation/editor/144703235

这篇博客，最重要的就是通过双层循环来枚举a、b、c的位数，比如for循环下标i从1到9，那么a的位数就是从1到i，在嵌套一层循环j从i+1到9，b的位数就是从i+1到 j，最后c位数就是从j+1到9。其中知道位数，数组转换成整数只需要初始化一个sum = 0，然后每遍历一位让sum * 10 + arr[i]就可以得到对应的整数。

代码如下

暴力做法：直接枚举3个数对应的位数

package AcWingLanQiao;

import java.io.*;

public class 带分数 {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static boolean[] flag = new boolean[20];
    static int[] arr = new int[20];
    static int target;
    //统计次数
    static int res = 0;
    public static void main(String[] args) throws IOException {
        target = nextInt();
        dfs(1);
        pw.println(res);
        pw.flush();
    }
    //暴力做法
    public static void dfs(int u){
        if(u > 9){
            for(int i = 1;i <= 9;i++){
                for(int j = i+1;j <= 9;j++){
                    int a = cal(1,i);
                    int b = cal(i+1,j);
                    int c = cal(j+1,9);
                    if(target * c == c * a + b){
                        res++;
                    }
                }
            }
            return;
        }
        for(int i = 1;i <= 9;i++){
            if(!flag[i]){
                arr[u] = i;
                flag[i] = true;
                dfs(u+1);
                flag[i] = false;
            }
        }
    }
    public static int cal(int a,int b){
        int sum = 0;
        for(int i = a;i <= b;i++){
            sum = sum * 10 + arr[i];
        }
        return sum;
    }

    public static int nextInt()throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
}