我家小花儿

这个屌丝很懒，什么也没留下！

热门标签

递归与递推类型题小结_给定一个未排序的整数序列s和整数k,描述一个递归算法,用于对s中的元素重新排序,使

作者：我家小花儿 | 2024-05-16 11:56:52

踩

给定一个未排序的整数序列s和整数k,描述一个递归算法,用于对s中的元素重新排序,使

1. 递归

1.1 解题思想

一个问题可以分解成具有相同解决思路的子问题
使用递归方法解决问题时最好先画出递归树
经过层层分解的子问题最后一定是有一个不能再分解的固定值的（即终止条件），然后从叶子节点一层层返回结果，最终解决这个问题

1.2 例题1（指数型枚举）

92. 递归实现指数型枚举

题意：

输出一个集合的幂集所有元素

思路：

把输入的n当作有n个空位
每一个空位有两种状态，是否选取当前位置对应的值到集合中
递归实现：按顺序从头依次讨论每一个位置的选取情况，画出递归树

递归树模型：

标准的二叉树，每个分支表示选与不选

时间复杂度：

$O(2^n)$

代码实现：

class Main {
    BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    Scanner s = new Scanner(System.in);
    
    // 一共要考虑的位置总数
    int n;

    // 记录每一个位置的状态，0表示还没考虑到，1表示选它，2表示不选它
    int[] st;
    
    public void run() throws IOException {
        n = s.nextInt();
        st = new int[n + 1];

        // 从第一个位置开始考虑
        dfs(1);
		log.flush();
    }

    // i 表示当前考虑到第几个位置了
    private void dfs(int i) throws IOException {
        // 边界位置
        if (i > n) {
            for (int k = 1; k <= n; k++) {
                if (st[k] == 1) {
                    log.write(k + " ");
                }
            }
            log.write("\n");
            return;
        }
        // 当前位置不选
        st[i] = 2;
        // 考虑下一个位置
        dfs(i + 1);
        // 回溯到父节点时恢复现场
        st[i] = 0;

        // 当前位置要选
        st[i] = 1;
        // 考虑下一个位置
        dfs(i + 1);
        // 回溯到父节点时恢复现场
        st[i] = 0;
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
}
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

1.3 例题2（排列型枚举）

94. 递归实现排列型枚举

题意：

从小到大输出一个序列的全排列 $A_n^n$

思路：

把输入的n当作有n个空位
依次考虑每一个空位的取值(1~n)，由小到大取

递归树模型：

随着选取的数字增多，每一层节点的分支减1

时间复杂度分析：

第一层：1个节点执行一次for循环，O(n)
第二层：n个节点，每个节点都执行一次for循环，O(n*n)
第三层：n*(n-1)个节点，每个节点都执行一次for循环，O(n*(n-1)*n)
…
倒数第二层：n*(n-1)*(n-2)*… 2 个节点，同理，O(n*(n-1)*(n-2)* … *2*n)
最后一层：n!个节点，每个节点不用再执行一次for循环，但是需要输出数据，O(n!*n)

总复杂度： $O ((n * (1 + n * (n - 1) + n * (n - 1) * (n - 2) + . . . + n!)))$ ，大概为 $O (n * n!)$

代码实现：

class Main {
    BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    Scanner s = new Scanner(System.in);
    
    // 记录位置总数
    int n;
    
    // 记录位置状态，0表示还为考虑该位置，1~n表示该位置上的取值
    int[] state;
    
    // 记录对应数字是否使用过
    boolean[] used;
    
    public void run() throws Exception {
        n = s.nextInt();
        state = new int[n + 1];
        used = new boolean[n + 1];
        
        // 从第一个位置开始考虑
        dfs(1);
        
        log.flush();
    }
    
    public void dfs(int i) throws Exception {
        // 边界，即叶子节点的下一步，此时所有位置的取值已经考虑完毕
        if (i > n) {
            for (int k = 1; k <= n; k++) {
                log.write(state[k] + " ");
            }
            log.write('\n');
            return;
        }
        
        // 循环找到未使用过的最小数放到当前位置 (下一个节点的状态)
        for (int k = 1; k <= n; k++) {
        
            if (!used[k]) {
                // 在当前位置取值
                state[i] = k;  
                used[k] = true;
                
                // 考虑下一步取值
                dfs(i + 1);
                
                // 回溯到父节点时恢复现场
                state[i] = 0;
                used[k] = false;
            }
        }
    }
    
