第一讲 递归与递推

递归实现排列型枚举

题目

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

输入格式
一个整数n。

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

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

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

数据范围
1≤n≤9
输入样例:

1
3

输出样例:

1
2
3
4
5
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

思路

这个题实际上就是对1-n进行全排列。

现在可以想象有n个位置,一个位置只可以放入一个数字(1-n)。

从第一个位置开始枚举每一个数字,当一个位置放入数字后就递归下一个位置的放置情况。直到所有情况处理完。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

static ArrayList<Integer> ay = new ArrayList<Integer>();
static int[] visit = new int[10];
static int n = 0;
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static void dfs(int v) throws Exception {
if(v == n) {
for(int i : ay) {
out.write(i + " ");
}
out.write('\n');
}
for(int i = 1; i <= n; i++) {
if(visit[i] == 0) {
ay.add(i);
visit[i] = 1;
dfs(v + 1);
ay.remove(ay.size() - 1);
visit[i] = 0;
}
}
}
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
dfs(0);
out.flush();
}
}

递归实现指数型枚举

题目

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

输入格式
输入一个整数n。

输出格式
每行输出一种方案。

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

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

本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。

数据范围
1≤n≤15
输入样例:

1
3

输出样例:

1
2
3
4
5
6
7
3
2
2 3
1
1 3
1 2
1 2 3

思路

这个题目思路大致与上一题相同,要注意的是对于每一组答案,前面的数字必须小于后面的数字。可以发现,在递归函数中循环遍历1-n,那么循环起始值以上一次取得的数值加1就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

static ArrayList<Integer> ay = new ArrayList<Integer>();
static int[] visit = new int[16];
static int n = 0;
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static void dfs(int v,int p) throws Exception{
if(v == p) {
for(int i : ay) {
out.write(i + " ");
}
out.write('\n');
}

for(int i = n; i >= 1; i--) {
if(visit[i] == 0) {
if(!ay.isEmpty() && ay.get(ay.size() - 1) > i) {
return;
}
ay.add(i);
visit[i] = 1;
dfs(v,p + 1);
ay.remove(ay.size() - 1);
visit[i] = 0;
}
}
}
public static void main(String[] args) throws Exception {
out.write('\n');
Scanner sc = new Scanner(System.in);
n = sc.nextInt();

for(int i = 1; i <= n; i++) {
dfs(i,0);
}
out.flush();
}

}

费解的开关

题目

你玩过“拉灯”游戏吗?25盏灯排成一个5x5的方形。每一个灯都有一个开关,游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。

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

1
2
3
4
5
10111
01101
10111
10000
11011

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

1
2
3
4
5
01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成:

1
2
3
4
5
01111
11001
11001
10100
11011

给定一些游戏的初始状态,编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。

输入格式

第一行输入正整数n,代表数据中共有n个待解决的游戏初始状态。

以下若干行数据分为n组,每组数据有5行,每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。

输出格式

一共输出n行数据,每行有一个小于等于6的整数,它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态,若6步以内无法使所有灯变亮,则输出“-1”。

数据范围
0<n≤500
输入样例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例:

1
2
3
3
2
-1

思路

对于这种开灯关灯问题(改变一个位置的状态会影响其它位置的状态)或许可以发现这样一种现象,那就是按一下再按一下相当于没有按

可以推出来,每一个位置最多可以按一下。

现在来模拟一下状态。

对于第一行的开关,如果有一个开关处于关的状态,那么能影响到这个开关的只能是它左边、右边、下边的开关。而像前面提到的每个开关只能按一次,当第一行的开关前面4个都处于开的状态,第5个处于关的状态,那么能影响到它的只能是它下面的开关,因为左边开关一旦按下势必会影响前面已经处理好的开关,而右边又没有开关了。

此时就可以设定当第一行的开关处于关的状态,就按一下它下面的开关来改变它的状态。

这样,对于第二行来说,第三行开关决定它的开关状态,以此类推。

此时,就可以枚举第一行开关的所有情况,有了第一行开关的状态,就可以推出来整个开关矩阵的情况。

