devbox
神奇cpp
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

递归与递推---题目练习_常用算法解析法枚举法递归法递推法练习题

作者：神奇cpp | 2024-08-22 00:40:16

赞

踩

常用算法解析法枚举法递归法递推法练习题

目录

1、递归实现指数型枚举

2、递归实现排列型枚举

3、递归实现组合型枚举

4、带分数

方法一

方法二

5、翻硬币

6、飞行员兄弟

7、费解的开关

递归是指在函数的定义中使用函数自身的方法。它通过不断地将问题分解为更小的子问题，直到达到基本情况，然后再逐层返回结果。

递推则是通过已知的前一个或前几个状态来推导出后续状态的方法。它是按照一定的规律逐步计算出后续结果的过程。

从宏观上来看，递归是将一个大问题分解为多个相同类型的小问题，不断重复；递推是根据前一个或前几个状态逐步推出后续状态，也就是从小问题解决到大问题。

本文是递归与递推的算法题练习，题目都源于网站Acwing

1、递归实现指数型枚举

输入样例：

3

输出样例：

  1.  
  2. 3
  3. 2
  4. 2 3
  5. 1
  6. 1 3
  7. 1 2
  8. 1 2 3

当每个状态的可能情况都是相同的，那么此时就是指数型枚举

在这种枚举方式中，通常会以某种特定的顺序或规则来遍历所有可能的情况

比如本题，枚举1~n的每个数，每个数都有选或不选两种情况，共有2^n种结果

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 20;
  5. int n;
  6. bool st[N];//每个数的状态，默认为都不选
  7.  
  8. void dfs(int x)
  9. {
  10.     if(x > n) 
  11.     {
  12.         for(int i=1;i<=n;i++)
  13.             if(st[i]) cout<<i<<" ";
  14.         cout<<endl;
  15.         return ;
  16.     }
  17.     
  18.     //不选
  19.     st[x] = false;
  20.     dfs(x+1);
  21.     
  22.     //选
  23.     st[x] = true;
  24.     dfs(x+1);
  25. }
  26.  
  27. int main()
  28. {
  29.     cin>>n;
  30.     
  31.     dfs(1);
  32.  
  33.     return 0;
  34. }

2、递归实现排列型枚举

输入样例：

3

输出样例：

  1. 1 2 3
  2. 1 3 2
  3. 2 1 3
  4. 2 3 1
  5. 3 1 2
  6. 3 2 1

所谓排列，就是对给定的元素，按照不同顺序，排列出所有可能的情况，每个元素不重不漏

特点：有序、不重不漏

代码实现时一般会为排列元素开一个状态数组，来判定是否选过

本题就是对1~n的全排列

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N =20;
  5. bool st[N];//状态数组，是否选过，默认没选
  6. int ans[N];
  7. int n;
  8.  
  9. void dfs(int x)
  10. {
  11.     if(x > n)
  12.     {
  13.         for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
  14.         cout<<endl;
  15.     }
  16.     
  17.     for(int i=1;i<=n;i++)
  18.     {
  19.         if(!st[i])
  20.         {
  21.             st[i] = true;
  22.             ans[x] = i;
  23.             dfs(x+1);
  24.             
  25.             st[i] = false;//还原现场
  26.         }
  27.     }
  28. }
  29.  
  30. int main()
  31. {
  32.     cin>>n;
  33.     dfs(1);
  34.     return 0;
  35. }

3、递归实现组合型枚举

输入样例：

5 3

输出样例：

  1. 1 2 3 
  2. 1 2 4 
  3. 1 2 5 
  4. 1 3 4 
  5. 1 3 5 
  6. 1 4 5 
  7. 2 3 4 
  8. 2 3 5 
  9. 2 4 5 
  10. 3 4 5

组合是从给定的元素集合中，选取若干个元素组成一组，而不考虑元素的排列顺序。

 

组合只关注选取哪些元素，而不关心这些元素的具体排列方式。

在代码实现中，组合型枚举区别于排列型、指数型枚举，它需要传参来标记枚举顺序（每次枚举的起始位置），防止枚举重复，同样的，因为每次标记了起始位置，所以从起始位置开始都是未选取的元素，不再像排列型枚举那样开状态数组

