网站建设的总体需求分析,个人备案挂企业网站,Wordpress会员插件推荐,网站开发岗位就业分析第一讲之递归与递推下篇 带分数费解的开关飞行员兄弟翻硬币 带分数 用暴力将所有全排列的情况都算出来 有三个数#xff0c;a,b,c 每种排列情况#xff0c;可以用两层for循环#xff0c;暴力分为三个部分#xff0c;每个部分一个数 当然注意这里#xff0c;第一层fo… 第一讲之递归与递推下篇 带分数费解的开关飞行员兄弟翻硬币 带分数 用暴力将所有全排列的情况都算出来 有三个数a,b,c 每种排列情况可以用两层for循环暴力分为三个部分每个部分一个数 当然注意这里第一层for循环小于7.因为一共9个数要保证剩下2个数不为0要留2个位置 第二层循环小于8要保证剩下一个数不为0了要留一个位置 如果边界值都写小于9的话那么就会出现a,b,c三个数出现0的情况这个时候我们就要特殊的判断下 #include iostreamusing 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;
} CSTL函数中也有现成的全排列函数(next_permutation等)可以不用自己手写 #include bits/stdc.husing 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的值来算 #includeiostream
#includecstdio
#includecstringusing 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.注意每种枚举情况都得把数据拷贝下然后还原初始状态 #includeiostream
#includecstdio
#includecstringusing 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 #includeiostream
#includecstdio
#includecstring
#includevector#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];}}vectorpairint, int result;//枚举出所有的情况for(int pos 0 ; pos 1 16; pos){vectorpairint, 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个肯定一样因为题干说肯定有解 #includeiostream
#includecstdio
#includestringusing 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;
}
