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

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

news 来源：原创 2024/5/4 11:06:24

文章目录

  • 前言
  • 一、递归
    • 知识点
    • 例题
      • 题目1：AcWing 95.斐波那契数列【简单，递归写法】
      • 题目2：AcWing 92.递归实现指数型枚举【简单】
      • 题目3：AcWing 94.递归实现排列型枚举【简单，全排列】
    • 习题
      • 题目1：AcWing 93.递归实现组合型枚举【简单】
      • 题目2：AcWing 1209.带分数【简单，蓝桥杯编程第2题】
      • 题目3：AcWing 95.费解的开关【中等】
      • 题目4：AcWing 116.飞行员兄弟【简单】
      • 题目5：AcWing 1208.翻硬币【简单，蓝桥杯2013年B组第8题】
  • 二、递推
    • 例题
      • 题目1：AcWing 95.斐波那契【简单，递推写法】

前言

前段时间为了在面试中能够应对一些算法题走上了刷题之路，大多数都是在力扣平台刷，目前是300+，再加上到了新学校之后，了解到学校也有组织蓝桥杯相关的程序竞赛，打算再次尝试一下，就想系统学习一下算法（再此之前是主后端工程为主，算法了解不多刷过一小段时间），前段时间也是第一次访问acwing这个平台，感觉上面课程也是比较系统，平台上题量也很多，就打算跟着acwing的课程来走一段路，大家一起共勉加油！

  • 目前是打算参加Java组，所以所有的题解都是Java。

本章节递归与递推习题一览：包含所有题目的Java题解链接

image-20221005164726213

例题：

  • AcWing 92. 递归实现指数型枚举 Java题解
  • AcWing 94. 递归实现排列型枚举 Java & C++
  • AcWing 21. 斐波那契数列 Java题解 （递归、递推写法）
  • AcWing 95. 费解的开关 Java题解

习题：

  • AcWing 21. 斐波那契数列 Java题解 （递归、递推写法）
  • AcWing 1209. 带分数 Java题解
  • AcWing 116. 飞行员兄弟 Java题解
  • AcWing 1208. 翻硬币 Java题解

一、递归

知识点

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

image-20220926165449301

斐波那契的递归写法

例题

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

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

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

image-20220926164937795

image-20220926165228536

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. 递归实现指数型枚举

借助状态来进行枚举递归

image-20220927125343883

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);
    }
}

image-20220927171539897

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

①使用一个数组存储：

image-20220927132509590

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();
        }
    }
}

image-20220927132618063

②使用集合工具类：

image-20220927171418574

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();
        }
    }
}

运行时间：

image-20220927171450269

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

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

思路：表示顺序的。

image-20220927175311926

时间复杂度的证明如下：

image-20220927175825927

对于全排列的时间复杂度为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);
    } 
}

image-20220927180845609

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;
}

image-20220927180824423

习题

image-20220927210805842

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

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

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

image-20220927191904202

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);
    }
}

image-20220927192802427

优化之后：

image-20221002143548102

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;
}

image-20220927193456088

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

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

image-20220927194551054

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

时间提升了3倍左右：

image-20220927194459877

题目2：AcWing 1209.带分数【简单，蓝桥杯编程第2题】

来源：第四届蓝桥杯省赛C++B/C组,第四届蓝桥杯省赛JAVAA/B组

链接：1209. 带分数

import java.util.*;

class Main {
    
    
    private static int n;
    private static boolean[] v = new boolean[10];
    //记录结果集
    private static int ans;
    
    //检查
    private static boolean check(int a, int c) {
        //计算b
        int b = n * c - a * c;
        
        //提前剪枝（若是出现0则直接结束）
        if (a == 0 || b <= 0 || c == 0) return false;
        
        //复制拷贝是否存在的数组（避免重新恢复现场）
        boolean[] vv = Arrays.copyOfRange(v, 0, v.length);
        //遍历b的所有元素
        while (b != 0) {
            int x = b % 10;
            //若是b中出现0或者之前已经出现过，此时直接就结束
            if (x == 0 || vv[x]) return false;
            //记录访问过
            vv[x] = true;
            b = b / 10;
        }
        //遍历10个数是否都有存在
        for (int i = 1; i <= 9; i++) {
            if (!vv[i]) return false; 
        }
        return true;
    }
    
