无锡嘉饰茂建设网站的公司,手机兼职在家挣钱的方法,网页微信版官网登录不扫码,会员中心网站模板递归 直白理解#xff1a;函数在其内部调用自身#xff08;自己调用自己#xff09;所有递归都可以采用递归搜索树来理解递归的特点#xff1a; 一般来说代码较为简短#xff0c;但是理解难度大一般时间和空间消耗较大#xff0c;容易产生重复计算#xff0c;可能爆栈 …递归 直白理解函数在其内部调用自身自己调用自己所有递归都可以采用递归搜索树来理解递归的特点 一般来说代码较为简短但是理解难度大一般时间和空间消耗较大容易产生重复计算可能爆栈
递归实现指数型枚举
题目描述
从 1∼n 这 n 个整数中随机选取任意多个输出所有可能的选择方案。
输入格式
输入一个整数 n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案输出空行。
本题有自定义校验器SPJ各行不同方案之间的顺序任意。
数据范围
1 n 15
输入样例
3输出样例
32
2 3
1
1 3
1 2
1 2 3思路递归DFS 从1 ~ n依次参考每一个数选或者不选。 举个栗子 当n 2时
从1~n依次考虑这个数选或者不选。
AC代码
#includecstdio
#includecstring
#includeiostream
#includealgorithmusing namespace std;const int N 16;int n;
int nums[N]; //记录当前位置的状态0还没考虑1选它2不选它 void dfs(int curr) {if (curr n) {for (int i 1; i n; i) { //if (nums[i] 1) {cout i ;}}cout endl;return;}nums[curr] 2; //当前位置不选dfs(curr 1); // 第一个分支不选当前位置nums[curr] 0; // 恢复现场此处该语句可省略nums[curr] 1; //当前位置选dfs(curr 1); // 第二个分支选当前位置nums[curr] 0; // 恢复现场此处该语句可省略
}int main()
{cin n;dfs(1); //传入当前枚举的位置从第一位开始枚举return 0;
}变式将所有方案记录下来
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includevectorusing namespace std;const int N 16;int n;
int nums[N]; //记录当前位置的状态0还没考虑1选它2不选它
vectorvectorint ways; //用来记录每一个方案void dfs(int curr) {if (curr n) {vectorint way;for (int i 1; i n; i) { //记录方案if (nums[i] 1) {way.push_back(i);}}ways.push_back(way);return;}nums[curr] 2; //当前位置不选dfs(curr 1); // 第一个分支不选当前位置nums[curr] 0; // 恢复现场此处该语句可省略nums[curr] 1; //当前位置选dfs(curr 1); // 第二个分支选当前位置nums[curr] 0; // 恢复现场此处该语句可省略
}int main()
{scanf(%d, n);dfs(1); //传入当前枚举的位置从第一位开始枚举for (int i 0; i ways.size(); i) {for (int j 0; j ways[i].size(); j) {printf(%d , ways[i][j]);}puts();}return 0;
}递归实现排列型枚举
题目描述
把 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思路递归DFS
全排列问题有两种理解思路 顺序一依次枚举每个数放到哪个位置 顺序二依次枚举每个位置放哪个数 以顺序二为例 当n 3时 AC代码
#includecstdio
#includecstring
#includeiostream
#includealgorithmusing namespace std;const int N 10;int n;
int state[N]; //记录当前方案0表示还没放数 1~n表示放入的数字
bool used[N]; //记录当前的数是否被使用true使用过 false还未使用void dfs(int curr) {if (curr n) { //判断边界for (int i 1; i n; i) { //输出方案printf(%d , state[i]);}puts();return;}//一次枚举每个分支即当前位置可以填哪些数for (int i 1; i n; i) { //按字典序从小到大一次枚举if (!used[i]) {state[curr] i; //填入该数used[i] true; //记录该数已被选用dfs(curr 1); //枚举下一个位置//恢复现场state[curr] 0; //该语句此处可以省略used[i] false;}}
}int main()
{cin n;dfs(1); //传入当前枚举的位置从第一位开始枚举return 0;
}递归实现组合型枚举
题目描述
把 1∼n 这 n 个整数中随机选出 m 个输出所有可能的选择方案。
输入格式
两个整数 nm在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案每行 1 个。
首先同一行内的数升序排列相邻两个数用一个空格隔开。
其次对于两个不同的行对应下标的数一一比较字典序较小的排在前面例如 1 3 5 7 排在 1 3 6 8 前面
数据范围
n 0,
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 思路递归DFS
题目要求是组合型枚举不能含重复项每一组数据从小到大排列
当n 5m 3时仅有以下几种符合要求其余分支无法凑满3个数因此舍弃 在枚举每个位置的时候将数字从小到大枚举这里考虑局部属性只需保证新加的数大于前一个数
考虑需要的参数全局变量、形参
参数一m个位置用来存入数据。way[N]参数二当前枚举到哪个位置。curr参数三当前最小可以从哪个数开始枚举。start
AC代码
#includecstdio
#includecstring
#includeiostream
#includealgorithmusing namespace std;const int N 30;int n, m;
int way[N]; //用来记录当前方案。0表示还未放入数据1~n表示存入的数据void dfs(int curr, int start) {if (curr m 1) { //边界判断已经选了m个数for (int i 1; i m; i) { //输出方案printf(%d , way[i]);}puts();return;}for (int i start; i n; i) { //每次从start开始枚举保证后一个数比前一个数大way[curr] i; //将数据i放入当前位置dfs(curr 1, i 1);way[curr] 0; //回复现场此处可以省略}
}int main()
{scanf(%d%d, n, m);dfs(1,1); //第一个参数从第一个位置开始枚举。第二个参数最小可以从1开始枚举return 0;
}剪枝优化
当枚举到第curr个位置时表示正在选第curr个数此时已经选好了curr - 1个数剩下可供选择的数为从start到n共有n - start 1当选中的数和剩下的所有数加起来不够m个数时表示此方案无解可以提前舍弃。curr - 1 n - start 1 m**即curr n - start m**
#includecstdio
#includecstring
#includeiostream
#includealgorithmusing namespace std;const int N 30;int n, m;
int way[N]; //用来记录当前方案。0表示还未放入数据1~n表示存入的数据void dfs(int curr, int start) {//剪枝当后面的所有数加起来不够m个时直接返回if (curr n - start m) {return;}if (curr m 1) { //边界判断已经选了m个数for (int i 1; i m; i) {printf(%d , way[i]);}puts();return;}for (int i start; i n; i) { //每次从start开始枚举保证后一个数比前一个数大way[curr] i; //将数据i放入当前位置dfs(curr 1, i 1);way[curr] 0; //回复现场此处可以省略}
}int main()
{scanf(%d%d, n, m);dfs(1,1); //第一个参数从第一个位置开始枚举。第二个参数最小可以从1开始枚举return 0;
}带分数
题目描述
100 可以表示为带分数的形式100 3 6925871469258 \over 71471469258
还可以表示为100 82 35461973546 \over 1971973546
注意特征带分数中数字 1∼9 分别出现且只出现一次不包含 0。
类似这样的带分数100有11种表示法。
输入格式
一个正整数n。
输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围
1 N 10610^6106
输入样例1:
100输出样例1
11输入样例2:
105输出样例2
6思路递归DFS
上述等式可以表示为这种形式n a bcb \over ccb采取一下方案来解决问题
枚举a、b、c的全排列分别枚举a、b、c的位数判断等式是否成立
结合题目优化一下 将上述等式转变为c * n c * a bn已知分别枚举a和c的全排列然后计算b是否满足要求即可。
AC代码
#includebits/stdc.h
using namespace std;const int N 20;
int n, ans; //ans用来记录最终的种数
bool st[N], backup[N]; // st数组记录当前数字是否被使用过。ture表示使用过false表示未使用;backup数组用来备份stbool check(int a, int c) {long long b n * (long long)c - a * c;if (!a || !b || !c) return false; //a,b,c均不能为0memcpy(backup, st, sizeof st); //备份st数组while (b) {int x b % 10; //取个位数b / 10; //删除个位数if (!x || backup[x]) return false; //依次判断b的每一个数是否被使用过backup[x] true; //标记这个数被用过}for (int i 1; i 9; i) { //判断9个数是否都被使用过if (!backup[i]) return false;}return true;
}void dfs_c(int used, int a, int c) { // 第一个参数表示当前已经用了多少个数字第二个参数表示a的值第三个参数表示c的值if (used n) return; //如果已经用完了n个数字则返回if(check(a,c)) ans; //检验a和c是否满足要求for (int i 1; i 9; i) {if (!st[i]) {st[i] true;dfs_c(used 1, a, c * 10 i);st[i] false; //恢复现场}}
}void dfs_a(int used, int a) { //第一个参数表示当前已经用了多少个数字第二个参数表示a的值if (a n) return; //如果a n则无解直接返回if (a) dfs_c(used, a, 0);for (int i 1; i 9; i) {if (!st[i]) {st[i] true;dfs_a(used 1, a * 10 i);st[i] false; //恢复现场}}
}int main() {cin n;dfs_a(0, 0); //第一个参数表示当前已经用了多少个数字第二个参数表示a的值cout ans;return 0;
}剪枝优化
在枚举a的位数的时候已经使用的数最多达到7因为b和c至少各占一位在枚举c的时候已经使用的数最多达到8因为b至少占一位
#includebits/stdc.h
using namespace std;const int N 20;
int n, ans; //ans用来记录最终的种数
bool st[N], backup[N]; // st数组记录当前数字是否被使用过。ture表示使用过false表示未使用;backup数组用来备份stbool check(int a, int c) {long long b n * (long long)c - a * c;if (!a || !b || !c) return false; //a,b,c均不能为0memcpy(backup, st, sizeof st); //备份st数组while (b) {int x b % 10; //取个位数b / 10; //删除个位数if (!x || backup[x]) return false; //依次判断b的每一个数是否被使用过backup[x] true; //标记这个数被用过}for (int i 1; i 9; i) { //判断9个数是否都被使用过if (!backup[i]) return false;}return true;
}void dfs_c(int used, int a, int c) { // 第一个参数表示当前已经用了多少个数字第二个参数表示a的值第三个参数表示c的值if (used 8) return; //剪枝优化当used 8时就可以返回了因为b至少占一位if(check(a,c)) ans; //检验a和c是否满足要求for (int i 1; i 9; i) {if (!st[i]) {st[i] true;dfs_c(used 1, a, c * 10 i);st[i] false; //恢复现场}}
}void dfs_a(int used, int a) { //第一个参数表示当前已经用了多少个数字第二个参数表示a的值if (a n) return; //如果a n则无解直接返回if (used 7) return; //剪枝优化当used 7时就可以返回了因为b和c至少各占一位if (a) dfs_c(used, a, 0); //当a不等于0的时候再去枚举c的可能情况for (int i 1; i 9; i) {if (!st[i]) {st[i] true;dfs_a(used 1, a * 10 i);st[i] false; //恢复现场}}
}int main() {cin n;dfs_a(0, 0); //第一个参数表示当前已经用了多少个数字第二个参数表示a的值cout ans;return 0;
}递推
简单斐波那契
题目描述
以下数列0 1 1 2 3 5 8 13 21 … 被称为斐波纳契数列。
这个数列从第 3 项开始每一项都等于前两项之和。
输入一个整数 N请你输出这个序列的前 N 项。
输入格式
一个整数 N。
输出格式
在一行中输出斐波那契数列的前 N 项数字之间用空格隔开。
数据范围
0 N 46
输入样例:
5输出样例
0 1 1 2 3思路递推
根据数列的规律可知数列的每一项等于其前面两项之和即f(n) f(n - 1) f(n - 2); (n 3)
AC代码
#includebits/stdc.h
using namespace std;int main()
{int n, a 0, b 1, t;cin n;for (int i 1; i n; i) {cout a ;t a b;a b;b t;}return 0;
}费解的开关
题目描述
你玩过“拉灯”游戏吗
25 盏灯排成一个 5×5 的方形。
每一个灯都有一个开关游戏者可以改变它的状态。
每一步游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 1 表示一盏开着的灯用数字 0 表示关着的灯。
下面这种状态
10111
01101
10111
10000
11011在改变了最左上角的灯的状态后将变成
01111
11001
11001
10100
11011给定一些游戏的初始状态编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。
输入格式
第一行输入正整数 n代表数据中共有 n 个待解决的游戏初始状态。
以下若干行数据分为 n 组每组数据有 5 行每行 5 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式
一共输出 n 行数据每行有一个小于等于 6 的整数它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态若 6 步以内无法使所有灯变亮则输出 −1。
数据范围
0 N 500
输入样例:
3
00111
01011
10001
11010
1110011101
11101
11110
11111
1111101111
11111
11111
11111
11111输出样例
3
2
-1思路递推
结合题目分析可以得出以下性质
按开关的顺序是随意的没有影响每个开关最多只按一次要求最小的触发次数按两次等于没按
结论
每一行开关的操作完全由上一行灯的明灭状态所决定。能影响第一行灯状态的只有第二行灯以此类推每操作一行只能保证当前行的前面所有行的灯都亮着当前行无法保证。因此只需要枚举第一行的所有操作即可。共25 25种方案利用二进制枚举
AC代码
#includebits/stdc.h
using namespace std;const int N 6;
char nums[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) { //改变上下左右和当前的灯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; //越界了}nums[a][b] ^ 1; //字符0变11变0}
}int main()
{int n;scanf(%d, n);while (n--) {for (int i 0; i 5; i) {scanf(%s, nums[i]);}int ans 10;for (int i 0; i 32; i) {memcpy(backup, nums, sizeof nums); //将nums数组备份int step 0;for (int t 0; t 5; t) {if (i t 1) {step;turn(0, t); //改变上下左右和当前的灯}}for (int x 0; x 4; x) { //检查前4行灯for (int y 0; y 5; y) {if (nums[x][y] 0) { //如果当前位置的灯是灭的则要按当前位置等的下一行灯的按钮step;turn(x 1, y); //改变上下左右和当前的灯}}}bool flag false;for (int i 0; i 5; i) { //检查最后一排灯是否都变亮if (nums[4][i] 0) {flag true;break;}}if (!flag) { //更新答案ans min(ans, step);}memcpy(nums, backup, sizeof nums); //恢复nums数组}if (ans 6) ans -1;printf(%d\n, ans);}return 0;
}翻硬币
题目描述
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面用 o 表示反面是小写字母不是零。
比如可能情形是**oo***oooo
如果同时翻转左边的两个硬币则变为oooo***oooo
现在小明的问题是如果已知了初始状态和要达到的目标状态每次只能同时翻转相邻的两个硬币,那么对特定的局面最少要翻动多少次呢
我们约定把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串分别表示初始状态和要达到的目标状态。
输出格式
一个整数表示最小操作步数
数据范围
输入字符串的长度均不超过100。 数据保证答案一定有解。
输入样例1:
**********
o****o****输出样例1
5输入样例2:
*o**o***o***
*o***o**o***输出样例2
1思路
我们可以依据输入输出样例来进行模拟分析可以发现以下性质
一次能改变一组相邻的两枚硬币翻两次相当于没有改变。对于同一个位置如果初始态和目标太的硬币正反不一致则含有该硬币的一组相邻硬币一定要进行翻转。题目保证样例必有解我们可以从左到右进行模拟遇到不同的硬币就进行翻转可以发现翻转硬币数最少的方案是唯一的。
AC代码
#includebits/stdc.h
using namespace std;int main() {string s1, s2;cin s1 s2;int ans 0;for (int i 0; i s1.size() - 1; i) {if (s1[i] ! s2[i]) { //当前位置硬币正反不同需要进行翻转s1[i] s2[i];s1[i 1] s1[i 1] * ? o : *;ans;}}cout ans;return 0;
}飞行员兄弟
题目描述
“飞行员兄弟”这个游戏需要玩家顺利的打开一个拥有 16 个把手的冰箱。
已知每个把手可以处于以下两种状态之一打开或关闭。
只有当所有把手都打开时冰箱才会打开。
把手可以表示为一个 4×4 的矩阵您可以改变任何一个位置 [ij] 上把手的状态。
但是这也会使得第 i 行和第 j 列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式
输入一共包含四行每行包含四个把手的初始状态。
符号 表示把手处于闭合状态而符号 - 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数 N表示所需的最小切换把手次数。
接下来 N 行描述切换顺序每行输出两个整数代表被切换状态的把手的行号和列号数字之间用空格隔开。
注意如果存在多种打开冰箱的方式则按照优先级整体从上到下同行从左到右打开。
数据范围
1 ij 4
输入样例1:
---
----
----
---输出样例1
5输入样例2:
*o**o***o***
*o***o**o***输出样例2
6
1 1
1 3
1 4
4 1
4 3
4 4思路
经分析可知 每一个控制把手最多按一次 按把手的先后顺序无关紧要 本题很难找出递推规律因为影响一个冰箱门的开关太多了因此可以采用暴力枚举来解决 枚举所有方案。0~216 - 1二进制枚举每个方案对应的位置如下 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 按照每一个枚举的方案对冰箱进行对应的操作 判断方案是否符合要求
AC代码
#includebits/stdc.h
using namespace std;const int N 5;
char g[N][N], backup[N][N];int get(int x, int y) { //映射关系转换return x * 4 y;
}void turn(int x, int y) { //将xy所在位置的行和列的符号反转for (int i 0; i 4; i) { //反转第x行的符号if (g[x][i] ) {g[x][i] -;} else {g[x][i] ;}}for (int i 0; i 4; i) { //反转第y列的符号if (g[i][y] ) {g[i][y] -;} else {g[i][y] ;}}g[x][y] g[x][y] ? - : ;
}int main() {vectorpairint, int ans; //用来存储当前最优的操作方案for (int i 0; i 4; i) cin g[i];for (int i 0; i 1 16; i) {vectorpairint, int temp; //存储当前操作memcpy(backup, g, sizeof g); //备份//对当前方案进行检验for (int x 0; x 4; x) {for (int y 0; y 4; y) { //遍历矩阵if (i get(x,y) 1) { //判断当前位置的开关是否被按temp.push_back({x, y});turn(x, y);}}}//判断所有冰箱是否都打开bool flag true;for (int x 0; x 4; x) {for (int y 0; y 4; y) {if (g[x][y] ) {flag false;}}}if (flag) {if (ans.empty() || ans.size() temp.size()) { //记录操作次数最少的方案ans temp;}}memcpy(g, backup, sizeof g); // 还原}cout ans.size() endl;for (int i 0; i ans.size(); i) {cout ans[i].first 1 ans[i].second 1 endl;}return 0;
}
