第一讲之递归与递推下篇
第一讲之递归与递推下篇
- 带分数
- 费解的开关
- 飞行员兄弟
- 翻硬币
带分数
用暴力将所有全排列的情况都算出来
> 有三个数，a,b,c
每种排列情况，可以用两层for循环，暴力分为三个部分，每个部分一个数
当然注意这里，第一层for循环，小于7.因为一共9个数，要保证剩下2个数不为0，要留2个位置
第二层循环，小于8，要保证剩下一个数不为0了，要留一个位置
如果边界值都写小于9的话，那么就会出现a,b,c三个数出现0的情况，这个时候，我们就要特殊的判断下
#include <iostream>using namespace std;const int N = 10;int target; // 题目给出的目标数
int num[N]; // 保存全排列的结果
bool used[N]; // 生成全排列过程中标记是否使用过
int cnt; // 计数，最后输出的结果// 计算num数组中一段的数是多少
int calc(int l, int r) {int res = 0;for (int i = l; i <= r; i++) {res = res * 10 + num[i];}return res;
}// 生成全排列
// 当全排列生成后进行分段
void dfs(int u) {// 用两层循环分成三段if (u == 9) {for (int i = 0; i < 7; i++) {for (int j = i + 1; j < 8; j++) {int a = calc(0, i);int b = calc(i + 1, j);int c = calc(j + 1, 8);// 注意判断条件，因为C++中除法是整除，所以要转化为加减乘来计算if (a * c + b == c * target) {cnt++;}}}return;}// 搜索模板for (int i = 1; i <= 9; i++) {if (!used[i]) {used[i] = true; // 标记使用num[u] = i;dfs(u + 1);used[i] = false; // 还原现场}}
}int main() {scanf("%d", &target);dfs(0);printf("%d\n", cnt);return 0;
}C++STL函数中也有现成的全排列函数(next_permutation等)，可以不用自己手写
#include <bits/stdc++.h>using namespace std;const int N = 10;int target;
int num[N];int calc(int l, int r) {int res = 0;for (int i = l; i <= r; i++) {res = res * 10 + num[i];}return res;
}int main() {cin >> target;for (int i = 0; i < 9; i++) {num[i] = i + 1;}int res = 0;do {for (int i = 0; i < 9; i++) {for (int j = i + 1; j < 9; j++) {int a = calc(0, i);int b = calc(i + 1, j);int c = calc(j + 1, 8);if (a == 0 || b == 0 || c == 0) {continue;}if (a * c + b == c * target) {++res;}}}// 调用函数生成全排列} while (next_permutation(num, num + 9));cout << res << '\n';return 0;
}这主要用两层dfs嵌套来做
先dfs算出a,每个dfs算出的a中，在dfs c,b的话可以根据a与c的值来算
#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;const int N = 10;int n; //目标数
bool used[N], backup[N]; //全排列的状态数组
int num[N]; //存储全排列的数据
int ans;bool check(int a, int c)
{long long b = n * (long long)c - a * c;if(!a || !b || !c) {return false;}memcpy(backup, used, sizeof used);//b是算出来的，所以b的数字是没用用到过的//因为这里要改变used[]数组，递归也在调用used数组那些//所以我们要重新创个数组while(b) {int x = b %10; //取出个位数b /= 10;if(! x|| backup[x]){return false;}backup[x] = true; //将b中用的数变为真}for(int i = 1; i <= 9; i++){if(!backup[i]){return false;}}return true;}void dfs_c(int u, int a, int c)
{if(u > 9) {return;}if(check(a, c)){ans++;}for(int i = 1;i <= 9; i++){if(!used[i]){used[i] = true;dfs_c(u + 1, a, c * 10 + i);used[i] = false; }}
} void dfs_a(int u, int a)
{if(a >= n) {return;}if(a) {dfs_c(u, a, 0);}for(int i = 1; i <= 9; i++){if(!used[i]){used[i] = true;num[u] = i;dfs_a(u + 1, a * 10 + i );used[i] = false;}}
}int main()
{scanf("%d", &n);dfs_a(0, 0);cout << ans << endl;return 0;}费解的开关
费解的开关，这道题的话，采用暴力的方法。一个开关2种状态：(选与不选)
，因为要求最优的，一个灯改变，它的上下左右相邻的回改变
解题思路：
所以我们先枚举第一行所有的情况 2^32 = 32,然后选择最优的情况
第一行枚举之后，后面依次枚举(利用下一行选开关，来改变上一行开关的状态)，
但是要留下最后一行(因为最后一行，就没有下一行来改变这一行的状态了)，然后检查这一行的状态
如果全是开的，说明这一行都打开了，说明这种枚举方式成功，记录下步数(与之前的比较，选择最优的)
如果不是全部开的，那么就说明枚举失败，进行下一次循环
代码部分细节讲解：
- i >> j & 1
这里其实用的是二进制的形式表示开关，对开关进行的一种优化
注意：结果的1与0，不表示开关的状态， 结果如果是1表示开关要按，为0表示开关不按
例如： 如果i为 00001， j为0， 右移0位表示00001，然后和1进行&运算，结果为1，表示开关(00001,从右往左看)，第一个位置要按，j = 1, j = 2…，都表示不按，所以在开关00001这种枚举情况中，按第一个开关就行，其余开关不用按
2.这里开关状态的变化，采用的枚举的方式
3.注意每种枚举情况，都得把数据拷贝下，然后还原初始状态
#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;const int N = 6;char g[N][N], backup[N][N]; //题目要求一组5个字符， 所以是char类型int dx[5] = {0,-1 , 1, 0, 0}, dy[5] = {0, 0, 0, -1, 1};void turn(int x, int y)
{for(int i = 0; i < 5; i++){//四周的开关状态改变int a = x + dx[i];int b = y + dy[i];if(a >= 0 && a < 5 && b >=0 && b < 5){g[a][b] ^= 1; //用异或来进行状态的改变}}
}int main()
{int T;cin >> T;while(T--){for(int i = 0; i < 5; i++){cin >> g[i];}int res = 10; // 题目要求步数小于6，这里用来存每种枚举情况更新的步数//枚举第一行32种情况for(int i = 0; i < 1 << 5 ; i++){int step = 0;memcpy(backup, g, sizeof g);for(int j = 0; j < 5; j++) {if(i >> j & 1){step++;turn(0, j); }}//剩下几行(除了最后一行)for(int i = 0; i < 4; i++){for(int j = 0; j < 5; j++){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更新结果{//printf("res = %d , step = %d\n", res, step);res = min(res, step); }memcpy(g, backup,sizeof backup);}if(res > 6) {cout << -1 << endl;}else{cout << res << endl;}}return 0;
}飞行员兄弟
这题的思路，跟上题费解的开关，思路差不多，不同的是上题是枚举第一行数据找最优
因为这个开关变化之后，这个开关对应的这一行，这一列都会变化，因为数据不多，
所以可以全部开关都进行暴力枚举
也是采用二进制数进行优化
枚举之后，在判断是否符合条件，当然这里需要我们输出每次改变开关的位置
我这里用vector存储的，pair类型<int, int>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>#define x first
#define y secondusing 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_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 j = 0; j < 4; j++){turn_one(x, j);turn_one(j, y);}//本身翻了2次，相当于没翻，所以还得翻一次turn_one(x, y);
}int main()
{for(int i = 0; i < 4; i++){for(int j = 0; j < 4; j++){cin >> g[i][j];}}vector<pair<int, int>> result;//枚举出所有的情况for(int pos = 0 ; pos < 1 << 16; pos++){vector<pair<int, int>> temp;memcpy(backup, g, sizeof g); for(int i = 0; i < 4; i++){for(int j = 0; j < 4; j++){if(pos >> get(i, j) & 1) //二进制的形式，为1表示需要按， 注意:这里的get(i, j) 要求得具体翻那几个位置{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;break;}}}if(!has_closed){if(result.empty() || result.size() > temp.size()){result = temp;}}memcpy(g, backup, sizeof backup);}cout << result.size() << endl;for(auto v : result){cout << v.first + 1 << " " << v.second + 1 << endl;}return 0;
}翻硬币
这题的话，虽然看着代码简单，但是也还是需要我们自己模拟下情况，才做的出来
判断开关的状态的话，前n- 1个就行，第n个肯定一样，因为题干说肯定有解
#include<iostream>
#include<cstdio>
#include<string>using namespace std;string a, b;void turn(int x)
{if(a[x] == 'o'){a[x] = '*';}else{a[x] = 'o';}}int main()
{cin >> a >> b;int count = 0;//前n- 1个就行，第n个肯定一样，因为题干说肯定有解for(int i = 0; i < a.size() - 1; i++){if(a[i] != b[i]){count++;turn(i);turn(i + 1);}}cout << count << endl;return 0;
}