代码：

  1. #include<bits/stdc++.h>
  2. using namespace  std;
  3.  
  4. const int N = 30;
  5. int n,m;
  6. int ans[N];
  7.  
  8. void dfs(int x,int start)
  9. {
  10.     if(x-1 + n-start + 1 < m) return;
  11.     
  12.     if(x > m)
  13.     {
  14.         for(int i=1;i<=m;i++) cout<<ans[i]<<" ";
  15.         cout<<endl;
  16.         return ;
  17.     }
  18.     
  19.     for(int i=start;i<=n;i++)
  20.     {
  21.         ans[x] = i;
  22.         dfs(x+1,i+1);
  23.         
  24.         ans[x] = 0;//还原现场，本题其实可以不用，会自动覆盖
  25.     }
  26. }
  27.  
  28. int main()
  29. {
  30.     cin>>n>>m;
  31.     
  32.     dfs(1,1);
  33.     
  34.     return 0;
  35. }

4、带分数

题意中的除法，没有特别指出时，一般都指正常的除法，而不是C++中的整除

题意表示，输入n，使得 n = a + b/c ，其中a、b、c包含的数字恰好为1~9各自出现一次

为了在编程时规避整除问题，我们一般把问题转化为乘法: n*c = a*c + b

方法一

每个元素恰好出现一次，正好对应全排列的性质，可以这么做：

  • 对1~9做全排列，共有 9！种情况
  • 枚举a、b、c分别有多少位（枚举了a、b就确定了c，两重循环即可）
  • 判断等式 n*c = a*c + b 是否相等

代码：

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 10;
  8. bool st[N];
  9. int ans[N];
  10. int n,cnt;
  11.  
  12. int to_nums(int l, int r)
  13. {
  14.     int res = 0;
  15.     for(int i = l; i <= r; i++)
  16.     {
  17.         res = res*10 + ans[i];
  18.     }
  19.     return res;
  20. }
  21.  
  22. void dfs(int x)
  23. {
  24.     if(x == 10)
  25.     {
  26.         for(int i = 1; i <= 7; i++)
  27.         {
  28.             for(int j = i+1; j<= 8; j++)
  29.             {
  30.                 int a = to_nums(1,i);
  31.                 int b = to_nums(i+1,j);
  32.                 int c = to_nums(j+1,9);
  33.                 
  34.                 if(c*n == c*a + b) cnt++;
  35.             }
  36.         }
  37.         
  38.         return;
  39.     }
  40.     
  41.     for(int i=1;i<=9;i++)
  42.     {
  43.         if(!st[i])
  44.         {
  45.             st[i] = true;
  46.             ans[x] = i;
  47.             dfs(x+1);
  48.             
  49.             st[i] = false;
  50.         }
  51.     }
  52. }
  53.  
  54. int main()
  55. {
  56.     cin>>n;
  57.     
  58.     dfs(1);
  59.     
  60.     cout<<cnt<<endl;
  61.     return 0;
  62. }

方法一的做法虽然能够AC，但因为是全排列，罗列了所有的情况去判断，有没有更高效的做法呢？

方法二

对于等式：n*c = a*c + b ，要找出满足该等式的三个数a、b、c，在给定了n的情况下，其实只需要确定了a、c， 根据等式，b也就确定了，再用确定的一组a、b、c，去判断是否满足题目要求（三个数包含的数字有且只能1~9各出现一次），这样的做法，不会像全排列那样罗列所有情况，会更加高效

步骤：

  • 先搜索可能满足情况的数字a ( 0 < a < n)
  • 对于每一个a，再去搜索可能的c ( a、c用的数字个数小于9，c > 0 )
  • 对于每一组a、c，通过等式n*c = a*c + b计算得出b，再判断是否满足题意
  • 如何判断？先判断b的各个数字是否与a、c用的数字冲突，再怕判断1~9是否都被使用了