求出最小步骤数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Acwing95 {

static int n;
static final int MAXN = 10;
static int[][] mg = new int[MAXN][MAXN];
static int ans = Integer.MAX_VALUE;
static int[][] tp = new int[MAXN][MAXN];

private static void inverse(int[][] ay,int i,int v) {
ay[i][v] = (ay[i][v] + 1) % 2;

ay[i][v - 1] = (ay[i][v - 1] + 1) % 2;
ay[i][v + 1] = (ay[i][v + 1] + 1) % 2;
ay[i + 1][v] = (ay[i + 1][v] + 1) % 2;
ay[i - 1][v] = (ay[i - 1][v] + 1) % 2;
}

private static int check() {
int p = 0;
for(int i = 1; i <= 5; i++) {
for(int j = 1; j <= 5; j++) {
tp[i][j] = mg[i][j];
}
}

for(int i = 2; i <= 5; i++) {
for(int j = 1; j <= 5; j++) {
if(tp[i - 1][j] == 0) {
inverse(tp,i,j);
p++;
}
}
}

for(int i = 1; i <= 5; i++) {
if(tp[5][i] == 0) {
return -1;
}
}
return p;
}
public static void dfs(int v,int p) {
if(v == 6) {
int cnt = check();
if(cnt == -1) {
return;
}
ans = Math.min(ans, cnt + p);
return;
}
dfs(v + 1,p);
inverse(mg,1,v);
dfs(v + 1,p + 1);
inverse(mg,1,v);
}
public static void main(String[] args) throws Exception{

Scanner sc = new Scanner(System.in);
n = sc.nextInt();
while(n-- > 0) {
ans = Integer.MAX_VALUE;
for(int i = 1; i <= 5; i++) {
String line = sc.next();
for(int j = 0; j < line.length(); j++) {
mg[i][j + 1] = (int)line.charAt(j) - 48;
}
}

dfs(1,0);
if(ans == Integer.MAX_VALUE || ans > 6) {
ans = -1;
}
System.out.println(ans);
}
}

}

递归实现组合型枚举

题目

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

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

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

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

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

数据范围
n>0 ,
0≤m≤n ,
n+(n−m)≤25
输入样例:

1
5 3

输出样例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
1 2 3 
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
```
## 思路
与全排列做法类似。指定递归函数出口为规定的数即可。
## 代码
```Java
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

static int n,m;
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static ArrayList<Integer> ay = new ArrayList<Integer>();
static int[] visit = new int[30];

public static void dfs(int v,int state) throws Exception{
if(v == m) {
for(int i : ay) {
out.write(i + " ");
}
out.write('\n');
}

for(int i = state + 1; i <= n; i++) {
if(visit[i] == 0) {
ay.add(i);
visit[i] = 1;
dfs(v + 1, i);
ay.remove(ay.size() - 1);
visit[i] = 0;
}
}
}

public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();

dfs(0,0);

out.flush();
}

}

带分数

题目

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

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

输入格式
一个正整数。

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

数据范围
1≤N<10^6

输入样例1:

1
100

输出样例1:

1
11

输入样例2:

1
105

输出样例2:

1
6

思路

这个题目要求1-9数字使用并且仅使用一次。

把a、b、c三个数字当成字符串连接到一起,即是一组答案。可以发现,对于每一个由1-9数字组成的字符串都可以对其进行拆分,之后判断是否可以构成n。

枚举字符串(即求全排列1-9),对于每一个字符串进行拆分,分成三部分,将这三部分换成整数,判断等式(n - a) * c = b(由n=a+b/c推导得来)是否成立。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.Scanner;