    public static void dfs_c(int u, int a, int c) {
        //c以n的最大长度最为基准
        if (u == n) return;
        //相当于枚举出来一组a,c
        if (check(a, c)) ans++;
        
        //向下递归推举出下一个c
        for (int i = 1; i <= 9; i++) {
            if (!v[i]) {
                v[i] = true;
                dfs_c(u + 1, a, c * 10 + i);
                v[i] = false;
            }
        }
    }
    
    //在进行递归推的时候算出a的值
    public static void dfs_a(int u, int a) {
        //若是a的值>=n数字，此时就直接提前结束
        if (a >= n) return;
        //符合条件情况，向下递归推出c
        if (a != 0) {
            dfs_c(u, a, 0);
        }
        
        for (int i = 1; i <= 9; i++) {
            if (!v[i]) {
                v[i] = true;
                dfs_a(u + 1, a * 10 + i);
                v[i] = false;
            }
        }
    }
    
    //枚举出来a,c => 推出b，最后进行check检查
    //全排列+check检查【更加复杂】
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs_a(0, 0);
        System.out.printf("%d", ans);
    }
}

题目3：AcWing 95.费解的开关【中等】

来源：《算法竞赛进阶指南》

链接：95. 费解的开关

  • 学习链接：AcWing 95. 费解的开关

思路：是否点亮全部的灯泡完全取决于第一行是否按灯泡开关起到了决定性的作用，后面的四行都是依据前一行来进行开关动作。当前给出的是固定范围，5x5，第一行有五个格子，换成二进制表示5位就有32中按法，该题中我们需要来进行所有方案的枚举即可找到最少次数的按键。

image-20220930094833878

复杂度分析：时间复杂度计算（32x(25x5)x500）

  • 其中32表示一个问题解的第一行开关按钮的方案数，25表示要对25个格子进行遍历判断亮关，5表示若是进行开那么上下左右以及当前位置需要进行变换操作，最后的500则是可能出现最大500个方案问题。
  • 约等于2000000，在一亿次运行范围中。
import java.util.*;
class Main {
    
    //输入情况数
    private static int n;
    //backup表示备份矩阵
    private static int[][] arr = new int[5][5], backup = new int[5][5];
    
    //结果集
    private static int ans = Integer.MAX_VALUE;
    //定义x、y方向  上下左右中
    private static int[] dx = {-1, 1, 0, 0, 0};
    private static int[] dy = {0, 0, -1, 1, 0};
    
    //按开关
    public static void turn(int i, int j) {
        //五个位置：上下左右中
        for (int pos = 0; pos < 5; pos++) {
            int x = i + dx[pos];
            int y = j + dy[pos];
            //若是越界则不进行开关操作（1->0   0->）
            if (x < 0 || x >= 5 || y < 0 || y >= 5) continue;
            //0^1=1  1^1=0
            backup[x][y] ^= 1;
        }
    }
    
    /*
    01111
    11111
    11111
    11111
    11111
    **/
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        while (n != 0) {
            //初始化
            for (int i = 0; i < 5; i++) {
                String s = sc.next();
                for (int j = 0; j < 5; j++) {
                    arr[i][j] = s.charAt(j) - '0';
                }
            }
            //每个位置的开关操作表示一个按法（按or不按）
            //对于00000，5位可以有32种按法 00000 00001  00010  00011，其中1就是开，0就是不按
            for (int op = 0; op < 1 << 5; op++) {
                int cnt = 0;//记录当前方案按的次数
                //备份与arr同样的状态backup，之后的模拟操作针对backup数组
                for (int i = 0; i < 5; i++)
                    for (int j = 0; j < 5; j++) 
                        backup[i][j] = arr[i][j];
                //对第一行进行操作
                //op表示的就是一个方案，根据来操作
                //根据当前的op方案来按第一行灯泡
                for (int j = 0; j < 5; j++){
                    //取出最后一个，例如：0  二进制表示00000000，op>>0表示进行右移1位，此时&1，就是取到最后一位，当前是0
                    //之后四个方案一次对应表示
                    if ((op >> j & 1) == 1){
                        turn(0, j);
                        cnt++;
                    }
                }
                //对后四行来进行操作
                for (int i = 0; i < 4; i++) {
                    for (int j = 0; j < 5; j++) {
                        //若是当前行没有点亮
                        if (backup[i][j] == 0) {
                            turn(i + 1, j);
                            cnt++;
                        }
                    }
                }
                //check最后一行是否全部点亮（有一个没点亮表示该方案不成立）
                int j = 0;
                while (j < 5) {
                    if (backup[4][j] == 0) break;
                    j++;
                }
                //若是当前的方案能够完全点亮
                if (j == 5 && cnt <= 6) ans = Math.min(cnt, ans); 
            }
            if (ans > 6) ans = -1;
            System.out.printf("%d\n", ans);
            n--;
            ans = Integer.MAX_VALUE;
        }
    }
}

