汽车网站建设参考文献开题报告,xammp如何按wordpress,中国建设银行个人网上银行登录,宁波网站建设制作价格文章目录 一、递归实现指数型枚举 1、1 题目描述 1、2 题解关键思路与解答 二、递归实现排列型枚举 2、1 题目描述 2、2 题解关键思路与解答 三、递归实现组合型枚举 3、1 题目描述 3、2 题解关键思路与解答 四、带分数 4、1 题目描述 4、2 题解关键思路与解答 五、费解的开关… 文章目录 一、递归实现指数型枚举 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表示不选择该数字。这样通过递归我们就可以很好的枚举出每一种情况。我们结合代码一起理解一下。 #includeiostream
using namespace std;const int N16;int n;
int state[N];
void dfs(int a)
{if(an){for(int i1;in;i){if(state[i]1)printf(%d ,i);}puts();return;}state[a]2;dfs(a1);//恢复现场state[a]0;state[a]1;dfs(a1);//恢复现场state[a]0;
}
int main()
{cinn;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是已经使用另一个数组记录所排序的数字。题目中还要求了字典序正常从小到大递归就已经是字典序较小的排在前面。我们直接看代码。 #includeiostream
using namespace std;const int N10;int n;
int state[N];
int used[N];
void dfs(int a)
{if(an){for(int i1;in;i)printf(%d ,state[i]);puts();return;}for(int i1;in;i){if(used[i]0){state[a]i;used[i]1;dfs(a1);used[i]0;}}
}
int main()
{cinn;dfs(1);return 0;
}
三、递归实现组合型枚举
3、1 题目描述 题目来源《算法竞赛进阶指南》 题目难度简单 题目描述 从 1∼n 这 n个整数中随机选出 m个输出所有可能的选择方案。 输入格式 两个整数 n,m,在同一行用空格隔开。 输出格式 按照从小到大的顺序输出所有方案每行 1 个。 首先同一行内的数升序排列相邻两个数用一个空格隔开。 其次对于两个不同的行对应下标的数一一比较字典序较小的排在前面例如 1 3 5 7 排在 1 3 6 8 前面。 数据范围: n0, 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 题解关键思路与解答 组合与排列十分相似但又有些不同。组合特殊的是 123 与 213 与 321相同的算是一种组合类型。题目中要求的同一行内的数升序排列。怎么定义升序呢我们可以人为的选数字为升序。我们可以把整体的升序看成局部的升序只要是满足后一个数比前一个数大即可。 #includeiostream
#includecstdio
#includecstringusing namespace std;int n,m;const int N26;int way[N];
void def(int a,int start)
{if(a-1n-start1m) //剪枝return;if(am1){for(int i1;im;i){printf(%d ,way[i]);}printf(\n);return;}for(int istart;in;i){way[a]i;def(a1,i1);}
}
int main()
{cinnm;def(1,1);return 0;
}
四、带分数
4、1 题目描述 题目来源第四届蓝桥杯省赛CB/C组 题目难度中等 题目描述 100可以表示为带分数的形式100369258 / 714 还可以表示为100823546 / 197 注意特征带分数中数字 1∼9 分别出现且只出现一次不包含 0。 类似这样的带分数100 有 11 种表示法。 输入格式: 一个正整数。 输出格式: 输出输入数字用数码 1∼9不重复不遗漏地组成带分数表示的全部种数。 数据范围: 1≤N106 输入样例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的每一位拿出来看看时候符合题目所要求的情况。我们直接结合代码一起理解一下。 #includecstdio
#includecstring
#includealgorithm
#includeiostreamusing namespace std;const int N12;int n,ans;
bool st[N],backup[N];bool check(int a,int c)
{long long bn*(long long)c-a*c;memcpy(backup,st,sizeof(st));while(b){int xb%10;b/10;if(!x || backup[x])return false;backup[x]true;}for(int i1;i9;i){if(!backup[i])return false;}return true;
}
void dfs_c(int u,int a,int c)
{if(u9)return;if(check(a,c))ans;for(int i1;i9;i){if(!st[i]){st[i]true;dfs_c(u1,a,c*10i);st[i]false;}}
}
void dfs_a(int u,int a)
{if(an)return;if(a)dfs_c(u,a,0);for(int i1;i9;i){if(!st[i]){st[i]true;dfs_a(u1,a*10i);st[i]false;}}
}
int main()
{cinn;dfs_a(0,0);coutansendl;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。 数据范围 0n≤500 输入样例 3
00111
01011
10001
11010
1110011101
11101
11110
11111
1111101111
11111
11111
11111
11111输出样例 3
2
-15、2 题解关键思路与解答 由于每个灯是数字 1 表示一盏开着的灯用数字 0 表示关着的灯我们就一行一行就行看。一行有五个灯我们把代表灯的状态的数字看作一个数的二进制位。也就是一行有32种情况。整体的思路就是下一行影响上一行我们需要做的是首先枚举第一行的32种情况接着调整完前四行最后看第五行是否为全亮即可。我们直接看代码 #includeiostream
#includecstdio
#includecstringusing namespace std;const int N6;
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 i0;i5;i){int axdx[i],bydy[i];if(a0 || a4 || b0 || b4)continue;g[a][b]^1;}
}
int main()
{int n;cinn;while(n--){int res10;for(int i0;i5;i)cing[i];for(int op0;op32;op){int step0;memcpy(backup,g,sizeof(g));for(int i0;i5;i){if(opi1){step;turn(0,i);}}for(int i0;i4;i){for(int j0;j5;j){if(g[i][j]0){step;turn(i1,j);}}}bool backfalse;for(int i0;i5;i){if(g[4][i]0){backtrue;break;}}if(!back)resmin(res,step);memcpy(g,backup,sizeof(g));}if(res6)res-1;coutresendl;}return 0;
} 六、总结 通过上面的习题练习我们发现用递归去枚举也很简单。同时我们也要掌握上面的递归枚举的思路和方法。在很多情况下我们可以多开数组来进行记录或者操作会给我们带来很大的便利。 递归与递推的练习就到这里希望以上内容对你有所帮助。
