山西网站设计,网上注册公司价格,手表网站欧米茄官网,凡客家具文章目录 前言Ⅰ. 递归实现指数型枚举0x00 算法思路0x00 代码书写0x00 思考总结 Ⅱ. 递归实现排列型枚举0x00 算法思路0x01代码书写0x02 思考总结 Ⅲ. 简单斐波那契0x00 算法思路0x01 代码书写 Ⅳ. 费解的开关0x00 算法思路0x01 代码书写 Ⅴ. 递归实现组合型枚举0x00 算法思路0… 文章目录 前言Ⅰ. 递归实现指数型枚举0x00 算法思路0x00 代码书写0x00 思考总结 Ⅱ. 递归实现排列型枚举0x00 算法思路0x01代码书写0x02 思考总结 Ⅲ. 简单斐波那契0x00 算法思路0x01 代码书写 Ⅳ. 费解的开关0x00 算法思路0x01 代码书写 Ⅴ. 递归实现组合型枚举0x00 算法思路0x01 代码书写 Ⅵ. 带分数0x00 算法思路0x01 代码书写 Ⅶ. 飞行员兄弟0x00 算法思路0x01 代码书写Ⅷ. 翻硬币0x00 算法思路0x01 代码书写 总结 前言
本篇博客主要打卡记录博主学习蓝桥杯CAB组辅导课的习题第一章节的题目。 Ⅰ. 递归实现指数型枚举
0x00 算法思路
这一道题主要考查 dfs 算法然后这一道题就是以位置来进行 搜索 当搜索到最后一个位置的时候就可以 收获结果 然后考虑枚举到的位置 可以选择 选 或者 不选
0x00 代码书写
#includebits/stdc.husing namespace std;const int N 16;int n;
int st[N]; // 状态记录每个位置当前的状态0表示还没考虑1表示选2表示不选 void dfs(int u)
{if(u n){for(int i 1 ; i n ; i)if(st[i] 1)cout i ;cout endl;return;}//不选st[u] 2;dfs(u 1);st[u] 0; //注意恢复现场 //选st[u] 1;dfs(u 1); st[u] 0; //注意恢复现场}int main()
{ cin n;dfs(1); //枚举第一个位置 return 0;
}0x00 思考总结
这一道题目 就是枚举每一个位置然后进行选这个数字或者不选这个数字当枚举到末尾的时候就可以进行收获(打印结果) — 本质就是枚举每一个位置然后根据选或不选进行的排列组合
Ⅱ. 递归实现排列型枚举
0x00 算法思路
利用一个判断数组st数组检查是否这个位置的数字我已经使用过了如果使用过了就继续如果没有就直接放到a数组里递归下一个位置
0x01代码书写
#includebits/stdc.husing namespace std;const int N 11;int n;
int st[N];//记录这个数字是否被使用过false表示没有true表示用过
int a[N];//存放数字 方便打印void dfs(int u)
{if(u n)//(u n 1)也是可以的表示枚举到最后一个位置{for(int i 1 ; i n; i)cout a[i] ;cout endl;return; }for(int i 1 ; i n ; i){if(st[i] false){a[u] i;st[i] true;dfs(u 1);st[i] false; //恢复现场}}return;
}int main()
{ cin n;dfs(1); //枚举第一个位置 return 0;
}0x02 思考总结
对比上一道题目上一道是根据选或不选来进行排列组合这一道题目则是根据n的位置的多少进行排列组合这里面用到了一个 st 数组来判断这一个数字是否被使用过从而对这n个位置的数字进行排列组合
Ⅲ. 简单斐波那契
0x00 算法思路
简单的递推公式问题
0x01 代码书写
#include iostream
using namespace std;
int main()
{int n;cin n;int a 0, b 1;for (int i 0; i n; i ){cout a ;int c a b;a b;b c;}cout endl;return 0;
}Ⅳ. 费解的开关
0x00 算法思路
暴力枚举第一行的32—2的5次方 种情况然后去统计第一行的五位01串中出现1的数量然后进行turn和step 然后枚举除了最后一行的前面四行遇到 ‘0’ 就可以对 i 1 行 j 列 进行 turn 操作从而使得 ij 这个位置的灯改变成亮。 最后去横扫最后一行看是否有黑的灯如果有的话代表我们的操作是无法完成任务的所以 输出-1 当发现没有黑的时候就可以取最小值进行迭代了。
这里复制粘贴一下Acwing上边的疑惑讲解 1.高票题解代码中的 if (k j 1) 究竟什么意思
其中k保存的根本就不是第一行的灯所有可能的状态不然它第j位都为1了还按它干嘛 k单纯只是保存了第一行按开关的32种方式与输入数据无关。
且大多数题解代码中都规定了k在二进制下某位为1就代表我们选择按下这一位所在编号的开关你也可以自己规定k在二进制下某位为0才代表我们选择按下这一位所在编号的开关这都无所谓。
比如k在二进制下表示为10001就代表我们选择按第一行编号为0和编号为4的开关然后对输入数据中第一行这两位执行turn操作。 贴一个Acwing大佬写的超级详细的题解 AcWing 95. 费解的开关有图超详细看不懂揍我
0x01 代码书写
#includebits/stdc.husing namespace std;const int N 6;char g[N][N], backup[N][N];
int dx[5] {-1,0,1,0,0}, dy[5] {0,1,0,-1,0};void turn(int x,int y)//dfs---迷宫类模板
{for(int i 0 ; i 5 ; i){int a x dx[i], b y dy[i];if(a 0 || a 5 || b 0 || b 5) continue;g[a][b] ^ 1;}
}int main()
{ int T;cin T;while(T -- ){for(int i 0 ; i 5 ; i)for(int j 0 ; j 5 ; j)cin g[i][j];int res 10;for(int op 0 ; op 32 ; op){memcpy(backup, g , sizeof g);int step 0;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)//对黑的灯进行turn操作if(g[i][j] 0){step ;turn(i 1 , j);}bool dark false;for(int i 0 ; i 5 ; i)//遍历最后一行看是否存在黑着的灯if(g[4][i] 0){dark true;break;}if(!dark) res min(res,step);memcpy(g, backup, sizeof g);}if(res 6) res -1;cout res endl;}return 0;
}Ⅴ. 递归实现组合型枚举
0x00 算法思路
通过枚举第一个位置和开始的数进行dfs操作当搜索到最后一个位置的时候就可以收获结果了
0x01 代码书写
#includebits/stdc.husing namespace std;const int N 30;int n, m;
int st[N];void dfs(int u, int start)
{if(u m 1){for(int i 1 ; i m ; i)cout st[i] ;cout endl;return; }for(int i start ; i n ; i){st[u] i;dfs(u 1, i 1);st[u] 0;}
}int main()
{ cin n m;dfs(1, 1); //枚举第一个位置 return 0;
}Ⅵ. 带分数
0x00 算法思路
根据 n a b / c 变换 成为 cn ac n所以可以先确定ac的值进而确定b的值所以有以下思路
枚举a的数值枚举c的数值判断b是否符合条件
这个题目也用到了全排列的思想—本节的第二道题目就是全排列题目的代码和思路
0x01 代码书写
#includebits/stdc.husing namespace std;const int N 10;int n;
bool st[N],backup[N];
int ans;bool check(int a,int c)
{long long b n * (long long)c - a * c;//防止溢出用long longmemcpy(backup,st,sizeof st);//用备份操作if(!a || !b || !c) return false;while(b)//判断b当中的数字是否被使用过了已经{int x b % 10;b / 10;if(!x || backup[x]) return false;//被使用过了就返回falsebackup[x] true;}for(int i 1 ; i 9 ; i)//最后再对abc三个数字所选的数字看看是否选完了0~9个数字if(!backup[i])return false;return true;
}void dfs_c(int u, int a ,int c)
{if(u 9) return; //超过9个数就可以returnif(check(a,c)) ans ; //发现组合就可以 ansfor(int i 1 ; i 9 ; i)//去确定c的值{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; //a不能大于nif(a) dfs_c(u,a,0);//a不能是0 然后去找cfor(int i 1 ; i 9 ; i)//去确定a的值{if(!st[i]){st[i] true;dfs_a(u 1,a * 10 i);st[i] false;}}return;
}int main()
{cin n;dfs_a(0, 0);// 去递归搜索 a 一开始选0个数字(用了多少个数)a是0。cout ans endl;return 0;
}Ⅶ. 飞行员兄弟
0x00 算法思路
先说结论在判断是否要对(i, j)位置的把手进行切换时只需要计算一下第i行和第j列总共7个把手(以下称为(i, j)对应的十字)中闭合的把手数目如果是奇数个就进行切换偶数个就不进行切换。(奇数个是该位置的把手进行过切换的充要条件)
因此我们从上到下从左到右顺次的对16个把手进行上述判断。如果判断结果是奇数个那么说明该位置被切换过进行记录即可。
0x01 代码书写
#includebits/stdc.husing namespace std;#define x first
#define y secondconst int N 5;
typedef pairint,int PII;
char g[N][N], backup[N][N];int get(int x, int y)
{return x * 4 y;
}void turn_one(int x, int y)
{if (g[x][y] ) g[x][y] -;else g[x][y] ;
}void turn_all(int x, int y)
{for (int i 0; i 4; i ){turn_one(x, i);turn_one(i, y);}turn_one(x, y);
}int main()
{for(int i 0 ; i 4 ; i) cin g[i];vectorPII res;for(int op 0 ; op 1 16 ; op){vectorPII temp;memcpy(backup, g ,sizeof g);for(int i 0 ; i 4 ; i)for(int j 0 ; j 4 ; j){if(op get(i, j) 1){temp.push_back({i, j});turn_all(i, j);}}bool has_closed false;for(int i 0 ; i 4 ; i)for(int j 0 ; j 4 ; j){if(g[i][j] )has_closed true;}if(has_closed 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;
}Ⅷ. 翻硬币
0x00 算法思路
将硬币和目标的样子进行比较当发现不一样的时候就进行 turn 翻转即可
0x01 代码书写
#includebits/stdc.husing namespace std;const int N110;
char start[N], aim[N];
int n;void turn(int i)
{if(start[i]o) start[i]*;else start[i]o;
}int main()
{cin start aim;n strlen(start);int res0;for(int i 0; i n - 1 ; i ){if(start[i] ! aim[i]){turn(i), turn(i1);res ;}}cout res endl;return 0;
}总结
本篇博客主要讲解了递推与递归的算法也涉及到了 dfs 搜索算法的使用其实 dfs 算法可以
先去想dfs的含义参数的含义找到dfs的结束条件进行收获结果根据题目要求实现dfs代码
希望自己可以多多练习后面蓝桥杯辅导课看完就会去看算法提高课继续提升
