蓝桥杯必考算法递归以及相关题目

作者主页：���热的陕西人

专栏链接：力扣刷题日记

欢迎各位大佬点赞关注收藏，留言

文章目录

• • 1.复杂度
  • 2.递归
  • • 2.1递归实现指数型枚举
    • 2.2递归实现排列型枚举
    • 2.3递归实现组合型枚举
    • 2.4带分数
    • 2.5费解的开关：
    • 2.6翻硬币
    • 2.7飞行员兄弟

      1.复杂度

      2.递归

      2.1递归实现指数型枚举

      #include#include#include#includeusing namespace std;#define N 16int st[N];int n;void dfs(int u) //0表示空，1表示不选，2表示选{    if(u > n)    {        for(int i = 1; i     cin > n;        dfs(1); //表示遍历到第0位            return 0;}

      2.2递归实现排列型枚举

      #include#include#include#includeusing namespace std;#define N 10int state[N]; //0表示未用，1表示使用int ways[N]; //存储我们的答案int n;void dfs(int u){    if(u > n) //边界    {        for(int i = 1; i         if(state[i] == 0)        {            state[i] = 1; //表示占用了u            ways[u] = i; //将u加入到答案                        dfs(u + 1);  //遍历下一个位置                        ways[u] = 0;                        state[i] = 0; //恢复现场        }                    }}int main(){            cin  n;        dfs(1);        return 0;}

      2.3递归实现组合型枚举

      两种方法解决：

      • 将例一不符合长度的答案去掉即可
      • 只需要满足答案的前一个数字比后一个数字大即可

        #include#include#include#includeusing namespace std;#define M 25int ways[M]; //存储我们的答案int n,m;void dfs(int u, int st){    if(n + u - st > m;        dfs(1, 1);        return 0;}

        2.4带分数

        链接：[P1426 - 蓝桥杯]带分数 - New Online Judge (ecustacm.cn)

        [P8599 蓝桥杯 2013 省 B] 带分数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

        思路： 设 n = a + b / c，化简为 n * c = a * c + b;

        那么我们先寻找a, 在a的基础上寻找c， 在a，c已知的情况下，去计算b。

        细节注意要b的类型longlong，不然只能过部分。

        因为算法需要去枚举答案，所以选用了递归的思路。

        #include#include#include#includeusing namespace std;#define N 10bool st[N], buckup[N];int ans;int n;bool check(int a, int c){ long long b = (long long)c * n - c * a;  //注意数据的大小，部分ac！！！！ if(!a || !b || !c) return false; //优化存在零的话直接返回错误 memcpy(buckup, st, sizeof st); while(b) {     int x = b % 10; //取个位     b /= 10; //去掉个位     if(!x || buckup[x]) return false; //存在0，或者对应的数字已经被占用则不是答案     buckup[x] = true; } for(int i = 1; i  if(u == n) return; //当位数达到9位的时候，代表无解 if(check(a, c)) ans++; //检查当前a，c的值，存在一个b成立，则使得答案++ for(int i = 1; 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); //计算当前a下，c的值，c的值从零开始 for(int i = 1; i          st[i] = true; //使用当前的数字         dfs_a(u + 1, a * 10 + i);         st[i] = false; //恢复现场     }}int main(){ cin  n; dfs_a(0, 0); //表示从第零开始，a = 0； cout  -1, 0, 1, 0, 0 }, dy[6] = { 0, 1, 0, -1, 0 };char g[6][6], bk[6][6];void turn(int x, int y){    for (int i = 0; i > n;    while (n--)    {        int res = 10; //设置一个较大的值        for (int i = 0; i > g[i];        for (int op = 0; op > i & 1)                {                    step++;                    turn(0, i); //反转[1,i + 1];                }            //2.接下来处理剩下的234行            for (int i = 0; i  6) res = -1;        cout     if(start[i] == 'o') start[i] = '*';    else start[i] = 'o'}   int main(){    cin  start >> dest;           int n = strlen(start);           int res = 0;           for(int i = 0; i  g[i]; //输入        vector res; //存储答案的数组，每个元素都是一个pair        for(int op = 0; op  get(i, j) & 1)            {                temp.push_back({i, j});                turn_all(i, j);            }                    //判断所有的灯泡是否全亮        bool has_closed = false;        for(int i = 0; i  temp.size()) res = temp;        }                memcpy(g, bku, sizeof g);    }        cout