代码：

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 20;
  8. bool st[N],backup[N];
  9. int n,cnt;
  10.  
  11. bool check(int a, int c)
  12. {
  13.     long long b = c*(long long)n - c*a;
  14.     if(!a || !b || !c) return false;
  15.     
  16.     memcpy(backup,st,sizeof st);
  17.     
  18.     while(b)
  19.     {
  20.         int t = b % 10;
  21.         b /= 10;
  22.         if(!t || backup[t]) return false;
  23.         backup[t] = true;
  24.     }
  25.     
  26.     for(int i=1; i <= 9; i++)
  27.     {
  28.         if(!backup[i]) return false;
  29.     }
  30.     
  31.     return true;
  32. }
  33.  
  34. void dfs_c(int x, int a, int c)
  35. {
  36.     if(x >= 9) return ;
  37.     
  38.     if(check(a,c)) cnt++;
  39.     
  40.     for(int i=1; i <= 9; i++)
  41.     {
  42.         if(!st[i])
  43.         {
  44.             st[i] = true;
  45.             dfs_c(x+1,a,c*10+i);
  46.             
  47.             st[i] = false;
  48.         }
  49.     }
  50. }
  51.  
  52. void dfs_a(int x,int a)
  53. {
  54.     if(a >=n) return ;
  55.     if(a) dfs_c(x,a,0);
  56.     
  57.     for (int i = 1; i <= 9; i ++ )
  58.     {
  59.         if(!st[i])
  60.         {
  61.             st[i] = true;
  62.             dfs_a(x+1,a*10+i);
  63.             
  64.             st[i] = false;
  65.         }
  66.     }
  67. }
  68.  
  69.  
  70. int main()
  71. {
  72.     cin>>n;
  73.     
  74.     dfs_a(0,0);
  75.     
  76.     cout<<cnt<<endl;
  77.     return 0;
  78. }

5、翻硬币

输入样例1：

  1. **********
  2. o****o****

输出样例1：

5

输入样例2：

  1. *o**o***o***
  2. *o***o**o***

输出样例2：

1

通过推演可以发现，我们只需用一个指针 i 从前向后扫描，如果当前 i 指向的位置初始状态和目标状态不同，就翻转 i 和 i+1 位置的硬币(并记录翻转次数+1)，保证 i 之前的初始状态和目标状态相同；因为题目说一定有解，如此遍历一遍，就一定能保证字符串的初始状态转变成了目标状态

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     string src,dst;
  7.     cin >> src >> dst;
  8.     
  9.     int ans = 0;
  10.     for(int i = 0; i < src.size(); i++ )
  11.     {
  12.         if(src[i] != dst[i])
  13.         {
  14.             src[i] = src[i] != '*' ? '*' : 'o';
  15.             src[i+1] = src[i+1] != '*' ? '*' : 'o';
  16.             ans++;
  17.         }
  18.     }
  19.     
  20.     cout << ans << endl;
  21.     return 0;
  22. }

6、飞行员兄弟

输入样例：

  1. -+--
  2. ----
  3. ----
  4. -+--

输出样例：

  1. 6
  2. 1 1
  3. 1 3
  4. 1 4
  5. 4 1
  6. 4 3
  7. 4 4

思路：题目数据是4 * 4的矩阵，对于每个开关我们可以有按或不按两种情况，也就是对于这个矩阵，枚举对矩阵的操作方案：共有2^16 可能；对于每种操作方案，去对矩阵操作一遍后判断是否满足题意（开关全开），保存操作次数最小的一种输出即可。

代码实现中，

  • 需要先枚举所有操作方案，每行用一个int数来代表，范围【0，15】；op[i]表示第 i 行的操作方案，所以需要对op[4]做指数型枚举，16^4种可能
  • 对于每一种操作方案，模拟一遍对矩阵的操作，所以需要一个备份矩阵backup，在每次矩阵操作、判断完成后，把被操作的矩阵恢复原样，方便下次操作
  • 矩阵的操作过程中，涉及到某个点的开关如果要按下，则需要用一个vector记录其坐标，方便后续输出；因为要更新最小值和对应得坐标，所以vector用tmp临时存储，如果要更新答案就把tmp赋值给ans，如果不更新答案就把tmp清空，以记录下一种操作方案的操作坐标

