前言
本篇博客主要打卡記錄博主學(xué)習(xí)藍(lán)橋杯C++AB組輔導(dǎo)課的習(xí)題第一章節(jié)的題目。
Ⅰ. 遞歸實(shí)現(xiàn)指數(shù)型枚舉
0x00 算法思路
這一道題主要考查 dfs 算法，然后這一道題就是以位置來進(jìn)行 搜索 當(dāng)搜索到最后一個(gè)位置的時(shí)候就可以 收獲結(jié)果 然后考慮枚舉到的位置 可以選擇 選 或者 不選
0x00 代碼書寫
#include<bits/stdc++.h>
using namespace std;
const int N = 16;
int n;
int st[N]; // 狀態(tài)，記錄每個(gè)位置當(dāng)前的狀態(tài)：0表示還沒考慮，1表示選，2表示不選
void dfs(int u)
{
if(u > n)
{
for(int i = 1 ; i <= n ; ++ i)
if(st[i] == 1)
cout << i << " ";
cout << endl;
return;
}
//不選
st[u] = 2;
dfs(u + 1);
st[u] = 0; //注意恢復(fù)現(xiàn)場(chǎng)
//選
st[u] = 1;
dfs(u + 1);
st[u] = 0; //注意恢復(fù)現(xiàn)場(chǎng)
}
int main()
{
cin >> n;
dfs(1); //枚舉第一個(gè)位置
return 0;
}
0x00 思考總結(jié)
這一道題目 就是枚舉每一個(gè)位置，然后進(jìn)行選這個(gè)數(shù)字或者不選這個(gè)數(shù)字，當(dāng)枚舉到末尾的時(shí)候就可以進(jìn)行收獲(打印結(jié)果) —> 本質(zhì)就是枚舉每一個(gè)位置然后根據(jù)選或不選進(jìn)行的排列組合
Ⅱ. 遞歸實(shí)現(xiàn)排列型枚舉
0x00 算法思路
利用一個(gè)判斷數(shù)組st數(shù)組，檢查是否這個(gè)位置的數(shù)字我已經(jīng)使用過了，如果使用過了，就繼續(xù)，如果沒有就直接放到a數(shù)組里，遞歸下一個(gè)位置
0x01代碼書寫
#include<bits/stdc++.h>
using namespace std;
const int N = 11;
int n;
int st[N];//記錄這個(gè)數(shù)字是否被使用過false表示沒有，true表示用過
int a[N];//存放數(shù)字 方便打印
void dfs(int u)
{
if(u > n)//(u == n + 1)也是可以的表示枚舉到最后一個(gè)位置
{
for(int i = 1 ; i <= n; ++ i)
cout << a[i] << " ";
cout << endl;
return;
}
for(int i = 1 ; i <= n ; ++ i)
{
if(st[i] == false)
{
a[u] = i;
st[i] = true;
dfs(u + 1);
st[i] = false; //恢復(fù)現(xiàn)場(chǎng)
}
}
return;
}
int main()
{
cin >> n;
dfs(1); //枚舉第一個(gè)位置
return 0;
}
0x02 思考總結(jié)
對(duì)比上一道題目，上一道是根據(jù)選或不選來進(jìn)行排列組合，這一道題目則是根據(jù)n的位置的多少進(jìn)行排列組合，這里面用到了一個(gè) st 數(shù)組來判斷這一個(gè)數(shù)字是否被使用過，從而對(duì)這n個(gè)位置的數(shù)字進(jìn)行排列組合
Ⅲ. 簡(jiǎn)單斐波那契
0x00 算法思路
簡(jiǎn)單的遞推公式問題
0x01 代碼書寫
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int a = 0, b = 1;
for (int i = 0; i < n; i ++ )
{
cout << a << ' ';
int c = a + b;
a = b;
b = c;
}
cout << endl;
return 0;
}
Ⅳ. 費(fèi)解的開關(guān)
0x00 算法思路
暴力枚舉第一行的32—>2的5次方 種情況，然后去統(tǒng)計(jì)第一行的五位01串中出現(xiàn)1的數(shù)量然后進(jìn)行turn和step++，
然后枚舉除了最后一行的前面四行，遇到 ‘0’ 就可以對(duì) i + 1 行 j 列 進(jìn)行 turn 操作，從而使得 i，j 這個(gè)位置的燈改變成亮。
最后去橫掃最后一行，看是否有黑的燈，如果有的話，代表我們的操作是無法完成任務(wù)的，所以 輸出-1
當(dāng)發(fā)現(xiàn)沒有黑的時(shí)候，就可以取最小值進(jìn)行迭代了。
這里復(fù)制粘貼一下Acwing上邊的疑惑講解：
1.高票題解代碼中的 if (k >> j & 1) 究竟什么意思？
其中，k保存的根本就不是第一行的燈所有可能的狀態(tài)，不然它第j位都為1了還按它干嘛？ k單純只是保存了第一行按開關(guān)的32種方式，與輸入數(shù)據(jù)無關(guān)。
且大多數(shù)題解代碼中都規(guī)定了k在二進(jìn)制下某位為1就代表我們選擇按下這一位所在編號(hào)的開關(guān)，你也可以自己規(guī)定k在二進(jìn)制下某位為0才代表我們選擇按下這一位所在編號(hào)的開關(guān)，這都無所謂。
比如k在二進(jìn)制下表示為10001，就代表我們選擇按第一行編號(hào)為0和編號(hào)為4的開關(guān)，然后對(duì)輸入數(shù)據(jù)中第一行這兩位執(zhí)行turn操作。
貼一個(gè)Acwing大佬寫的超級(jí)詳細(xì)的題解
AcWing 95. 費(fèi)解的開關(guān)（有圖超詳細(xì)，看不懂揍我）
0x01 代碼書寫
#include<bits/stdc++.h>
using namespace std;
const int N = 6;
char g[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)//dfs--->迷宮類模板
{
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;
g[a][b] ^= 1;
}
}
int main()
{
int T;
cin >> T;
while(T -- )
{
for(int i = 0 ; i < 5 ; ++ i)
for(int j = 0 ; j < 5 ; ++ j)
cin >> g[i][j];
int res = 10;
for(int op = 0 ; op < 32 ; ++ op)
{
memcpy(backup, g , sizeof g);
int step = 0;
for(int i = 0 ; i < 5 ; ++ i)
if(op >> i & 1)
{
step ++;
turn(0, i);
}
for(int i = 0 ; i < 4 ; ++ i)
for(int j = 0 ; j < 5 ; ++ j)//對(duì)黑的燈進(jìn)行turn操作
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 = min(res,step);
memcpy(g, backup, sizeof g);
}
if(res > 6) res = -1;
cout << res << endl;
}
return 0;
}
Ⅴ. 遞歸實(shí)現(xiàn)組合型枚舉
0x00 算法思路
通過枚舉第一個(gè)位置和開始的數(shù)進(jìn)行dfs操作，當(dāng)搜索到最后一個(gè)位置的時(shí)候就可以收獲結(jié)果了
0x01 代碼書寫
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int n, m;
int st[N];
void dfs(int u, int start)
{
if(u == m + 1)
{
for(int i = 1 ; i <= m ; ++ i)
cout << st[i] << " ";
cout << endl;
return;
}
for(int i = start ; i <= n ; ++ i)
{
st[u] = i;
dfs(u + 1, i + 1);
st[u] = 0;
}
}
int main()
{
cin >> n >> m;
dfs(1, 1); //枚舉第一個(gè)位置
return 0;
}
Ⅵ. 帶分?jǐn)?shù)
0x00 算法思路
根據(jù) n = a + b / c 變換 成為 ： cn = ac + n所以可以先確定ac的值進(jìn)而確定b的值所以有以下思路：
- 枚舉a的數(shù)值
- 枚舉c的數(shù)值
- 判斷b是否符合條件
這個(gè)題目也用到了全排列的思想—>本節(jié)的第二道題目就是全排列題目的代碼和思路
0x01 代碼書寫
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int n;
bool st[N],backup[N];
int ans;
bool check(int a,int c)
{
long long b = n * (long long)c - a * c;//防止溢出用long long
memcpy(backup,st,sizeof st);//用備份操作
if(!a || !b || !c) return false;
while(b)//判斷b當(dāng)中的數(shù)字是否被使用過了已經(jīng)
{
int x = b % 10;
b /= 10;
if(!x || backup[x]) return false;//被使用過了就返回false
backup[x] = true;
}
for(int i = 1 ; i <= 9 ; ++ i)//最后再對(duì)abc三個(gè)數(shù)字所選的數(shù)字看看是否選完了0~9個(gè)數(shù)字
if(!backup[i])
return false;
return true;
}
void dfs_c(int u, int a ,int c)
{
if(u > 9) return; //超過9個(gè)數(shù)就可以return
if(check(a,c)) ans ++; //發(fā)現(xiàn)組合就可以 ++ans
for(int i = 1 ; i <= 9 ; ++ i)//去確定c的值
{
if(!st[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; //a不能大于n
if(a) dfs_c(u,a,0);//a不能是0 然后去找c
for(int i = 1 ; i <= 9 ; ++ i)//去確定a的值
{
if(!st[i])
{
st[i] = true;
dfs_a(u + 1,a * 10 + i);
st[i] = false;
}
}
return;
}
int main()
{
cin >> n;
dfs_a(0, 0);// 去遞歸搜索 a 一開始選0個(gè)數(shù)字(用了多少個(gè)數(shù))，a是0。
cout << ans << endl;
return 0;
}
Ⅶ. 飛行員兄弟
0x00 算法思路
先說結(jié)論，在判斷是否要對(duì)(i, j)位置的把手進(jìn)行切換時(shí)，只需要計(jì)算一下第i行和第j列總共7個(gè)把手(以下稱為(i, j)對(duì)應(yīng)的十字)中閉合的把手?jǐn)?shù)目，如果是奇數(shù)個(gè)就進(jìn)行切換，偶數(shù)個(gè)就不進(jìn)行切換。(奇數(shù)個(gè)是該位置的把手進(jìn)行過切換的充要條件)
因此我們從上到下從左到右順次的對(duì)16個(gè)把手進(jìn)行上述判斷。如果判斷結(jié)果是奇數(shù)個(gè)那么說明該位置被切換過，進(jìn)行記錄即可。
0x01 代碼書寫
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 5;
typedef pair<int,int> PII;
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 i = 0; i < 4; i ++ )
{
turn_one(x, i);
turn_one(i, y);
}
turn_one(x, y);
}
int main()
{
for(int i = 0 ; i < 4 ; ++ i) cin >> g[i];
vector<PII> res;
for(int op = 0 ; op < 1 << 16 ; ++ op)
{
vector<PII> temp;
memcpy(backup, g ,sizeof g);
for(int i = 0 ; i < 4 ; ++ i)
for(int j = 0 ; j < 4 ; ++ j)
{
if(op >> get(i, j) & 1)
{
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;
}
if(has_closed == false)
if(res.empty() || res.size() > temp.size()) res = temp;
memcpy(g,backup,sizeof g);
}
cout << res.size() << endl;
for(auto& op : res) cout << op.x + 1 << " " << op.y + 1 << endl;
return 0;
}
Ⅷ. 翻硬幣
0x00 算法思路
將硬幣和目標(biāo)的樣子進(jìn)行比較，當(dāng)發(fā)現(xiàn)不一樣的時(shí)候就進(jìn)行 turn 翻轉(zhuǎn)即可
0x01 代碼書寫
#include<bits/stdc++.h>
using namespace std;
const int N=110;
char start[N], aim[N];
int n;
void turn(int i)
{
if(start[i]=='o') start[i]='*';
else start[i]='o';
}
int main()
{
cin >> start >> aim;
n = strlen(start);
int res=0;
for(int i = 0; i < n - 1 ; i ++)
{
if(start[i] != aim[i])
{
turn(i), turn(i+1);
res ++;
}
}
cout << res << endl;
return 0;
}
總結(jié)
本篇博客主要講解了遞推與遞歸的算法，也涉及到了 dfs 搜索算法的使用，其實(shí) dfs 算法可以文章來源：http://www.zghlxwxcb.cn/news/detail-719851.html
- 先去想dfs的含義，參數(shù)的含義
- 找到dfs的結(jié)束條件進(jìn)行收獲結(jié)果
- 根據(jù)題目要求實(shí)現(xiàn)dfs代碼
希望自己可以多多練習(xí)，后面藍(lán)橋杯輔導(dǎo)課看完就會(huì)去看算法提高課繼續(xù)提升文章來源地址http://www.zghlxwxcb.cn/news/detail-719851.html
到了這里，關(guān)于藍(lán)橋杯---第一講 遞歸與遞推的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
