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

《从入门到精通：蓝桥杯编程大赛知识点全攻略》（一）-递归实现指数型枚举、递归实现排列型枚举

article 2025/1/6 7:14:57

本篇博客将聚焦于通过递归来实现两种经典的枚举方法：指数型枚举和排列型枚举。这两种枚举方式在计算机科学和算法竞赛中都有广泛应用，无论是在解题中，还是在实际工作中都极具价值。

前言

斐波那契数列递归

递归实现指数型枚举

算法思路

代码如下

递归实现排列型枚举

算法思路

代码如下

总结

前言

在编程的世界里，递归是一种优雅且强大的技术，它能让复杂问题变得更加简洁和易于理解。无论是数学中的公式推导，还是计算机科学中的算法设计，递归都扮演着不可或缺的角色。在数据结构与算法中，递归不仅能帮助我们高效地解决问题，还能展现出代码的简洁性和表达力。

本篇博客将聚焦于通过递归来实现两种经典的枚举方法：指数型枚举和排列型枚举。这两种枚举方式在计算机科学和算法竞赛中都有广泛应用，无论是在解题中，还是在实际工作中都极具价值。

斐波那契数列递归

递归最经典的就是斐波那契数列，其中第1个数是1，第2个数是2，第3个数是前两个数字之和。

$f(n) = f(n - 1) + f(n - 2) n\geq 3$

java代码如下：

package AcWingLanQiao;

import java.util.*;

public class 递归 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(f(n));
    }
    public static int f(int n){
        if(n==1){ return 1;}
        if(n==2){ return 2;}
        return f(n-1)+f(n-2);
    }
}

递归实现指数型枚举

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

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。

对于没有选任何数的方案，输出空行。

数据范围

1≤n≤15

输入样例

输出样例

算法思路

每一个位置都有两种情况，分别是选和不选。

当有n个数时，结果就有 $2^{n}$ 中情况。

当n为对的时候，上述对应的是递归搜索树。从第一个位置开始分两种情况，选和不选，后续每个位置一次类推。

我们用一个数组flag，数组下标表示从1到n，flag[i]表示该值在每个位置的状态，0表示还未考虑，1表示选，2表示这个位置不选；通过dfs深度优先搜索，用u来表示当前在哪个位置，先思考递归的出口，当当前位置u要大于n时（即u > n），就说明n个位置每个位置的情况都处理好了，就说明最后flag[i] = 1对应的下标就是结果所需的序列。

当u <= n时，我们只需处理两种情况，一种是选，一种是不选。当选时，将flag[u] = 1，然后递归的处理下一个位置dfs(u+1)，最后再恢复现场flag[u] = 0，即相当于是当前的位置都处理完了，将位置恢复为未处理，然后再走另一种情况；当不选时，将flag[u] = 2,后递归的处理下一个位置dfs(u+1)，最后再恢复现场flag[u] = 0。

代码如下

package AcWingLanQiao;
import java.io.*;
import java.util.*;

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 N = 16;
    /*
    状态数据，记录每个位置的当前状态
    0表示还未考虑
    1表示选它
    2表示不选它
     */
    static int[] flag = new int[N];
    static int n;
    public static void main(String[] args)throws Exception {
        n = nextInt();
        dfs(1);
        pw.flush();
    }

    public static void dfs(int u){
        if(u > n){
            for(int i = 1;i <= n;i++){
                if(flag[i] == 1){
                    pw.print(i+" ");
                }
            }
            pw.println();
            pw.flush();
            return;
        }
        flag[u] = 2;
        dfs(u+1);  //第一个分支不选
        flag[u] = 0;//恢复现场

        flag[u] = 1;
        dfs(u+1); //第二个分支选
        flag[u] = 0;
    }

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

递归实现排列型枚举

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

输入格式

一个整数 n。

输出格式

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

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

1≤n≤9

输入样例

输出样例

注：字典序排序是一种按照字典中单词出现的顺序来排列元素的方法。在计算机科学中，它被用来比较两个字符串的大小关系，即比较它们从左到右第一个不同字符的ASCII值的大小关系。这种排序方式不仅适用于英文单词，也适用于任意字符串的比较。

算法思路

用整型数组arr来存储数列的结果，布尔类型数组flag，其中flag[i]若为true表示数字i已被使用，若为false表示数字i未被使用。使用深度优先搜索dfs来解决此问题。我们可以通过每个位置放置哪个数字来进行思考。

我们先来思考递归的出口，当当前位置u大于n时（即u > n），说明所有的位置上数字都以排好，所以此时只需打印arr数组，就可以得到结果。当n为3时，说明一个位置有3种情况，所以要有一个外层循环，然后来判断flag[i]是否被使用，未被使用则将当前位置复制为i即arr[u] = i，还需将该数字对应的flage数组设置为已使用即flag[i] = true，然后递归的处理下一个位置即dfs(u+1)，最后再进行回溯操作flag[i] = false。如果flag[i]已经被使用，则接着进行下一次数字进行判断，n个数字都被使用，也可说明数列已被排完序。

算法时间复杂度为O（n*n!）

代码如下



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 N = 10;
    static int[] arr = new int[N];
    static boolean[] flag = new boolean[N]; //true表示用过 false表示未被用过
    static int n;
    public static void main(String[] args) throws IOException {
        n = nextInt();
        dfs(1);

        pw.flush();
    }
    public static void dfs(int u) {
        if(u > n){ //边界
            for(int i = 1; i<= n;i++){
                pw.print(arr[i]+" ");
            }
            pw.println();
            return;
        }

        //枚举每个分支
        for(int i = 1; i<= n;i++){
            if(!flag[i]){
                arr[u] = i;
                flag[i] = true;
                dfs(u+1);
                //恢复现场
                flag[i] = false;
            }
        }
    }
    public static int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }
}

代码输入

代码输出结果