[蓝桥杯] 递归与递推习题训练

news/2024/10/30 9:32:38/

 

文章目录

一、递归实现指数型枚举

1、1 题目描述

1、2 题解关键思路与解答

二、递归实现排列型枚举 

2、1 题目描述

2、2 题解关键思路与解答

三、递归实现组合型枚举

3、1 题目描述

3、2 题解关键思路与解答

四、带分数

4、1 题目描述

4、2 题解关键思路与解答

五、费解的开关

5、1 题目描述

5、2 题解关键思路与解答

 六、总结


标题:蓝桥杯——递归与递推习题训练

作者:@Ggggggtm

寄语:与其忙着诉苦,不如低头赶路,奋路前行,终将遇到一番好风景

  蓝桥杯比赛只有四十天左右啦,最近会按照模块更新一些有关蓝桥杯算法题。学习算法不仅仅是为了参见比赛,更是以后找工作的一个敲门砖。废话不多说,我们直接看题。

一、递归实现指数型枚举

1、1 题目描述

题目来源:《算法竞赛进阶指南》

题目难度:简单

题目描述:

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

输入格式:

  输入一个整数 n。

输出格式:

  每行输出一种方案。

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

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

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

数据范围:

  1≤ n≤ 15

输入样例:

3

输出样例:


3
2
2 3
1
1 3
1 2
1 2 3

1、2 题解关键思路与解答

   由于上述题目是要求递归,我们可以通过开一个数组纪录是否选择该数组(0表示还没对该数字进行操作,1表示选择该数字,2表示不选择该数字)。这样通过递归,我们就可以很好的枚举出每一种情况。我们结合代码一起理解一下。

#include<iostream>
using namespace std;const int N=16;int n;
int state[N];
void dfs(int a)
{if(a>n){for(int i=1;i<=n;i++){if(state[i]==1)printf("%d ",i);}puts("");return;}state[a]=2;dfs(a+1);//恢复现场state[a]=0;state[a]=1;dfs(a+1);//恢复现场state[a]=0;
}
int main()
{cin>>n;dfs(1);return 0;
}

二、递归实现排列型枚举 

2、1 题目描述

题目来源:《算法竞赛进阶指南》

题目难度:简单

题目描述:

  把 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

2、2 题解关键思路与解答

  这个题的关键就在于是排列。通过递归枚举的方法实现排列,我们需要开两个数组:一个数组是记录还数字是否被使用过(0是未被使用,1是已经使用),另一个数组记录所排序的数字。题目中还要求了字典序,正常从小到大递归就已经是字典序较小的排在前面。我们直接看代码。

#include<iostream>
using namespace std;const int N=10;int n;
int state[N];
int used[N];
void dfs(int a)
{if(a>n){for(int i=1;i<=n;i++)printf("%d ",state[i]);puts("");return;}for(int i=1;i<=n;i++){if(used[i]==0){state[a]=i;used[i]=1;dfs(a+1);used[i]=0;}}
}
int main()
{cin>>n;dfs(1);return 0;
}

三、递归实现组合型枚举

3、1 题目描述

题目来源:《算法竞赛进阶指南》

题目难度:简单

题目描述:

  从 1∼n 这 n个整数中随机选出 m个,输出所有可能的选择方案。

输入格式:

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

输出格式:

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

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

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

数据范围:

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

输入样例:

5 3

输出样例:

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

3、2 题解关键思路与解答

  组合与排列十分相似,但又有些不同。组合特殊的是 1,2,3 与 2,1,3 与 3,2,1相同的,算是一种组合类型。题目中要求的同一行内的数升序排列。怎么定义升序呢?我们可以人为的选数字为升序。我们可以把整体的升序看成局部的升序,只要是满足后一个数比前一个数大即可。

#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;int n,m;const int N=26;int way[N];
void def(int a,int start)
{if(a-1+n-start+1<m)  //剪枝return;if(a==m+1){for(int i=1;i<=m;i++){printf("%d ",way[i]);}printf("\n");return;}for(int i=start;i<=n;i++){way[a]=i;def(a+1,i+1);}
}
int main()
{cin>>n>>m;def(1,1);return 0;
}

