「蓝桥杯」
蓝桥杯系列文章目录
- [ ★] 第一讲 递推与递归
题目目录：
- [ ★] 第一讲 递推与递归
-
- [ ★] 第一题 DFS下的全排列（一题带你搞懂全排列，下面第二种方法作为福利提供给大家，仅此模版，一次搞定全排列）
-
- [ ★] 第一讲 递推与递归（一题带你入门开关问题）
我的核心技术者社区
诚邀各位技术爱好者，在本社区，我会尽全力给大家提供一个友好的交流平台。欢迎各位技术爱好者加入。
链接：
https://bbs.csdn.net/forums/CoreTechnologyProvider_TheOne?category=0一、DFS下的全排列
把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。输入格式一个整数 n。输出格式按照从小到大的顺序输出所有方案，每行 1 个。首先，同一行相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。数据范围1≤n≤9输入样例：3输出样例：1 2 31 3 22 1 32 3 13 1 23 2 1第一题代码如下：
C++版本1.0
#includeusing namespace std;const int N = 10;int state[N];bool used[N];int n;void dfs(int u)//u代表当前位置{if (u > n)//BaseCase，如果当前位置超出所给数字n，也就是超越边界{for (int i = 1; i <= n; i++){cout << state[i] << " ";//输出状态数组}cout << endl;return;}for (int i = 1; i <= n; i++){if (!used[i])//当前数字未被应用{state[u] = i;//当前位置为u的状态数组元素应用数字iused[i] = true;//标记当前数字已被应用dfs(u + 1);//进入下一个位置state[u] = 0;//恢复现场，位置为u的当前状态数组位置设置为0used[i] = false;//恢复现场，当前数字数字标记为未被应用}}}int main(){ cin>>n; dfs(1); return 0;}JAVA版本1.0
import java.util.*;public class Main { public static boolean[] used = new boolean[10]; public static int n; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); String[] arr = new String[n + 1]; for(int i = 1; i <= n; i++) { arr[i] = String.valueOf(i); } dfs(1, arr); } public static void dfs(int u, String[] state)//u代表当前位置 { if (u > n)//BaseCase，如果当前位置超出所给数字n，也就是超越边界 { for (int i = 1; i <= n; i++) { System.out.print(state[i] + " ");//输出状态数组 } System.out.println(); return; } for (int i = 1; i <= n; i++) { if (!used[i])//当前数字未被应用 { state[u] = String.valueOf(i);//当前位置为u的状态数组元素应用数字i used[i] = true;//标记当前数字已被应用 dfs(u + 1, state);//进入下一个位置 state[u] = "0";//恢复现场，位置为u的当前状态数组位置设置为0 used[i] = false;//恢复现场，当前数字数字标记为未被应用 } } }}看到这里的朋友会说你写的两个数组是什么鬼东西，有没有更容易理解的。好的，更容易理解的代码如下。
C++版本2.0
友友们，我写了，编译器说我 Segmentation Fault
#includeusing namespace std;int n;vector<string> removeIndexString(vector<string> arr, int index){vector<string> x;for (int i = 0; i < n ; i++){if (i != index){x.push_back(arr[i]);}}return x;}vector<string> process(vector<string> strs){vector<string> d;if (strs.size() == 0){d.push_back("");return d;}for (int i = 0; i < strs.size(); i++){string first = strs[i];vector<string> nexts = removeIndexString(strs, i);vector<string> next = process(nexts);for (string cur : next){d.push_back((first + cur));}}return d;}int main(){cin >> n;vector<string> arr;for (int i = 0; i < n; i++){arr.push_back((i + 1) + "");}vector<string> ans = process(arr);for (string res : ans){for (int i = 0; i < res.size(); i++){cout << res[i] << " ";}cout << endl;}}JAVA版本2.0
import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String[] arr = new String[n]; for(int i = 0; i < n; i++) { arr[i] = String.valueOf(i + 1); } List<String> ans = process(arr); for(String res : ans) { char[] an = res.toCharArray(); for(int i = 0; i < an.length;i++) { System.out.print(an[i] + " "); } System.out.println(); } } public static List<String> process(String[] strs) { List<String> ans = new ArrayList<>();//定义一个链表 if(strs.length == 0)//如果strs数组中没有元素了，返回空 { ans.add(""); return ans; } for(int i = 0; i < strs.length; i++) { String first = strs[i];//定义第一位置的元素 String[] nexts = removeIndexString(strs, i);//你把除了第一位置的元素数组给我 List<String> next = process(nexts);//你去把之后位置的元素给我 for(String cur : next)//组合，将每个位置的元素进行组合 { ans.add(first + cur); } } return ans;//返回答案链表 } public static String[] removeIndexString(String[] arr, int index)//移除index位置的元素后的数组 { int N = arr.length; String[] ans = new String[N - 1]; int ansIndex = 0; for(int i = 0; i < N; i++) { if(i != index) { ans[ansIndex++] = arr[i]; } } return ans; }}二、递推之飞行兄弟
递推之飞行兄弟，对于开关问题，首先确定所有可能性，然后尝试枚举每一种可能性。
“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 16 个把手的冰箱。已知每个把手可以处于以下两种状态之一：打开或关闭。只有当所有把手都打开时，冰箱才会打开。把手可以表示为一个 4×4 的矩阵，您可以改变任何一个位置 [i,j] 上把手的状态。但是，这也会使得第 i 行和第 j 列上的所有把手的状态也随着改变。请你求出打开冰箱所需的切换把手的次数最小值是多少。输入格式输入一共包含四行，每行包含四个把手的初始状态。符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。至少一个手柄的初始状态是关闭的。输出格式第一行输出一个整数 N，表示所需的最小切换把手次数。接下来 N 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。数据范围1≤i,j≤4输入样例：-+-----------+--输出样例：61 11 31 44 14 34 4第二题代码如下：
C++版本1.0
#include#define x first#define y secondusing namespace std;const int N = 5;char g[N][N], backup[N][N];//数组元素位置如下图进行标记//[0, 1, 2, 3]//[4, 5, 6, 7]//[8, 9, 10, 11]//[12, 13, 14, 15]int get(int x, int y)//获取坐标为（x，y）的数组元素所在的位置{ return x * 4 + y;}void turnOne(int x, int y)//将坐标为（x， y）的元素进行反转{ if (g[x][y] == '+') g[x][y] = '-'; else g[x][y] = '+';}void turnAll(int x, int y)//因为反转一个开关，会把该位置开关所在行和所在列全部进行反转{ for (int i = 0; i < 4; i++) { turnOne(x, i); turnOne(i, y); } turnOne(x, y);//因为坐标为（x，y）的开关被反转了两次，相当于没有反转，所以在反转一次}int main(){ for (int i = 0; i < 4; i++) cin >> g[i];//输入给定的4X4的矩阵 vector<pair<int, int>> res;//定义答案数组 for (int op = 0; op < 1 << 16; op++)//因为有16个开关，每个开关有打开和关闭两个选择，所以全部的可能性为2^16 - 1 { vector<pair<int, int>> temp;//定义辅助数组 memcpy(backup, g, sizeof g);//将g矩阵进行拷贝，因为每一次操作之后需要复原，方便进行下一次可能性 for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) if (op >> get(i, j) & 1)//模拟每种可能性，1代表打开，0代表关闭 { temp.push_back({ i, j });//将坐标为（i，j）的开关打开 turnAll(i, j);//反转坐标为（i，j）的开关所在行和所在列 } bool isClosed = false;//定义标记isClosed，用来判断所有元素是否全部打开，即所有元素全部为‘-’ for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) if (g[i][j] == '+') isClosed = true; if (isClosed == false)//如果所有开关全部打开 { if (res.empty() || res.size() > temp.size())//如果答案数组为空，或者答案数组的元素个数大于临时数组的元素个数，证明答案数组的结果不是最优解，进行替换 { res = temp; } } memcpy(g, backup, sizeof g); } cout << res.size() << endl;//输出答案数组元素个数 for (auto op : res) { cout << op.x + 1 << ' ' << op.y + 1 << endl;//因为我们是从零下表开始，答案是从一下标开始，所以将答案数组中的下标全部加一即可 } return 0;}JAVA版本1.0
import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class tst {//数组元素位置如下图进行标记//[0, 1, 2, 3]//[4, 5, 6, 7]//[8, 9, 10, 11]//[12, 13, 14, 15] public static class Pair{//定义Pair类，用来记录每个开关的位置信息 int x; int y; public Pair(int o1, int o2) { this.x = o1; this.y = o2; } } public static int get(int x,int y)//获取坐标为（x，y）的数组元素所在的位置 { return x * 4 + y; } public static void turnOne(char[][] ch, int x, int y)//将坐标为（x， y）的元素进行反转 { ch[x][y] = ch[x][y] == '+' ? '-' : '+'; } public static void turnAll(char[][] ch, int x, int y)//因为反转一个开关，会把该位置开关所在行和所在列全部进行反转 { for(int i = 0; i < 4; i++) { turnOne(ch, x, i); turnOne(ch, i, y); } turnOne(ch, x, y);//因为坐标为（x，y）的开关被反转了两次，相当于没有反转，所以在反转一次 } public static void copyArray(char[][] ch, char[][] help) { for(int i = 0; i < ch.length; i++) { for(int j = 0; j < ch[0].length; j++) { help[i][j] = ch[i][j]; } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); char[][] ch = new char[4][4]; char[][] help = new char[4][4]; List<Pair> ans = new ArrayList<>();//定义答案链表 int allOp = 1 << 16;//因为有16个开关，每个开关有打开和关闭两个选择，所以全部的可能性为2^16 - 1 for(int i = 0; i < 4; i ++) { String str = sc.next(); for(int j = 0; j < 4; j++) { ch[i][j] = str.charAt(j); } } for(int op = 0; op < allOp; op++) { List<Pair> res = new ArrayList<>();//定义辅助链表 copyArray(ch, help);//将g矩阵进行拷贝，因为每一次操作之后需要复原，方便进行下一次可能性 for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { if(((op >> get(i, j)) & 1) == 1)//模拟每种可能性，1代表打开，0代表关闭 { res.add(new Pair(i, j));//将坐标为（i，j）的开关打开,并加入临时链表 turnAll(ch, i, j);//反转坐标为（i，j）的开关所在行和所在列 } } } boolean isClosed = false;//定义标记isClosed，用来判断所有元素是否全部打开，即所有元素全部为‘-’ for(int i = 0; i < 4; i ++) { for(int j = 0; j < 4; j++) { if(ch[i][j] == '+') { isClosed = true; } } } if(isClosed == false)//如果所有开关全部打开 { if(ans.isEmpty() || (ans.size() > res.size()))//如果答案数组为空，或者答案数组的元素个数大于临时数组的元素个数，证明答案数组的结果不是最优解，进行替换 { ans = res; } } copyArray(help,ch); } System.out.println(ans.size());//输出答案链表元素个数 for(Pair op : ans) { System.out.println((op.x+1) + " "+ (op.y+1));//因为我们是从零下表开始，答案是从一下标开始，所以将答案链表中的下标全部加一即可 } }}