    public static void main(String[] args) throws Exception {new Main().run();}
}
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

1.4 习题1（组合型枚举）

93. 递归实现组合型枚举

题意：

输出一个序列的组合 $C_n^m$

思路：

把输入的m当作m个空位，输入的n为(1~n)数
从前往后开始依次考虑每个空位的取值(1~n)，后考虑的空位的值一定大于前一个空位

递归树模型：

从第二层的节点开始，从左到右每一个子树的所有节点依次递减

代码实现：

class Main {  
    Scanner s = new Scanner(System.in);
    BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));

    // 记录n个空位
    int n;
    // 记录m个需要选择的位置数量
    int m;
    // 方案
    int[] ways;
    // 当前位置最小能考虑到到数
    int start = 1;
    
    public void run() throws IOException {
        n = s.nextInt();
        m = s.nextInt();
        ways = new int[m + 1];

        dfs(1);
        log.flush();
    }

    private void dfs(int i) throws IOException {
		// 剪枝：还未考虑到到的空位数量 > 待选的数的个数 (无效枚举)
        if (m - i + 1 > n - start + 1) {
            return;
        }
		
        // 边界
        if (i > m) {
            // 扫描state
            for (int k = 1; k <= m; k++) {
                log.write(ways[k] + " ");
            }
            log.write('\n');
            return;
        }
        
        for (int k = start; k <= n; k++) {
            ways[i] = k;
            start = k + 1;
            dfs(i + 1);
            
            // 恢复现场
            ways[i] = 0;
            start = k;
        }
    }

    public static void main(String[] args) throws IOException {new Main().run(); }
}
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

1.5 习题2（带分数）

1209. 带分数

题意：

以 $n=a+\frac{b}{c}$ 的形式表示一个整数
其中a、b、c的每一位数字包含完1~9且不重复

思路：

暴力枚举出9个数的全排列，然后用一个数组保存（全排列搜索模型）
从全排列的结果中用两重循环暴力分解出三段，每段代表一个数
验证枚举出来的三个数是否满足题干条件，若满足则计数

public class Main {
    Scanner s = new Scanner(System.in);

    // 输入数
    int n;
    // 用来存全排列数
    int[] nums;
    // 用来判断哪些数使用过
    boolean[] used;
    int a, b, c;
    // 计数
    int cnt;

    public void run() {
        n = s.nextInt();
        nums = new int[10];
        used = new boolean[10];

        dfs(1);
        System.out.println(cnt);
        
    }

    public void dfs(int i) {
        // 边界
        if (i > 9) {
            
            // 对每一种排列进行枚举分段
            for (int x = 1; x <= 7; x++) {
                for (int y = x + 1; y <= 8; y++) {
                    a = subNums(1, x);
                    b = subNums(x + 1, y);
                    c = subNums(y + 1, 9);
                    
                    // 对符合条件对数进行计数
                    if (n * c == a * c + b) cnt++;
                }
            }
            return;
        }
        
        // 全排列搜索模型
        for (int k = 1; k <= 9; k++) {
            if (!used[k]) {
                nums[i] = k;
                used[k] = true;

                dfs(i + 1);

                nums[i] = 0;
                used[k] = false;
            }
        }
    }
    
    // 求每一段的数字
    private int subNums(int l, int r) {
        int num = 0;
        for (int i = l; i <= r; i++) {
            num = num * 10 + nums[i];
        }
        return num;
    }


    public static void main(String[] args) {
        new Main().run();
    }
}
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

2. 递推

2.1 解题思路：

首先找到题目的递推式子
与递归不同的是，递推解决子问题是从头开始

2.2 例题1（简单斐波那契）

简单斐波那契

思路：

递推式子：f(n) = f(n - 1) + f(n - 2)
初始化一个数组前两项为0、1
根据递推式子从第三行开始递推

class Main {
    BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    Scanner s = new Scanner(System.in);
    
    // 斐波那契的前n项
    int n;
    
    // 递推式子
    int[] f;
    
