第一讲 递推与递归
创始人
2025-05-28 18:56:05
0

文章目录

    • 1.费解的开关(递推、位运算)
    • 2.带分数(全排序/递归👍)
    • 3.飞行员兄弟(位运算)
    • 4.翻硬币(贪心/递推❓)
    • 5.递归实现指数型枚举
    • 6.递归实现排列行枚举
    • 7.递归实现组合型枚举

1.费解的开关(递推、位运算)

你玩过“拉灯”游戏吗?

25 盏灯排成一个 5×5 的方形。

每一个灯都有一个开关,游戏者可以改变它的状态。

每一步,游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 1 表示一盏开着的灯,用数字 0 表示关着的灯。
下面这种状态

10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成:

01111
11101
10111
11011
再改变它正中间的灯后状态将变成:

01111
11001
11001
10100
11011
给定一些游戏的初始状态,编写程序判断游戏者是否可能在 6
步以内使所有的灯都变亮。
数据范围
0 在这里插入图片描述

💡思路:
目标是将所有的数都变为1,当上一行的状态确定时,若上一行存在0,那么我们只能通过操作0去影响上一行的0.
(1)只要第一行的状态确定了,那么所有开关的状态就可以确定了,(显然我们直到下一行去改上一行,为什么还要枚举第一行的开关状态呢,其实是为了找到尽可能小的答案,我们把第一行的按法枚举一遍,每个位置都有两种选择,按(1)或者不按(0),遍历这32情况,然后取最小值 )
实现:

(1)只要第0行开关的状态确定,那么所有情况我们都可以推出来,因此枚举第一行操作的所有情况,总有32种情况,
(2)从第0行递推出第1到第4行的状态,若当前行状态已确定,且存在一个开关是0状态,则需要下一行的位置对开关进行切换,影响当前行开关是0的状态
(3)最后枚举最后一行,若该状态全部是1,则表示这种情况是可以的,更新最小步数


public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int n = 0;static int dx[] = {-1, 0, 1, 0, 0};static int dy[] = {0, 1, 0, -1, 0};static int[][]a = new int[10][10];static int[][]ca = new int[10][10];static int minn = 10;public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());while(n-- > 0) {minn = 10;for(int i = 0; i < 5; i++) {String line = br.readLine();for(int j = 0; j < 5; j++) {a[i][j] = line.charAt(j) - '0';ca[i][j] = a[i][j];}}if(n >= 1) {String blank = br.readLine();}for(int i = 0; i < (1 << 5); i++) {int step = 0;copy();for(int j = 0; j < 5; j++) {if(((i >> j) & 1) == 1) { //1代表按step++;turn(0,j); //改变(x,y)及其周围的}}for(int x = 0; x < 4; x++) {for(int y = 0; y < 5; y++) {if(a[x][y] == 0) {step++;turn(x + 1, y);}}}boolean ok = true;for(int j = 0; j < 5; j++) {if(a[4][j] == 0) {ok = false;break;}}if(ok) {minn = Math.min(minn,step);}}if(minn > 6) {out.println(-1);}else {out.println(minn);}out.flush();}}private static void turn(int x, int y) {for(int k = 0; k < 5; k++) {int nx = x + dx[k];int ny = y + dy[k];if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) {continue;}else {a[nx][ny] ^= 1;}}}private static void copy() {for(int i = 0; i < 5; i++) {for(int j = 0; j < 5; j++) {a[i][j] = ca[i][j];}}}
}

2.带分数(全排序/递归👍)

100 可以表示为带分数的形式:100=3+69258/714
还可以表示为:100=82+3546/197
注意特征:带分数中,数字 1∼9分别出现且只出现一次(不包含 0 )。
类似这样的带分数,100 有 11 种表示法。

输入格式:
一个正整数。

输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
(N<1e6)

💡思路:

只能说很巧妙,想到了其实很简单,想不到就没…
很显然,他说1-9种的数字每个数只能出现且只出现一次,我们可以枚举1-9的全排列,并用数组存下来每一位,对于每一种情况,为了表示此表达式的三部分,我们将全排列,通过i和j两个变量分为三段,然后计算是否满足给定的表达式即可(❗❗❗注意除法:防止出现小数,我们将其变为乘法,这种做法我们经常会用到

//全排列实现关键代码(经常使用)for(int i = 1; i <= 9; i++) {if(!vis[i]) {vis[i] = true;perm[u] = i;dfs(u + 1);vis[i] = false;}}

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int n = 0,ans = 0;static int[] perm = new int[20];static boolean[] vis = new boolean[20];public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());dfs(1);System.out.println(ans);}private static void dfs(int u) {if(u == 10) {for(int i = 1; i < 8;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(a*c + b == n*c) {ans++;}}}return;}for(int i = 1; i <= 9; i++) {if(!vis[i]) {vis[i] = true;perm[u] = i;dfs(u + 1);vis[i] = false;}}}private static int cal(int l, int r) {int res = 0;for(int i = l; i <= r; i++) {res = res * 10 + perm[i];}return res;}}

3.飞行员兄弟(位运算)

在这里插入图片描述

