title: 蓝桥杯复习-递归部分
tags:

  • ACM
  • 蓝桥杯
  • 递归
    abbrlink: 84f9ae2e
    date: 2021-03-17 20:34:04

Acw 92.递归实现指数型枚举

题目

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

输入格式

输入一个整数 nn。

输出格式

每行输出一种方案。

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

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

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

数据范围

1≤n≤151≤n≤15

输入样例：

  1. 3

输出样例：

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

代码

  1. #include<iostream>
  2. #include<cstdio>
  4. using namespace std;
  6. const int N=16;
  8. int n;
  9. int st[N];
  11. void dfs(int u)
  12. {
  13.     if(u>n)
  14.     {
  15.         for(int i=1;i<=n;i++)
  16.         {
  17.             if(st[i]==1)
  18.                 printf("%d ", i);
  19.         }
  20.         cout<<endl;
  21.         return;
  22.     }
  23.     st[u]=2;
  24.     dfs(u+1);
  25.     st[u]=0;//分支1不选
  27.     st[u]=1;
  28.     dfs(u+1);
  29.     st[u]=0;//分支2选
  30. }
  32. int main()
  33. {
  34.     cin>>n;
  35.     dfs(1);
  36.     return 0;
  37. }

Acw 94.递归实现排列型枚举

题目

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

输入格式

一个整数 nn。

输出格式

按照从小到大的顺序输出所有方案，每行 11 个。

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

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

数据范围

1≤n≤91≤n≤9

输入样例：

  1. 3

输出样例：

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

代码

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  5. using namespace std;
  7. const int N=10;
  9. int n;
  10. int state[N];
  11. bool used[N];
  13. void dfs(int u)
  14. {
  15.     if(u>n)
  16.     {
  17.         for(int i=1;i<=n;i++)
  18.             printf("%d ", state[i]);
  19.         puts("");
  20.         return;
  21.     }
  22.     for(int i=1;i<=n;i++)
  23.     {
  24.         if(!used[i])
  25.         {
  26.             state[u]=i;
  27.             used[i]=true;
  28.             dfs(u+1);
  30.             state[u]=0;
  31.             used[i]=false;
  32.         }
  33.     }
  34. }
  36. int main()
  37. {
  38.     cin>>n;
  39.     dfs(1);
  40.     return 0;
  41. }

Acw 93.递归实现组合型枚举

题目

从 1∼n1∼n 这 nn 个整数中随机选出 mm 个，输出所有可能的选择方案。

输入格式

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

输出格式

按照从小到大的顺序输出所有方案，每行 11 个。

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

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

数据范围

n>0n>0 ,
0≤m≤n0≤m≤n ,
n+(n−m)≤25n+(n−m)≤25

输入样例：

  1. 5 3

输出样例：

  1. 1 2 3 
  2. 1 2 4 
  3. 1 2 5 
  4. 1 3 4 
  5. 1 3 5 
  6. 1 4 5 
  7. 2 3 4 
  8. 2 3 5 
  9. 2 4 5 
  10. 3 4 5

思考题：如果要求使用非递归方法，该怎么做呢？

思路

利用递归建立起数结构，每次都对是否选中下一个树做成选择，构成二叉树

代码

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  5. using namespace std;
  7. const int N=30;
  9. int n,m;
  10. int way[N];
  12. void dfs(int u, int start)
  13. {
  14.     if(u+n-start<m) return; //剪枝
  15.     if(u==m+1)
  16.     {
  17.         for(int i=1;i<=m;i++)
  18.         {
  19.             for(int i=1;i<=m;i++)   cout<<way[i]<<" ";
  20.             cout<<endl;
  21.             return;
  22.         }
  23.     }
  24.     for(int i=start;i<=n;i++)
  25.     {
  26.         way[u]=i;
  27.         dfs(u+1, i+1);
  28.         way[u]=0;//恢复
  29.     }
  30. }
  32. int main()
  33. {
  34.     cin>>n>>m;
  35.     dfs(1,1);
  36.     return 0;
  37. }

Acw 95.费解的开关

题目

你玩过“拉灯”游戏吗？

2525 盏灯排成一个 5×55×5 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 11 表示一盏开着的灯，用数字 00 表示关着的灯。

下面这种状态

  1. 10111
  2. 01101
  3. 10111
  4. 10000
  5. 11011

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

  1. 01111
  2. 11101
  3. 10111
  4. 10000
  5. 11011

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

  1. 01111
  2. 11001
  3. 11001
  4. 10100
  5. 11011

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

输入格式

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

以下若干行数据分为 nn 组，每组数据有 55 行，每行 55 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

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

对于某一个游戏初始状态，若 66 步以内无法使所有灯变亮，则输出 −1−1。

数据范围

0<n≤5000<n≤500

输入样例：

  1. 3
  2. 00111
  3. 01011
  4. 10001
  5. 11010
  6. 11100
  8. 11101
  9. 11101
  10. 11110
  11. 11111
  12. 11111
  14. 01111
  15. 11111
  16. 11111
  17. 11111
  18. 11111

输出样例：

  1. 3
  2. 2
  3. -1

代码

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  5. using namespace std;
  7. const int N=6;
  9. char g[N][N], backup[N][N];
  10. int dx[5]={-1, 0, 1, 0, 0}, dy[5]={0, 1, 0, -1, 0};
  12. void turn(int x, int y)
  13. {
  14.     for(int i=0;i<5;i++)
  15.     {
  16.         int a=x+dx[i], b=y+dy[i];
  17.         if(a<0 || a>=5 || b<0 || b>=5)    continue;
  18.         g[a][b]^=1;
  19.     }
  20. }
  22. int main()
  23. {
  24.     int T;
  25.     cin>>T;
  26.     while(T--)
  27.     {
  28.         for(int i=0;i<5;i++)
  29.             cin>>g[i];
  30.         int res=10;
  31.         for(int op=0;op<32;op++)
  32.         {
  33.             memcpy(backup, g, sizeof(g));
  34.             int step=0;
  35.             for(int i=0;i<5;i++)
  36.             {
  37.                 if(op>>i & 1)
  38.                 {
  39.                     step++;
  40.                     turn(0, i);
  41.                 }
  42.             }
  43.             for(int i=0;i<4;i++)
  44.             {
  45.                 for(int j=0;j<5;j++)
  46.                 {
  47.                     if(g[i][j]=='0')
  48.                     {
  49.                         step++;
  50.                         turn(i+1, j);
  51.                     }
  52.                 }
  53.             }
  54.             bool dark=false;
  55.             for(int i=0;i<5;i++)
  56.             {
  57.                 if(g[4][i]=='0')
  58.                 {
  59.                     dark=true;
  60.                     break;
  61.                 }
  62.             }
  63.             if(!dark)   res=min(res, step);
  64.             memcpy(g, backup, sizeof(g));
  65.         }
  66.         if(res>6)   res=-1;
  67.         cout<<res<<endl;
  68.     }
  69.     return 0;
  70. }