    public void run() throws Exception {
        n = s.nextInt();
        f = new int[46];
        
        // 初始化
        f[1] = 0;
        f[2] = 1;
        
        // 从前到后递推
        for (int i = 3; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        
        for (int i = 1; i <= n; i++) {
            log.write(f[i] + " ");
        }
        
        log.flush();
    }
    
    public static void main(String[] args) throws Exception {new Main().run();}
}
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

2.3 例题2（费解的开关）

95. 费解的开关

题意：

给定一个5x5的方格，共25盏灯
每盏灯有开和关两种状态
每次操作一盏灯时，以该灯为中心的十字形状范围的灯都会改变状态
找到用最少的操作步数使所有的灯都亮着，当步数超过6时返回-1

思路：

枚举出对第一行的所有操作情况（指数类型枚举模型），注意这里不是枚举第一行的灯的状态
根据推导可知：当第一行操作完毕确认完的状态后，后面除了最后一行的每一行操作就已经确定了，即必须在上一行关灯的下方一个位置进行状态变化
当操作到最后一行到时候，前面的n-1行已经全亮
最后只需要特判一下最后一个行的状态，只要有一个不亮，则说明第一行的本次操作情况无效



import java.util.*;
import java.io.*;
class Main {
    Scanner s = new Scanner(System.in);
    
    // 矩阵数量
    int n;
    
    // 输入的每一行
    String line;
    
    // char数组
    char[][] g;
    
    public void run() {
        n = s.nextInt();
        g = new char[5][5];
        
        while(n-- > 0) {
            // 填充数组
            for (int i = 0; i < 5; i++) {
                line = s.next();
                for (int j = 0; j < 5; j++) {
                    g[i][j] = line.charAt(j);
                }
            }
            
            // 输出每次输入的g的ans
            minStep(g);
        }
    }
    
    public void minStep(char[][] c) {
        
        // 输入数组的替身
        char[][] backup = new char[5][5];
        
        for (int k = 0; k < 5; k++) {
            System.arraycopy(c[k], 0, backup[k], 0, 5);
        }
        
        
        int ans = 7;
        
        // 先枚举出第一行的所有操作情况
        for (int op = 0; op < 32; op++) {
            
            // 每次op让step归0
            int step = 0;
            
            // 二进制数中对数字为1的位置进行翻转 
            for (int i = 0; i < 5; i++) {
                if ((op >> i & 1) == 1) {
                    turn(backup, 0, i);
                    step++;
                }
            }
            
            // 从第一行到第四行开始扫描
            for (int i = 0; i < 4; i++) {
                
                for (int j = 0; j < 5; j++) {
                    // 如果当前行的当前列元素为0则对下一行对应位置进行翻转
                    if (backup[i][j] == '0') {
                        turn(backup, i + 1, j); 
                        step++;
                    }
                }
            }
            
            boolean bright = true;
            
            // 扫描最后一行元素，判断其是否全为1
            for (int i = 0; i < 5; i++) {
                if(backup[4][i] != '1') {
                    bright = false;
                }
            }
            
            // 如果最后一行全亮，则本次op有效，与前一次的移动步数比较，以至于所有op结束后找到最小值
            if (bright) {
                ans = Math.min(ans, step);
            }
            
            // 恢复替身改变之前的状态
            for (int k = 0; k < 5; k++) {
                System.arraycopy(c[k], 0, backup[k], 0, 5);
            }
        }
        
        // 判断最小步数是否大于6，如果大于6则返回-1
        if(ans > 6) ans = -1;
        System.out.println(ans);
    }
    
    // 关于(x, y)的5个点偏移量
    int[] dx = {-1, 0, 1, 0, 0};
    int[] dy = {0, 1, 0, -1, 0};
    
    public void turn(char[][] c, int x, int y) {
        
        for (int i = 0; i < 5; i++) {
            // (a, b)为(x, y)附加对应偏移量的点
            int a = x + dx[i];
            int b = y + dy[i];
            
            // 判断一下边界，如果越界，这该点无效，不需要翻转
            if (a < 0 || a >=5 || b < 0 || b >= 5) continue;
            
            // 对该点进行翻转
            c[a][b] = c[a][b] == '1' ? '0' : '1';
        }
    }
    
    public static  void main(String[] args) {new Main().run();}
}
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/578643

递归与递推类型题小结_给定一个未排序的整数序列s和整数k,描述一个递归算法,用于对s中的元素重新排序,使

文章目录

1. 递归

1.1 解题思想

1.2 例题1（指数型枚举）

题意：

思路：

递归树模型：

时间复杂度：

代码实现：

1.3 例题2（排列型枚举）

题意：

思路：

递归树模型：

时间复杂度分析：

代码实现：

1.4 习题1（组合型枚举）

题意：

思路：

递归树模型：

代码实现：

1.5 习题2（带分数）

题意：

思路：

2. 递推

2.1 解题思路：

2.2 例题1（简单斐波那契）

思路：

2.3 例题2（费解的开关）

题意：

思路：