蓝桥杯学习-13回溯

13回溯

一、回溯1

例题1–递归实现分列型摆列-蓝桥19684

1. 1.递归可以解决不定次数的循环问题
2. 2.使用数组来标记数字是否被选过

复制代码

1. import java.util.Scanner;
3. public class Main {
4.     static int n;
5.     static boolean[] st = new boolean[10];  //判断数字是否被选过
6.     static int[] path = new int[10];  //存储排列组合
7.     //递归程序
8.     public static void dfs(int u){
9.         if(u > n){
10.             //递归结束的条件，递归结束就输出结果。（但这里其实是针对每一次的排序而言）
11.             for (int i = 1; i <= n; i++) {
12.                 System.out.print(path[i] + " ");
13.             }
14.             System.out.println();
15.             return;
16.         }
17.         //递归--循环排列组合
18.         for (int i = 1; i <= n ; i++) {
19.             if(st[i]) continue;
20.             st[i] = true;//选中
21.             path[u] = i;  //记录
22.             dfs(u + 1);  //下一个数的循环
23.             st[i] = false;  //解除
24.         }
25.     }
26.     public static void main(String[] args) {
27.         Scanner sc = new Scanner(System.in);
28.         n = sc.nextInt();
29.         dfs(1);
30. /*        for (int i = 1; i <= n ; i++) {
31.             st[i] = true;
32.             for (int j = 1; j <= n ; j++) {
33. //                if(j == i) continue;
34.                 if(st[j]) continue;
35.                 st[j] = true;
36.                 for (int k = 1; k <= n ; k++) {
37. //                    if (k == i || k ==j) continue;
38.                     if(st[k]) continue;
39.                     System.out.println(i+ "," + j + "," + k);
40.                 }
41.                     st[j] = false;
42.             }
43.                 st[i] = false;
44.         }*/
45.     }
46. }

复制代码

*特别留意！！！

效果对但是没有通过用例，缘故原由是输出的格式题目！各个数之间要用空格隔开！这点特别必要留意。
例题2–串变动蓝桥4360

1. 对k个操作进行全排列。以及k--的排列，直到可以变为T串，或循环到最后都变不了

复制代码

例题3–带分数蓝桥208

回溯+摆列

1. 思路，1-9出现且只出现1次，进行9的全排列，把9个数的所有组合排列出来，再把加号和除号放进去，看看哪些符合条件

复制代码

1. import java.util.*;
3. public class Main {
4.     static int N;
5.     static int count = 0;
6.     //static List<String> permutations = new ArrayList<>();
8.     public static void main(String[] args) {
9.         Scanner sc = new Scanner(System.in);
10.         N = sc.nextInt();
11.         sc.close();
13.         // 生成1~9的所有排列
14.         permute("123456789", 0, 8);
15.         System.out.println(count);
16.     }
18.     // 生成全排列
19.     public static void permute(String str, int l, int r) {
20.         if (l == r) {
21.             //permutations.add(str);
22.             check(str);
23.         } else {
24.             for (int i = l; i <= r; i++) {
25.                 str = swap(str, l, i);
27.                 permute(str, l + 1, r);
29.                 str = swap(str, l, i);
31. // 回溯
32.             }
33.         }
34.     }
36.     // 检查所有的加号和除号位置
37.     public static void check(String str) {
38.         for (int i = 1; i <= 7; i++) {  // 加号位置，要大于0
39.             for (int j = i + 1; j <= 8; j++) {  // 除号位置，在加号的右边
40.                 int A = Integer.parseInt(str.substring(0, i));
41.                 int B = Integer.parseInt(str.substring(i, j));
42.                 int C = Integer.parseInt(str.substring(j));
43.                
44.                 // 避免除0错误
45.                 if (C == 0) continue;
46.                
47.                 // 判断是否符合 A + B / C = N
48.                 if (A + (double) B / C == N) {
49.                     count++;
50.                 }
51.             }
52.         }
53.     }
55.     // 字符串交换工具方法
56.     public static String swap(String str, int i, int j) {
57.         char[] charArray = str.toCharArray();
58.         char temp = charArray[i];
59.         charArray[i] = charArray[j];
60.         charArray[j] = temp;
61.         return new String(charArray);
62.     }
63. }

复制代码

1. 1234
2. 1243
3. 1324
4. 1342
5. 1432
6. 1423
7. 2134
8. 2143
9. 2314
10. 2341
11. 2431
12. 2413
13. 3214
14. 3241
15. 3124
16. 3142
17. 3412
18. 3421
19. 4231
20. 4213
21. 4321
22. 4312
23. 4132
24. 4123

复制代码

明确回溯中的关键利用

1. str = swap(str, l, i);

复制代码

• 做选择：互换当前元素和 i 位置的元素，相当于实验将 i 放在当前的位置。
  

1. permute(str, l + 1, r);

复制代码

• 递归调用：继续处置惩罚反面的数字，进入下一层。
  

1. str = swap(str, l, i);

复制代码

• 打消选择：把字符串规复到原来的状态，确保不影响下一次的实验。
  