image-20221001133610766

题目4：AcWing 116.飞行员兄弟【简单】

来源：《算法竞赛进阶指南》

视频讲解：2.1

链接：116. 飞行员兄弟

y总分析：数据量小，可以使用暴力搜索。216=65535，数据量不大，枚举所有方案，再最终check所有状态。【太强了 】

image-20220929163116901

优化：可以使用二进制来进行优化，不过当前使用数组方案是能够满足情况的。

思路：将16个格子从左往右，从上至下，看做是16位的数，可使用一个int整型表示。

import java.util.*;

//顺序从上到下，从左到右
//枚举16位
//2^16 x 7 x 16 约733万
class Main {
    
    static class Pair<K, V> {
        K x;
        V y;
        public Pair(K x, V y) {
            this.x = x;
            this.y = y;
        }
    }
    
    static final int N = 4;
    static char[][] arr = new char[4][4], backup = new char[4][4];
    //保存结果集、按下的位置
    static List<Pair<Integer, Integer>> ansList;
    
    //根据i与j取得当前的位数
    public static int getPos(int i, int j) {
        return i * 4 + j;
    }
    
    public static void turnOne(int x, int y) {
        if (backup[x][y] == '-') backup[x][y] = '+';
        else backup[x][y] = '-';
    }
    
    //按住当前位置
    public static void turnAll(int i, int j) {
        for (int pos = 0; pos < 4; pos++) {
            turnOne(i, pos);
            turnOne(pos, j);
        }
        turnOne(i, j);
    }
    
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //初始化
        for (int i = 0; i < 4; i++) {
            String line = sc.next();
            for (int j = 0; j < 4; j++) {
                arr[i][j] = line.charAt(j);
            }
        }
        //定义不同的方案数
        for (int op = 0; op < 1 << 16; op++) {
            List<Pair<Integer, Integer>> list = new ArrayList<>();
            //根据指定方案来进行推算
            //备份一份状态
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    backup[i][j] = arr[i][j];
                }
            }
            //对backup来进行操作 
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    //当前方案该i，j位置需要进行按住
                    if ((op >> getPos(i, j) & 1) == 1) {
                        turnAll(i, j);
                        list.add(new Pair<Integer, Integer>(i, j));
                    }
                }
            }
            //最终进行check检查
            boolean flag = true;
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    if (backup[i][j] != '-') {
                        flag = false;
                        break;
                    }
                }
            }
            //报错结果集
            if (flag && (ansList == null || ansList.size() > list.size())) {
                ansList = list;
            }
        }
        //最终输出结果集
        System.out.printf("%d\n", ansList.size());
        for (int i = 0; i < ansList.size(); i++) {
            System.out.printf("%d %d\n", ansList.get(i).x + 1, ansList.get(i).y + 1);
        }
    }
}

image-20221001143313257

题目5：AcWing 1208.翻硬币【简单，蓝桥杯2013年B组第8题】

来源：第四届蓝桥杯省赛C++B组

标签：递推

视频讲解：2.1中

链接：1208. 翻硬币

分析：两大类做法：初始状态->目标状态。

  • 可采用宽搜bfs，可使用时间复杂度比较高。只有状态数局面不大采用bfs。
  • 若是局面特别大可采用其他做法。

把其想象为开关的做法【此类就是一个模拟的问题】

有解必然只有一组唯一解。（看起来最少需要多少步，实际上只有一组解）

若是一次翻转3或4次时，也同样可以使用上面的模拟解决了【前面一次能够推举出后面按的操作】。

