「蓝桥杯」

蓝桥杯系列文章目录

• [ ★] 第一讲 递推与递归

题目目录：

• [ ★] 第一讲 递推与递归
• • [ ★] 第一题 DFS下的全排列（一题带你搞懂全排列，下面第二种方法作为福利提供给大家，仅此模版，一次搞定全排列）
• • [ ★] 第一讲 递推与递归（一题带你入门开关问题）

我的核心技术者社区

诚邀各位技术爱好者，在本社区，我会尽全力给大家提供一个友好的交流平台。欢迎各位技术爱好者加入。
链接：

https://bbs.csdn.net/forums/CoreTechnologyProvider_TheOne?category=0

一、DFS下的全排列

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数 n。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围
1≤n≤9

输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

第一题代码如下：

C++版本1.0

#include<bits/stdc++.h>usingnamespace std;constint N =10;int state[N];bool used[N];int n;voiddfs(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的状态数组元素应用数字i
            used[i]=true;//标记当前数字已被应用dfs(u +1);//进入下一个位置
            state[u]=0;//恢复现场，位置为u的当前状态数组位置设置为0
            used[i]=false;//恢复现场，当前数字数字标记为未被应用}}}intmain(){
    cin>>n;dfs(1);return0;}

JAVA版本1.0

import java.util.*;publicclassMain{publicstaticboolean[] used =newboolean[10];publicstaticint n;publicstaticvoidmain(String[] args){
        Scanner sc =newScanner(System.in);
        n = sc.nextInt();
        String[] arr =newString[n +1];for(int i =1; i <= n; i++){
            arr[i]= String.valueOf(i);}dfs(1, arr);}publicstaticvoiddfs(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

#include<bits/stdc++.h>usingnamespace 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;}intmain(){
    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.*;publicclassMain{publicstaticvoidmain(String[] args){
        Scanner sc =newScanner(System.in);int n = sc.nextInt();
        String[] arr =newString[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();}}publicstatic List<String>process(String[] strs){
        List<String> ans =newArrayList<>();//定义一个链表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;//返回答案链表}publicstatic String[]removeIndexString(String[] arr,int index)//移除index位置的元素后的数组{int N = arr.length;
        String[] ans =newString[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
输入样例：
-+--
----
----
-+--
输出样例：
6
1 1
1 3
1 4
4 1
4 3
4 4

第二题代码如下：

C++版本1.0

#include<bits/stdc++.h>#define x first#define y secondusingnamespace std;constint 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]intget(int x,int y)//获取坐标为（x，y）的数组元素所在的位置{return x *4+ y;}voidturnOne(int x,int y)//将坐标为（x， y）的元素进行反转{if(g[x][y]=='+') g[x][y]='-';else g[x][y]='+';}voidturnAll(int x,int y)//因为反转一个开关，会把该位置开关所在行和所在列全部进行反转{for(int i =0; i <4; i++){turnOne(x, i);turnOne(i, y);}turnOne(x, y);//因为坐标为（x，y）的开关被反转了两次，相当于没有反转，所以在反转一次}intmain(){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;//因为我们是从零下表开始，答案是从一下标开始，所以将答案数组中的下标全部加一即可}return0;}

JAVA版本1.0

import java.util.ArrayList;import java.util.List;import java.util.Scanner;publicclasstst{//数组元素位置如下图进行标记//[0,  1,  2,   3]//[4,  5,  6,   7]//[8,  9,  10, 11]//[12, 13, 14, 15]publicstaticclassPair{//定义Pair类，用来记录每个开关的位置信息int x;int y;publicPair(int o1,int o2){this.x = o1;this.y = o2;}}publicstaticintget(int x,int y)//获取坐标为（x，y）的数组元素所在的位置{return x *4+ y;}publicstaticvoidturnOne(char[][] ch,int x,int y)//将坐标为（x， y）的元素进行反转{
        ch[x][y]= ch[x][y]=='+'?'-':'+';}publicstaticvoidturnAll(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）的开关被反转了两次，相当于没有反转，所以在反转一次}publicstaticvoidcopyArray(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];}}}publicstaticvoidmain(String[] args){
        Scanner sc =newScanner(System.in);char[][] ch =newchar[4][4];char[][] help =newchar[4][4];
        List<Pair> ans =newArrayList<>();//定义答案链表int allOp =1<<16;//因为有16个开关，每个开关有打开和关闭两个选择，所以全部的可能性为2^16 - 1for(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 =newArrayList<>();//定义辅助链表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(newPair(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));//因为我们是从零下表开始，答案是从一下标开始，所以将答案链表中的下标全部加一即可}}}

尾语

抱歉，我最近有些忙，博客会陆续补上。谢谢大家！