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

📟作者主页：慢热的陕西人

🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

文章目录

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

      1.复杂度

      

      2.递归

      2.1递归实现指数型枚举

      

      #include
      #include
      #include
      #include
      using namespace std;
      #define N 16
      int 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
      #include
      using namespace std;
      #define N 10
      int 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
        #include
        using namespace std;
        #define M 25
        int 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
        #include
        using namespace std;
        #define N 10
        bool 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