💡💡💡思路:
由于数据范围比较小,我们可以直接通过位运算进行二进制枚举,但是需要注意的是,借助二进制枚举的时候,我们只能枚举一维的,我们需要将0-15共16个位置映射到二维坐标(一般映射的时候,xy坐标从0开始比较方便映射),然后枚举所有答案,取得最小的值进行输出。
❗需要注意的是:
每次进行新的状态枚举的时候,我们需要从初始状态开始,所以一定不用忘记数组的拷贝和相关变量的初始化。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int n = 0,ans = 0,step = 0,minn = 0x3f3f3f3f;static String path = "",p = "";static int[] perm = new int[20];static boolean[][] vis = new boolean[10][10];static boolean[][] vis1 = new boolean[10][10];static int[][] a = new int[10][10];static int[][] ca = new int[10][10];public static void main(String[] args) throws Exception{for(int i = 0; i < 4; i++) {String str = br.readLine();for(int j = 0; j < 4; j++) {char ch = str.charAt(j);if(ch == '-') {a[i][j] = 0; //打开状态是0}else {a[i][j] = 1;}ca[i][j] = a[i][j];}}dfs();}private static void dfs() {for(int m = 0; m < (1 << 16); m++) {p = ""; step = 0;copy(a,ca);for(int i = 0; i < 16; i++) {  //将1代表需要操作,0代表不操作if(((m >> i) &1) == 1) { int x = i/4;int y = i%4;turn(x,y);p += (x + 1); p += (y + 1);step++;}}boolean ok = true;for(int i = 0; i < 4; i++) {for(int j = 0; j < 4; j++) {if(a[i][j] == 1) {ok = false;break;}}}if(ok) {if(step < minn) {minn = step;path = p;}}}System.out.println(minn);for(int i = 0; i < path.length();i++) {System.out.println(path.charAt(i) + " " + path.charAt(i + 1));i += 1;}}private static void copy(int[][] a, int[][] ca) {for(int i = 0; i < 4; i++) {for(int j = 0; j < 4; j++) {a[i][j] = ca[i][j];}}}private static void turn(int x, int y) {for(int i = 0; i < 4; i++) {a[i][y] ^= 1; }for(int i = 0; i < 4; i++) {a[x][i] ^= 1;}a[x][y] ^= 1;}}

4.翻硬币(贪心/递推❓)

在这里插入图片描述

思路:从前往后,将问题规模不断缩小,并且保证对所有需要翻转的棋子,只需要翻转一次,使得我们的操作保证操作次数最小。

ACcode:

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int n = 0,ans = 0;public static void main(String[] args) throws Exception{String str1 = "";String str2 = "";str1 = br.readLine();str2 = br.readLine();char[]s1 = str1.toCharArray();char[]s2 = str2.toCharArray();for(int i = 0; i < s1.length - 1; i++) {if(s1[i] != s2[i]) {ans++;if(s1[i] == '*') {s1[i] = 'o';}else {s1[i] = '*';}if(s1[i + 1] == '*') {s1[i + 1] = 'o';}else {s1[i + 1] = '*';}}}System.out.println(ans);}
}

5.递归实现指数型枚举

在这里插入图片描述
思路:直接递归实现选不选即可,注意需要回溯(即取消标记,恢复现场)


public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 20;static int n = 0,m = 0,ans = 0;static int[] a = new int[N];static boolean vis[] = new boolean[N];public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());dfs(1);}private static void dfs(int u) {if(u == n + 1) {for(int i = 1; i <= n; i++) {if(vis[i]) {System.out.print(i + " ");				}}System.out.println();return;}vis[u] = false;dfs(u + 1);vis[u] = true;dfs(u + 1);}
}

方法二:记住上次的结束,下次直接从后面开始

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 20;static int n = 0,m = 0,ans = 0, k = 0;static int[] a = new int[N];static int pos[] = new int[N];public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());k = Integer.parseInt(br.readLine());dfs(1,0);}private static void dfs(int u,int pre) {if(u == k + 1) {for(int i = 1; i <= k; i++) {System.out.print(pos[i] + " ");}System.out.println();return;}for(int i = pre + 1; i <= n; i++) {pos[u] = i;dfs(u + 1,i);}}
}

6.递归实现排列行枚举

在这里插入图片描述

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 20;static int n = 0,m = 0,ans = 0;static int[] a = new int[N];static boolean vis[] = new boolean[N];public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());dfs(1);}private static void dfs(int u) {if(u == n + 1) {for(int i = 1; i <= n; i++) {System.out.print(a[i] + " ");}System.out.println();return;}for(int i = 1; i <= n; i++) {if(!vis[i]) {vis[i] = true;a[u] = i;dfs(u + 1);vis[i] = false;}}}}

7.递归实现组合型枚举

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 30;static int n = 0,m = 0,ans = 0, k = 0;static int[] a = new int[N];static int pos[] = new int[N];public static void main(String[] args) throws Exception{String[]nm = br.readLine().split(" ");n = Integer.parseInt(nm[0]);k = Integer.parseInt(nm[1]);dfs(1,0);}private static void dfs(int u,int pre) {if(u == k + 1) {for(int i = 1; i <= k; i++) {System.out.print(pos[i] + " ");}System.out.println();return;}for(int i = pre + 1; i <= n; i++) {pos[u] = i;dfs(u + 1,i);}}
}

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播,要解决的几个问题是:1&...
Windows10添加群晖磁盘... 在使用群晖NAS时,我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章,在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
Fluent中创建监测点 1 概述某些仿真问题,需要创建监测点,用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装(Wind... 前言:刚换了一台电脑,里面所有东西都需要重新配置,习惯了所...
MFC文件操作  MFC提供了一个文件操作的基类CFile,这个类提供了一个没有缓存的二进制格式的磁盘...
有效的括号 一、题目 给定一个只包括 '(',')','{','}'...
【Ctfer训练计划】——(三... 作者名:Demo不是emo  主页面链接:主页传送门 创作初心ÿ...