• 这是 回溯的英华：探索完一条路径后，将状态规复，以便继续探索其他路径。
  

发起：用树状图画出回溯的实行过程，一步步明确状态的厘革。

几道回溯小题

二、回溯2

例题–N皇后题目蓝桥1508

标题要求也不允许处在与棋盘边框成 45 角的斜线上。（留意与棋盘边框）
主对角线

副对角线

暴力做法

1. 假设n=4，进行4次循环的嵌套，每一次代表的是每一行棋子的位置。

复制代码

1. public class Main {
2.     static int N = 30;
3.     //行row，列col，主对角线zhu，副对角线fu
4.     static boolean[] row = new boolean[N];
5.     static boolean[] col = new boolean[N];
6.     static boolean[] zhu = new boolean[N];
7.     static boolean[] fu = new boolean[N];
8.     public static void main(String[] args){
9.         int ans = 0;//记录
10.         //一个for表示一行
11.         for (int i = 1; i <= N; i++) {//尝试第1个棋子
12.             int x1 = 1,y1 = i;//行//列
13.             //被选中了就为true
14.             row[x1] = true;
15.             col[y1] = true;
16.             zhu[N - y1 + x1] = true;
17.             fu[x1 + y1] = true;
18.             for (int j = 1; j <= N; j++) {//尝试第2个棋子
19.                 int x2 = 2,y2 = j;//行//列
20.                 //不符合规则的就跳过
21.                 if(row[x2] || col[y2] || zhu[N - y2 + x2] || fu[x2 + y2]) continue;
22.                 //被选中了就为true
23.                 row[x2] = true;
24.                 col[y2] = true;
25.                 zhu[N - y2 + x2] = true;
26.                 fu[x2 + y2] = true;
27.                 for (int k = 1; k <= N; k++) {//尝试第3个棋子
28.                     //同样
29.                     for (int l = 1; l <= N; l++) {//尝试第4个棋子
30.                         //同样，顺便ans加加
32.                     }
33.                 }
34.                 //结束要释放//回溯
35.                 row[x2] = false;
36.                 col[y2] = false;
37.                 zhu[N - y2 + x2] = false;
38.                 fu[x2 + y2] = false;
39.             }
40.             //结束要释放//回溯
41.             row[x1] = false;
42.             col[y1] = false;
43.             zhu[N - y1 + x1] = false;
44.             fu[x1 + y1] = false;
45.         }
46.     }
47. }

复制代码

着实上面的row数组是没须要的，由于循环的就是行数，按行数来的。
dfs递归做法

1. import java.util.Scanner;
3. //TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
4. // click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
5. public class Main {
6.     static int ans;
7.     static int n;
8.     static int N = 30;
9.     //行row，列col，主对角线zhu，副对角线fu
10.     //static boolean[] row = new boolean[N];
11.     static boolean[] col = new boolean[N];
12.     static boolean[] zhu = new boolean[N];
13.     static boolean[] fu = new boolean[N];
14.     //递归函数
15.     public static void dfs(int u){
16.         if(u > n){
17.             //循环到最后
18.             ans++;
19.             return;
20.         }
21.         for (int i = 1; i <= n; i++) {
22.             //这表示每一行循环每一列,因此i表示的是列数，u表示的是行数
23.             //首先判断是否被占用
24.             if(col[i] || zhu[n - i + u] || fu[u + i])  continue;
25.             //选中一个数
26.             col[i] = true;
27.             zhu[n - i + u] = true;
28.             fu[u + i] = true;
29.             //递归下一行
30.             dfs(u + 1);
31.             //回溯
32.             col[i] = false;
33.             zhu[n - i + u] = false;
34.             fu[u + i] = false;
35.         }
36.     }
37.     //主逻辑函数
38.     public static void solve(){
39.         //输入N
40.         Scanner sc = new Scanner(System.in);
41.         n = sc.nextInt();
42.         //调用
43.         dfs(1);
44.         System.out.println(ans);
45.     }
46.     public static void main(String[] args) {
47.         solve();
48.     }
49. }

复制代码

1. 学到的知识点：
2. 1.难点：本题要求不能在同一行，同一列和与棋盘边框成45度角。
3. 45度角这个需要找规律。
4. 把这些情况都转换为设为一个布尔数组，来判断是否被放置。true--被放置，false--没有。
5. 2.学习到的递归知识：
6. 首先，设n为4，进行一个暴力的做法。
7. 就是遍历每一行，对于每一行，判断某个位置是否符合条件（1中的条件）。
8. 符合条件后，设定其被放置，进行下一层遍历。否则continue。
9. 对于一次找到合法的放置位置后，需要将位置进行释放--这就是回溯。
11. 因此，将暴力的做法转为递归，就容易了。
12. 找到一个合法的放置位置（u>x后），ans++；
13. 递归函数中，为每一行的遍历。
14. 一行遍历完后进行下一行的递归（dfs(u + 1)）;
15. 下面几行回溯。

复制代码

写完代码看完视频又忘记思绪，不好说。只可意会。
三、回溯3-子集摆列（递归实现指数型摆列）