四、带分数

4、1 题目描述

题目来源:第四届蓝桥杯省赛C++B/C组

题目难度:中等

题目描述:

  100可以表示为带分数的形式:100=3+69258 / 714

  还可以表示为:100=82+3546 / 197

  注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)。

  类似这样的带分数,100 有 11 种表示法。

输入格式:

  一个正整数。

输出格式:

  输出输入数字用数码 1∼9不重复不遗漏地组成带分数表示的全部种数。

数据范围:

 1≤N<106

输入样例1:

100

输出样例1:

11

输入样例2:

105

输出样例2:

6

4、2 题解关键思路与解答

  我们可以把带分数的形式看成一个公式:n = a + b / c 。也就是a、b和c 的数字 中1∼9 分别出现且只出现一次。那我们就可以想枚举a和c的情况,然后通过公式 b = c*n-c*a 计算出b的值。再把b的每一位拿出来看看时候符合题目所要求的情况。我们直接结合代码一起理解一下。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>using namespace std;const int N=12;int n,ans;
bool st[N],backup[N];bool check(int a,int c)
{long long b=n*(long long)c-a*c;memcpy(backup,st,sizeof(st));while(b){int x=b%10;b/=10;if(!x || backup[x])return false;backup[x]=true;}for(int i=1;i<=9;i++){if(!backup[i])return false;}return true;
}
void dfs_c(int u,int a,int c)
{if(u>9)return;if(check(a,c))ans++;for(int i=1;i<=9;i++){if(!st[i]){st[i]=true;dfs_c(u+1,a,c*10+i);st[i]=false;}}
}
void dfs_a(int u,int a)
{if(a>=n)return;if(a)dfs_c(u,a,0);for(int i=1;i<=9;i++){if(!st[i]){st[i]=true;dfs_a(u+1,a*10+i);st[i]=false;}}
}
int main()
{cin>>n;dfs_a(0,0);cout<<ans<<endl;return 0;
}

五、费解的开关

5、1 题目描述

题目来源:《算法竞赛进阶指南》

题目难度:中等

题目描述:

  你玩过“拉灯”游戏吗?

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

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

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

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

  我们用数字 1 表示一盏开着的灯,用数字 0 表示关着的灯。

下面这种状态:

10111
01101
10111
10000
11011

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

01111
11101
10111
10000
11011

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

01111
11001
11001
10100
11011

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

输入格式:

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

  以下若干行数据分为 n 组,每组数据有 5 行,每行 5 个字符。

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

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

输出格式:

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

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

数据范围:

0<n≤500

输入样例:

3
00111
01011
10001
11010
1110011101
11101
11110
11111
1111101111
11111
11111
11111
11111

输出样例:

3
2
-1

5、2 题解关键思路与解答

  由于每个灯是数字 1 表示一盏开着的灯,用数字 0 表示关着的灯,我们就一行一行就行看。一行有五个灯,我们把代表灯的状态的数字看作一个数的二进制位。也就是一行有32种情况。整体的思路就是下一行影响上一行,我们需要做的是首先枚举第一行的32种情况,接着调整完前四行,最后看第五行是否为全亮即可。我们直接看代码:

#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;const int N=6;
char g[N][N],backup[N][N];
int dx[5]={-1,0,1,0,0},dy[5]={0,0,0,-1,1};void turn(int x,int y)
{for(int i=0;i<5;i++){int a=x+dx[i],b=y+dy[i];if(a<0 || a>4 || b<0 || b>4)continue;g[a][b]^=1;}
}
int main()
{int n;cin>>n;while(n--){int res=10;for(int i=0;i<5;i++)cin>>g[i];for(int op=0;op<32;op++){int step=0;memcpy(backup,g,sizeof(g));for(int i=0;i<5;i++){if(op>>i&1){step++;turn(0,i);}}for(int i=0;i<4;i++){for(int j=0;j<5;j++){if(g[i][j]=='0'){step++;turn(i+1,j);}}}bool back=false;for(int i=0;i<5;i++){if(g[4][i]=='0'){back=true;break;}}if(!back)res=min(res,step);memcpy(g,backup,sizeof(g));}if(res>6)res=-1;cout<<res<<endl;}return 0;
}

 六、总结

  通过上面的习题练习,我们发现用递归去枚举也很简单。同时,我们也要掌握上面的递归枚举的思路和方法。在很多情况下,我们可以多开数组来进行记录或者操作,会给我们带来很大的便利。

  递归与递推的练习就到这里,希望以上内容对你有所帮助。