代码一：

  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. const int N = 20;
  7. char g[N][N],backup[N][N];
  8. int op[4];
  9. bool st[16];
  10. int ways = 50;
  11.  
  12. struct point
  13. {
  14.     int x;
  15.     int y;
  16. };
  17.  
  18. vector<struct point> tmp,ans;
  19. void turn(int x, int y)
  20. {
  21.     for(int i = 0; i < 4; i++ )
  22.     {
  23.         g[x][i] = g[x][i] != '+' ? '+' : '-';
  24.     }
  25.  
  26.      for(int i = 0; i < 4; i++ )
  27.     {
  28.         g[i][y] = g[i][y] != '+' ? '+' : '-';
  29.     }
  30.  
  31.     g[x][y] = g[x][y] != '+' ? '+' : '-';
  32. }
  33.  
  34.  
  35. void check()
  36. {
  37.     int step = 0;
  38.    
  39.     for(int i = 0; i < 4; i++ )
  40.     {
  41.         for(int j = 0; j < 4; j++ )
  42.         {
  43.             if(op[i] >> j & 1)
  44.             {
  45.                 step++;
  46.                 turn(i,j);
  47.                 tmp.push_back({i,j});
  48.             }
  49.         }
  50.     }
  51.  
  52.     bool off = false;
  53.     for(int i = 0; i < 4; i++ )
  54.     {
  55.         for(int j = 0; j < 4; j++ )
  56.         {
  57.             if(g[i][j] == '+')
  58.             {
  59.                 off = true;
  60.                 break;
  61.             }
  62.         }
  63.     }
  64.  
  65.     if(!off && (step < ways))
  66.     {
  67.         ways = min(ways,step);
  68.         ans = tmp;
  69.     }
  70.     else
  71.     {
  72.         tmp.clear();
  73.     }
  74.     
  75.     memcpy(g, backup, sizeof backup);
  76. }
  77.  
  78.  
  79. void dfs_op(int x)
  80. {
  81.     if(x == 4)
  82.     {
  83.         check();
  84.         return ;
  85.     }
  86.  
  87.     for(int i = 0; i < 16; i++ )
  88.     {
  89.        op[x] = i;
  90.        dfs_op(x+1);
  91.     }
  92. }
  93.  
  94. int main()
  95. {
  96.     for(int i = 0; i < 4; i++ ) cin >> g[i];
  97.     
  98.      memcpy(backup, g, sizeof g);
  99.  
  100.     dfs_op(0);
  101.  
  102.     cout << ways << endl;
  103.     for(auto& p : ans)
  104.     {
  105.         cout << p.x + 1 << " " << p.y + 1 <<endl;
  106.     }
  107.     return 0;
  108. }

代码二：

这个版本，是枚举操作方案时，直接用一个int来表示4x4矩阵的开关操作，再通过映射函数来对应矩阵的每个元素（矩阵元素从0开始标序号）

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using PII = pair<int,int>;
  4.  
  5. char g[5][5],backup[5][5];
  6. int cnt = 100;
  7. vector<PII> ans;
  8.  
  9. void turn(int x, int y)
  10. {
  11.     for(int i = 0; i < 4; i++ )
  12.     {
  13.         g[x][i] = g[x][i] != '+' ? '+' : '-';
  14.         g[i][y] = g[i][y] != '+' ? '+' : '-';
  15.     }
  16.     
  17.     g[x][y] = g[x][y] != '+' ? '+' : '-';
  18. }
  19.  
  20.  
  21. int get(int x, int y)
  22. {
  23.     return x*4 + y;
  24. }
  25.  
  26. int main()
  27. {
  28.     for(int i=0;i<4;i++) cin>>g[i];
  29.     
  30.     memcpy(backup, g, sizeof g);
  31.     
  32.     for(int op = 0; op < 1 << 16; op++)
  33.     {
  34.         vector<PII> tmp;
  35.         for(int i = 0; i < 4; i++ )
  36.         {
  37.             for(int j = 0; j < 4; j++ )
  38.             {
  39.                 if(op >> get(i,j) & 1)
  40.                 {
  41.                     tmp.push_back({i,j});
  42.                     turn(i,j);
  43.                 }
  44.             }
  45.         }
  46.         
  47.         bool off = false;
  48.         for(int i = 0; i < 4; i++ )
  49.         {
  50.             for(int j = 0; j < 4; j++ )
  51.             {
  52.                 if(g[i][j] == '+')
  53.                 {
  54.                     off = true;
  55.                     break;
  56.                 }
  57.             }
  58.         }
  59.         
  60.         if(!off && cnt > tmp.size())
  61.         {
  62.             cnt = tmp.size();
  63.             ans = tmp;
  64.         }
  65.         
  66.         memcpy(g, backup, sizeof g);
  67.     }
  68.     
  69.     
  70.     cout << cnt << endl;
  71.     for(auto& op : ans) cout << op.first + 1 << " " << op.second + 1 <<endl;
  72.     return 0;
  73. }

7、费解的开关

你玩过“拉灯”游戏吗？

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

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

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

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

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

下面这种状态

  1. 10111
  2. 01101
  3. 10111
  4. 10000
  5. 11011

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

  1. 01111
  2. 11101
  3. 10111
  4. 10000
  5. 11011

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

  1. 01111
  2. 11001
  3. 11001
  4. 10100
  5. 11011

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

输入格式

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

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

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

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

输出格式

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

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

数据范围

0<<声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/1013954

推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。