1. 一旦涉及选与不选，删和不删，留和不留-->两种状态-->就要想到子集枚举

复制代码

例题1–递归实现指数型摆列19685

1. 其实看不懂这个题目，好奇怪的题目。根据老师的解析来写。
2. 大致理解为从1-n中，输出所有的组合数就对了。
3. 我知道了，就是要按照题目的要求来，要先判断0不选，再判断1选。具体看代码更了解。

复制代码

暴力做法

假设n=3.

1. public class Main {
2.     static int[] st = new int[10];
3.     //主逻辑函数
4.     public static void solve(){
5.         int n = 3;
6.         for (int i = 0; i <=1; i++) {//表示选或不选
7.             st[1] = i;
8.             for (int j = 0; j <= 1; j++) {//表示选或不选
9.                 st[2] = j;
10.                 for (int k = 0; k <= 1; k++) {//表示选或不选
11.                     st[3] = k;
12.                     for (int l = 1; l <= 3; l++) {
13.                         //选中的输出
14.                         if(st[l] == 1) System.out.print(l);
15.                     }
16.                     System.out.println();
17.                 }
18.             }
19.         }
20.     }
21.     public static void main(String[] args) {
22.         solve();
23.     }
24. }

复制代码

使用回溯dfs来实现

1. import java.util.Scanner;
3. //TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
4. // click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
5. public class Main {
6.     static int n;
7.     static int[] st = new int[20];
8.     //递归函数
9.     public static void dfs(int u){
10.         if(u > n){
11.             //一次结束，输出结果
12.             for (int l = 1; l <= n; l++) {
13.                 //选中的输出
14.                 if(st[l] == 1) System.out.print(l + " ");
15.             }
16.             System.out.println();
17.             return;//这里要返回，因为？
18.         }
19.         for (int i = 0; i <= 1; i++) {
20.             st[u] = i;
21.             dfs(u + 1);//下一个数选或不选
22.         }
23.     }
24.     //主逻辑函数
25.     public static void solve(){
26.         Scanner sc = new Scanner(System.in);
27.         n = sc.nextInt();
28.         dfs(1);
29. //        for (int i = 0; i <=1; i++) {//表示选或不选
30. //            st[1] = i;
31. //            for (int j = 0; j <= 1; j++) {//表示选或不选
32. //                st[2] = j;
33. //                for (int k = 0; k <= 1; k++) {//表示选或不选
34. //                    st[3] = k;
35. //                    for (int l = 1; l <= 3; l++) {
36. //                        //选中的输出
37. //                        if(st[l] == 1) System.out.print(l);
38. //                    }
39. //                    System.out.println();
40. //                }
41. //            }
42. //        }
43.     }
44.     public static void main(String[] args) {
45.         solve();
46.     }
47. }

复制代码

1. 特别注意输出的格式问题，空格或者逗号特别注意，总因为这个没通过！！！

复制代码

例题2–19880
例题3–蛋糕的鲜味值8664

1. package huisu;
3. import java.util.Scanner;
5. public class TasteCake {
6.     static int[] cake = new int[30];
7.     static int[] st = new int[30];
8.     static int n,k;
9.     static int max;
11.     //获得最大的总和
12.     public static void getMax(){
13.         int sum = 0;
14.         for (int i = 1; i <= n; i++) {
15.             if(st[i] == 1){
16.                 //被选中并且美味值小于k
17.                 sum += cake[i];
18.             }
19.         }
20.         //结束后返回目前最大值
21.         if(sum < k){
22.             max = Math.max(sum,max);
23.         }
24.     }
25.     //递归
26.     public static void dfs(int u){//u表示第几个蛋糕
27.         if(u > n){
28.             //表示n个蛋糕选与不选完了
29.             getMax();
30.             return;
31.         }
32.         for (int i = 0; i <= 1; i++) {//选与不选
33.             st[u] = i;
34.             dfs(u + 1);//下一个蛋糕
35.         }
36.     }
37.     //主逻辑函数
38.     public static void solve(){
39.         Scanner sc = new Scanner(System.in);
40.         //输入n，k
41.         n = sc.nextInt();
42.         k = sc.nextInt();
43.         //输入蛋糕的美味值
44.         for (int i = 1; i <= n; i++) {
45.             cake[i] = sc.nextInt();
46.         }
47.         //递归
48.         dfs(1);
49.         //输出结果
50.         System.out.println(max);
51.     }
52.     public static void main(String[] args) {
53.         solve();
54.     }
55. }

复制代码

1. 注意：
2. 一定要看清题目啊，看题目和观察样例。
3. 这里是要选出的蛋糕的总值小于k，而不是选出的每一个小于k的。
4. 我第一次写理解为后面那一种，就错了。
5. 其实看样例也能看出来。
6. 题目真难理解。。。

复制代码

例题4–luoguP1036
头脑

1. 老师说只需要思考最后两层的递归，其他层的递归其实就和最后两层一样
2. 对于选与不选的递归问题，事件复杂度都是2^n，对于n<=25的都可以运行

复制代码