AcWing 蓝桥杯AB组辅导课 01、递归与递推（一）

2022-10-21 191

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： AcWing 蓝桥杯AB组辅导课 01、递归与递推（一）

一、递归

知识点

递归，递归的深度决定了运算次数：

斐波那契的递归写法

例题

题目1：AcWing 95.斐波那契数列【简单，递归写法】

题目链接：21. 斐波那契数列

yxc总结—求解斐波那契数列的若干方法

class Solution {
    private int[] arr = new int[39];
    //1 1 2 3 5  f(i) = f(i - 1) + f(i - 2)   【i>2】
    //记忆化递归
    public int Fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int f1 = 0, f2 = 0;
        if (arr[n - 1] != 0) {
            f1 = arr[n - 1];
        }else {
            f1 = arr[n - 1] = Fibonacci(n - 1);
        }
        if (arr[n - 2] != 0) {
            f2 = arr[n - 2];
        }else {
            f2 = arr[n - 1] = Fibonacci(n - 2);
        }
        return f1 + f2;
    }
}

递归本质实际上是一棵递归搜索树。

题目2：AcWing 92.递归实现指数型枚举【简单】

链接：92. 递归实现指数型枚举

借助状态来进行枚举递归

import java.util.*;
class Main{
    private static int n;
    private static int[] arr;//0表示初始，1表示选，2表示不选
    public static void dfs(int u) {
        if (u == n) {
            for (int i = 0; i < n; i++) {
                if (arr[i] == 1) {
                    System.out.printf("%d ",i + 1);
                }
            }
            System.out.println();
            return;
        }
        //递归
        arr[u] = 1;
        dfs(u + 1);
        arr[u] = 0;
        arr[u] = 2;
        dfs(u + 1);
        arr[u] = 0;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n];
        dfs(0);
    }
}

若是我们想要存储所有的路径呢？

①使用一个数组存储：

import java.util.*;
class Main{
    private static final int N = 16;
    private static int n;
    private static int[] arr = new int[N];//0表示初始，1表示选，2表示不选
    //存储所有的路径
    private static int[][] ways = new int[1 << 15][16];
    private static int cnt = 0;//路径方案
    public static void dfs(int u) {
        if (u == n) {
            //存储路径方案
            for (int i = 0; i < n; i++) {
                if (arr[i] == 1) {
                    ways[cnt][i] = i + 1;
                }
            }
            cnt++;
            return;
        }
        //递归
        arr[u] = 1;
        dfs(u + 1);
        arr[u] = 0;
        arr[u] = 2;
        dfs(u + 1);
        arr[u] = 0;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(0);
        //统一进行输出
        for (int i = 0; i < cnt; i++) {
            for (int j = 0; j < n; j++) {
                if (ways[i][j] != 0) {
                    System.out.printf("%d ", ways[i][j]);
                }
            }
            System.out.println();
        }
    }
}

②使用集合工具类：

import java.util.*;
class Main{
    private static final int N = 16;
    private static int n;
    private static int[] arr = new int[N];//0表示初始，1表示选，2表示不选
    //存储所有的路径
    private static List<List<Integer>> ways = new ArrayList<>();
    public static void dfs(int u) {
        if (u == n) {
            List<Integer> path = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                if (arr[i] == 1) {
                    path.add(i + 1);
                }
            }
            ways.add(path);
            return;
        }
        //递归
        arr[u] = 1;
        dfs(u + 1);
        arr[u] = 0;
        arr[u] = 2;
        dfs(u + 1);
        arr[u] = 0;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(0);
        //统一进行输出
        for (int i = 0; i < ways.size(); i++) {
            List<Integer> path = ways.get(i);
            for (int j = 0; j < path.size(); j++) {
                System.out.printf("%d ", path.get(j));
            }
            System.out.println();
        }
    }
}

运行时间：

题目3：AcWing 94.递归实现排列型枚举【简单，全排列】

链接：94. 递归实现排列型枚举

思路：表示顺序的。