public class Acwing1209 {

static long n;
static String line = "";
static int[] visit = new int[10];
static int ans = 0;

private static long toLong(String str) {
long value = 0;
for(int i = 0; i < str.length(); i++) {
value = value * 10 + (int)str.charAt(i) - 48;
}
return value;
}
private static void check() {
for(int i = 1; i <= 9; i++) {
for(int j = 1; j <= 9; j++) {
int t = 9 - i - j;
if(t <= 0) {
break;
}
long a = toLong(line.substring(0, i));
long b = toLong(line.substring(i,i + j));
long c = toLong(line.substring(i + j));
if((n - a) * c == b) {
ans++;
return;
}
}
}
}
public static void dfs(int v) {
if(v == 9) {
check();
}
for(int i = 1; i <= 9; i++) {
if(visit[i] == 0) {
line += i;
visit[i] = 1;
dfs(v + 1);
visit[i] = 0;
line = line.substring(0, line.length() - 1);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextLong();
dfs(0);
System.out.println(ans);
}
}

翻硬币

题目

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写字母,不是零)。

比如,可能情形是:oo*oooo

如果同时翻转左边的两个硬币,则变为:oooo***oooo

现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个硬币,那么对特定的局面,最少要翻动多少次呢?

我们约定:把翻动相邻的两个硬币叫做一步操作。

输入格式
两行等长的字符串,分别表示初始状态和要达到的目标状态。

输出格式
一个整数,表示最小操作步数

数据范围
输入字符串的长度均不超过100。
数据保证答案一定有解。

输入样例1:

1
2
**********
o****o****

输出样例1:

1
5

输入样例2:

1
2
*o**o***o***
*o***o**o***

输出样例2:

1
1

思路

类似于开灯问题。

可以发现,对于一个硬币来说,翻两次相当于没翻,也就是说,一个硬币最多只能翻一次。

对于最左边的硬币:能影响它状态的只有它自己和它右边第一个硬币。如果某一时刻它翻动一次,它自己和它右边的硬币状态改变。此时,对第二个硬币来讲,就不能翻动它自身,能影响它的只有它右边的硬币,以此类推,后边的硬币只能被它后一位影响。

这样就好办了,对比目标串做出相应变化就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.Scanner;

public class Main {

static String src = "";
static String des = "";
static int ans = Integer.MAX_VALUE;
static int len = 0;

private static int check() {
int p = 0;

String str = src;

for(int i = 0; i < len; i++) {
if(des.charAt(i) != str.charAt(i)) {
str = inverse(str,i);
p++;
}
}

if(!des.equals(str)) {
p = -1;
}
return p;
}

private static String inverse(String str,int index) {
if(index == len) {
return str;
}

char[] ch = str.toCharArray();
if(ch[index] == '*') {
ch[index] = 'o';
}
else {
ch[index] = '*';
}

if(ch[index + 1] == '*') {
ch[index + 1] = 'o';
}
else {
ch[index + 1] = '*';
}
return str = new String(ch);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
src = sc.next();
len = src.length();

des = sc.next();
int cnt = check();
System.out.println(cnt);
sc.close();
}
}

飞行员兄弟

题目

“飞行员兄弟”这个游戏,需要玩家顺利的打开一个拥有16个把手的冰箱。

已知每个把手可以处于以下两种状态之一:打开或关闭。

只有当所有把手都打开时,冰箱才会打开。

把手可以表示为一个4х4的矩阵,您可以改变任何一个位置[i,j]上把手的状态。

但是,这也会使得第i行和第j列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式
输入一共包含四行,每行包含四个把手的初始状态。

符号“+”表示把手处于闭合状态,而符号“-”表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。

输出格式
第一行输出一个整数N,表示所需的最小切换把手次数。

接下来N行描述切换顺序,每行输入两个整数,代表被切换状态的把手的行号和列号,数字之间用空格隔开。

注意:如果存在多种打开冰箱的方式,则按照优先级整体从上到下,同行从左到右打开。

数据范围
1≤i,j≤4
输入样例:

1
2
3
4
-+--
----
----
-+--

输出样例:

1
2
3
4
5
6
7
6
1 1
1 3
1 4
4 1
4 3
4 4

思路

对于每一个把手,都有两种状态,一个是开,一个是关。枚举所有的状态,对每种状态判断是不是全打开就行了。

注意,题目要求将改变的把手位置打印出来并且有顺序要求,那么只需要从最后往前面递归就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Scanner;

class Node {
int x,y;
Node(int x,int y) {
this.x = x;
this.y = y;
}
}
public class Main {

static int[][] mg = new int[5][5];
static int ans = Integer.MAX_VALUE;
static Deque<Node> stack = new ArrayDeque<Node>();

static ArrayList<Node> ay = new ArrayList<Node>();
static ArrayList<Node> cur = new ArrayList<Node>();

private static boolean check() {
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
if(mg[i][j] == 1) {
return false;
}
}
}
return true;
}
private static void inverse(int x,int y) {
for(int i = 0; i < 4; i++) {
if(i != y) {
mg[x][i] = (mg[x][i] + 1) % 2;
}
}

for(int i = 0; i < 4; i++) {
if(i != x) {
mg[i][y] = (mg[i][y] + 1) % 2;
}
}

mg[x][y] = (mg[x][y] + 1) % 2;
}
private static void judge(int p) {
if(p <= ans) {
ans = p;
ay.clear();
for(Node node : cur) {
ay.add(node);
}
}
}
public static void dfs(int v,int p) {

if(v == -1) {
if(check()) {
judge(p);
}
return;
}
int x = v / 4;
int y = v % 4;

dfs(v - 1,p);

inverse(x,y);
cur.add(new Node(x + 1,y + 1));
dfs(v - 1,p + 1);
cur.remove(cur.size() - 1);
inverse(x,y);

}
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 < line.length(); j++) {
if(line.charAt(j) == '+') {
mg[i][j] = 1;
}
else {
mg[i][j] = 0;
}
}
}

dfs(15,0);

System.out.println(ans);
for(int i = ay.size() - 1; i >= 0; i--) {
System.out.println(ay.get(i).x + " " + ay.get(i).y);
}
}

}
-------------本文结束感谢您的阅读-------------
0%