image-20221001145442308

  • 10个字符，一次连续按两个，相当于9次，那么一个个依次去进行比较即可。
import java.util.*;

class Main {
    
    public static void turn(int i) {
        from[i] = from[i] == '*' ? 'o' : '*';
    }
    
    static char[] from;
    static char[] to;
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        from = cin.next().toCharArray();
        to = cin.next().toCharArray();
        //n - 1步
        int n = from.length;
        int ans = 0;
        for (int i = 0; i < n - 1; i++) {
            if (from[i] != to[i]) {
                //进行反转连续的两个
                turn(i);
                turn(i + 1);
                ans++;
            }
        }
        System.out.printf("%d", ans);
    }
}

image-20221001145520997

二、递推

例题

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

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

class Solution {
    
    private int[] fn = new int[40];
    
    //递推
    public int Fibonacci(int n) {
        fn[1] = 1;
        fn[2] = 1;
        for (int i = 3; i <= n; i++) fn[i] = fn[i - 1] + fn[i - 2];
        return fn[n];
    }
}

image-20220929121820006

相关文章：

  • 2022软考高项十大领域知识整理（三）--项目质量管理、沟通管理
  • spring boot在线投票系统 毕业设计源码141307
  • 申请专利申请流程,专利申请详细步骤
  • echarts文档解读
  • 稀疏矩阵的压缩存储
  • 动手学习深度学习 08：机器视觉
  • CNN（卷积网络）如何处理Size(Shape)大小可变的输入图像数据
  • 小鱼的一键安装系列
  • Spring Cloud Alibaba-Ribbon的源码分析
  • MASA MAUI Plugin IOS蓝牙低功耗（三）蓝牙扫描
  • 30岁以上的程序员还死磕技术，别说拿高薪，可能连饭碗都会保不住
  • numpy快速处理数据学习笔记
  • C++多态详解
  • sqlserver sa 密码忘记 处理
  • 自定义流程，匹配业务需求，还得是专业流程引擎
  • css布局，左右固定中间自适应实现
  • Docker 笔记（1）：介绍、镜像、容器及其基本操作
  • eclipse(luna)创建web工程
  • iOS帅气加载动画、通知视图、红包助手、引导页、导航栏、朋友圈、小游戏等效果源码...
  • Linux链接文件
  • mysql_config not found
  • Python 基础起步 (十) 什么叫函数？
  • React系列之 Redux 架构模式
  • spring + angular 实现导出excel
  • Swift 中的尾递归和蹦床
  • 从 Android Sample ApiDemos 中学习 android.animation API 的用法
  • 大快搜索数据爬虫技术实例安装教学篇
  • 分享一个自己写的基于canvas的原生js图片爆炸插件
  • 漂亮刷新控件-iOS
  • 如何用vue打造一个移动端音乐播放器
  • 试着探索高并发下的系统架构面貌
  • 由插件封装引出的一丢丢思考
  • Spring第一个helloWorld
  • ​RecSys 2022 | 面向人岗匹配的双向选择偏好建模
  • ​Z时代时尚SUV新宠：起亚赛图斯值不值得年轻人买？
  • ​软考-高级-系统架构设计师教程（清华第2版）【第1章-绪论-思维导图】​
  • !$boo在php中什么意思,php前戏
  • #pragma 指令
  • $$$$GB2312-80区位编码表$$$$
  • (31)对象的克隆
  • （9）目标检测_SSD的原理
  • （第8天）保姆级 PL/SQL Developer 安装与配置
  • （附源码）SSM环卫人员管理平台 计算机毕设36412
  • （附源码）小程序儿童艺术培训机构教育管理小程序 毕业设计 201740
  • (免费分享)基于springboot,vue疗养中心管理系统
  • (三)docker：Dockerfile构建容器运行jar包
  • （三）终结任务
  • （未解决）macOS matplotlib 中文是方框
  • （转） ns2/nam与nam实现相关的文件
  • ***测试-HTTP方法
  • .NET CF命令行调试器MDbg入门（三） 进程控制
  • .net core Swagger 过滤部分Api
  • .NET gRPC 和RESTful简单对比
  • .NET Reactor简单使用教程
  • .NET/C# 中你可以在代码中写多个 Main 函数，然后按需要随时切换