时间复杂度的证明如下：

对于全排列的时间复杂度为O(n.n!)，其中还计算上了输出的时间复杂度。

Java解法（超时）：

import java.util.*;
class Main {
    private static int N = 9;
    private static int n;
    //路径结果集
    private static int[] state = new int[N];
    //1-5路径是否访问过
    private static boolean[] visited = new boolean[N];
    //u表示的是当前的数字的长度
    public static void dfs (int u) {
        if (u == n) {
            //开始输出方案
            for (int i = 0; i < n; i++) {
                System.out.printf("%d ", state[i]);
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                //进行标记
                visited[i] = true;
                state[u] = i + 1;
                //递归
                dfs(u + 1);
                //恢复现场
                visited[i] = false;
                state[u] = 0;
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(0);
    } 
}

C++解法（不超时）：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 9;
int n;
int state[N];
bool visited[N];
void dfs (int u) {
    if (u == n) {
        for (int i = 0; i < n; i++) {
            printf("%d ", state[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            state[u] = i + 1;
            visited[i] = true;
            dfs(u + 1);
            state[u] = 0;
            visited[i] = false;
        }
    }
}
int main() {
    scanf("%d", &n);
    dfs(0);
    return 0;
}

习题

题目1：AcWing 93.递归实现组合型枚举【简单】

链接：93. 递归实现组合型枚举

思路：在之前递归实现排列型枚举上来进行改进，这里只不过是限制了数值的范围及长度，我们只需要在for遍历i的过程时修改指定的值即可。

Java解法：

import java.util.*;
class Main {
    private static final int N = 30;
    private static int n, m;
    //这里面每条结果集都是m个，所以这里无需使用visted数组来表示是否访问过
    private static int[] state = new int[N];
    public static void  dfs (int u, int start) {
        //优化剪枝
        if (u + (n - start) < m) return;
        if (u == m) {
            //遍历打印
            for (int i = 0; i < m; i++) {
                System.out.printf("%d ", state[i]);
            }
            System.out.println();
            return;
        }
        //根据起始位置开始
        for (int i = start; i < n; i++) {
            state[u] = i + 1;
            dfs(u + 1, i + 1);
            state[u] = 0;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        dfs(0, 0);
    }
}

优化之后：

C++解法：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 30;
int n, m;
int state[N];
void dfs(int u, int start) {
    //优化剪枝
    if (u + (n - start) < m) return;
    if (u == m) {
        for (int i = 0; i < m; i++) {
            printf("%d ", state[i]);
        }
        printf("\n");
        return;
    }
    for (int i = start; i < n; i++) {
        state[u] = i + 1;
        dfs(u + 1, i + 1);
        state[u] = 0;
    }
}
int main() {
    scanf("%d%d", &n, &m);
    dfs (0, 0);
    return 0;
}

40倍是什么鬼？c++这么快！

优化：对于当前数+剩余的情况数<结果数量时提前进行结束

//提前剪枝（当前的各自数量+剩余的各自数量） < 总的组成数量
//简单说：即便把后面所有的数都选上，都不够m个，当前分支绝对无解
if (u + (n - start) < m) return;

时间提升了3倍左右：

AcWing 蓝桥杯AB组辅导课 01、递归与递推（一）

一、递归

知识点

例题

题目1：AcWing 95.斐波那契数列【简单，递归写法】

题目2：AcWing 92.递归实现指数型枚举【简单】

题目3：AcWing 94.递归实现排列型枚举【简单，全排列】

习题

题目1：AcWing 93.递归实现组合型枚举【简单】

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

AcWing 蓝桥杯AB组辅导课 01、递归与递推（一）

一、递归

知识点

例题

题目1：AcWing 95.斐波那契数列【简单，递归写法】

题目2：AcWing 92.递归实现指数型枚举【简单】

题目3：AcWing 94.递归实现排列型枚举【简单，全排列】

习题

题目1：AcWing 93.递归实现组合型枚举【简单】

热门文章

最新文章

相关电子书