http://www.ppmy.cn/news/26920.html

相关文章

【C++提高编程】C++全栈体系(二十三)

C提高编程 第三章 STL - 常用容器 八、set / multiset 容器 1. set基本概念 简介&#xff1a; 所有元素都会在插入时自动被排序 本质&#xff1a; set/multiset属于关联式容器&#xff0c;底层结构是用二叉树实现。 set和multiset区别&#xff1a; set不允许容器中有重…

Tomcat的类加载机制

不遵循双亲委托 在JVM中并不是一次性地把所有的文件都加载到&#xff0c;而是按需加载&#xff0c;加载机制采用 双亲委托原则&#xff0c;如下图所示&#xff1a; BootStrapClassLoader 引导类加载器ExtClassLoader 扩展类加载器AppClassLoader 应用类加载器CustomClassLoad…

Docker 安装nacos并且配置数据库持久化(无脑CV版)

我们以运行ruoyi-cloud项目为例子 在安装之前请注意版本对应问题 https://github.com/alibaba/spring-cloud-alibaba/wiki/%E7%89%88%E6%9C%AC%E8%AF%B4%E6%98%8E 由于我的是2021.0.4.0&#xff0c;因此安装2.0.4版本 否则可能会出现以下错误 在若依的issue有解决方案https:…

扬帆优配|3300点半日游!上证指数冲高回落;再迎重磅利好!

今天早盘&#xff0c;A股冲高回落&#xff0c;上证指数3300点得而复失&#xff0c;深证成指也于12000点无功而返。 盘面上&#xff0c;煤炭、钢铁、房地产、才智政务等板块涨幅居前&#xff0c;酿酒、酒店餐饮、日用化工、IT设备等板块跌幅居前。北上资金净流入7.77亿元。 房地…

.net 6 引入EFCore

这里默认使用sql server数据库 DBFirst nuget引入程序集 Microsoft.EntityFrameworkCore Microsoft.EntityFrameworkCore.SqlServer Microsoft.EntityFrameworkCore.Design Microsoft.EntityFrameworkCore.Tools Microsoft.Extensions.Logging.Console 执行脚本 设置DAL…

用Python搓一个黑洞

文章目录简介单位制观测绘图简介 黑洞图像大家都知道&#xff0c;毕竟前几年刚发布的时候曾火遍全网&#xff0c;甚至都做成表情包了。 问题在于&#xff0c;凭什么认为这就是黑洞的照片&#xff0c;而不是一个甜甜圈啥的给整模糊了得到的呢&#xff1f;有什么理论依据吗&…

Python列表list操作-遍历、查找、增加、删除、修改、排序

在使用列表的时候需要用到很多方法&#xff0c;例如遍历列表、查找元素、增加元素、删除元素、改变元素、插入元素、列表排序、逆序列表等操作。 1、遍历列表 遍历列表通常采用for循环的方式以及for循环和enumerate&#xff08;&#xff09;函数搭配的方式去实现。 1&#xff…

如何使用raw socket发送UDP报文

前面写的一篇《Linux下如何在数据链路层接收原始数据包》举了一个实例,使用raw socket接收UDP数据报,但是发送一个数据包比接收要复杂一些,本文以一个实例说明如何使用raw socket发送一个UDP报文。 1. 前言 阅读本文前可以考虑先阅读一下我的另外一篇文章《Linux下如何在数据…