【算法基礎】遞歸與遞推

遞歸實現指數型枚舉

題目?

算法解析?

遞歸實現排列型枚舉

題目?

算法解析?

費解的開關

題目?

?算法解析

遞歸實現組合型枚舉

題目?

算法解析?

帶分數

題目?

算法解析?

?飛行員兄弟

?題目

算法解析?

翻硬幣

題目?

算法解析?

遞歸實現指數型枚舉

題目?

算法解析?

?對于1-n中任意的數來說，考慮這個數時只會面臨兩種情況

最終結果選擇該數
最終結果不選擇該數

我們只需要枚舉每個數的兩個狀態：選和不選，考慮完后遞歸到下一層考慮下一個數即可

時間復雜度：2 × 2 .... × 2 = 2 ^ n

題中n為15，2^15 =?32768?，符合要求

代碼：

#include <iostream>
using namespace std;
const int N = 16;
int path[N];
bool st[N]; //st[i]為true，表示選第i個數，st[i]為false，表示不選該數
int n;
void dfs(int u)
{if(u > n){//前n個數全部考慮完了，輸出方案for(int i = 1 ; i <= n ; ++i)if(st[i]) cout << i << " ";cout << endl;return;}//1.不選u，直接進入到下一層dfs(u+1);//2.選u，進入到下一層st[u] = true;dfs(u+1);st[u] = false; //恢復現場
}
int main()
{cin >> n;dfs(1); return 0;
}

遞歸實現排列型枚舉

題目?

算法解析?

首先考慮排列型枚舉與指數型枚舉的區別

指數型枚舉考慮的角度是對于1-n中的所有數，選和不選所產生的所有方案。
排列型枚舉考慮的角度是對于1-n中的所有數必須選。它們分別可以放在哪個位置?

所以排列型枚舉的結果長度已經是固定了。我們分別考慮每個位置能放哪個元素。

假設n為3，可以畫出如下樹

只需要通過深度優先遍歷，當遍歷到樹的葉子節點時就把答案數組輸出
具體操作就是考慮答案數組的第一個位置填什么，若填的數是合法的，那么就遞歸到下一層
注意：不能填已經填過的數，例如第一個位置填的是3，那么我們填第二個位置時就不能填3了。我們可以使用一個st數組來標識這個位置能填什么

時間復雜度：O(n! * n)

該題中n為10，10! * 10 =?36288000，由于代碼常數比較小，所以該數量級其實符合題目要求

代碼：

#include <iostream>
using namespace std;
const int N = 10;
int path[N]; //答案數組
bool st[N]; //st[i] 為true標識i不能選了，為false表示能選i
int n;
void dfs(int u)
{if(u > n) //前n個位置都考慮完了輸出即可{for(int i = 1 ; i <= n ; ++i)cout << path[i] << " ";cout << endl;return;}for(int i = 1 ; i <= n ; ++i){if(!st[i]){path[u] = i; //第u個數填ist[i] = true;dfs(u+1);st[i] = false; //恢復現場}}
}
int main()
{cin >> n;dfs(1); //從第1個位置開始考慮return 0;
}

費解的開關

題目?

?算法解析

首先先考慮暴力枚舉的方式，我們是否可以用指數型枚舉的方式來枚舉所有的按法呢？

實際上是可以的，每一個位置的按鈕都只有按和不按兩種狀態，如果我們枚舉所有方案，那么正確答案一定會被枚舉到。

但時間復雜度為O(2^25 n)，題目中2^25? =?33554432 , 而題目中n為500，顯然必超時。

注意：對于有些相似題目來說，其實可以使用暴力解法的，這里把暴力解法也留在下面。

代碼：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 6;
int T;
char g[N][N] , backup[N][N];
int dx[5] = {-1,0,1,0,0} , dy[5] = {0,0,0,-1,1};
//dx為方向向量，對應為上、中、下、左、右
//turn函數的功能是按下(x,y)位置的按鈕，并處理它所帶來的連鎖反應
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){g[a][b] = ((g[a][b] - '0') ^ 1) + '0'; //按下開關(0變1,1變0)}}
}int main()
{cin >> T;while(T--){for(int i = 0 ; i < 5 ; ++i)    scanf("%s",g[i]);//枚舉所有方案int res = 10;memcpy(backup,g,sizeof g);for(int i = 0 ; i < 1 << 25 ; ++i){int step = 0;for(int j = 0 ; j < 25 ; ++j){if(i >> j & 1){step++;turn(j / 5 , j % 5);}}bool has_sol = true;//判斷該方案是否為解for(int j = 0 ; j < 5 ; ++j)for(int k = 0 ; k < 5 ; ++k)if(g[j][k] == '0') has_sol = false;if(has_sol && step <= 6) res = min(res , step);memcpy(g,backup,sizeof backup);}if(res <= 6) cout << res << endl;else cout << "-1" << endl;}return 0;
}

接下來就是說明一下正解了。

假設我們已經知道了第一行應該怎么按最后才能得到解，接下來考慮第二行時我們應該怎么做呢？

由于第一行得按法已經確定了，那么此時第二行必須使得第一行當中為0的位置變為1，因為題目要求全部為1。如果第一行的某個位置在按完以后為1，那么我們在第二行按的時候就絕對不能按它對應的位置，因為他會使得第一行的1變為0

如下圖：

第一行確定，假設如下：

由于第一行為0的位置下面的位置必須按，第一行為1的位置必須不按，所以第二行怎么按實際上是確定的，如下圖：

此時第三行與第二行考慮的方式也一樣，第二行為0的位置下面的位置必須得按，第二行為1的位置下面的位置必須不按。不再贅述了

當最終到了第5行，由于已經沒有第6行來改變它的狀態了，那么此時如果第5行為0那也沒辦法，說明沒解。如果第五行為1說明有解，統一一下按的次數，如果小于6，則更新結果。

最后一個問題：第一行怎么按是怎么確定的呢？

我們可以通過指數型枚舉的方式枚舉第一行的按法，如果有正確按法，則枚舉一定能枚舉到

時間復雜度：2^5*5*n =80000，符合題目要求

代碼：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 6;
int T;
char g[N][N] , backup[N][N];
int dx[5] = {-1,0,1,0,0} , dy[5] = {0,0,0,-1,1};
//dx為方向向量，對應為上、中、下、左、右
//turn函數的功能是按下(x,y)位置的按鈕，并處理它所帶來的連鎖反應
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){g[a][b] = ((g[a][b] - '0') ^ 1) + '0'; //按下開關(0變1,1變0)}}
}int main()
{cin >> T;while(T--){for(int i = 0 ; i < 5 ; ++i)    scanf("%s",g[i]);//枚舉所有方案int res = 10;memcpy(backup,g,sizeof g);for(int i = 0 ; i < 1 << 5 ; ++i){int step = 0;for(int j = 0 ; j < 5 ; ++j){if(i >> j & 1){step++;turn(0 , j);}}//第一行確定了接下來的所有行的按法都確定了for(int j = 0 ; j < 4 ; ++j){for(int k = 0 ; k < 5 ; ++k)if(g[j][k] == '0'){step++;turn(j+1,k);}}bool has_sol = true;//判斷該方案是否為解，第五行是否有0for(int j = 0 ; j < 5 ; ++j)if(g[4][j] == '0') has_sol = false;if(has_sol && step <= 6) res = min(res , step);memcpy(g,backup,sizeof backup);}if(res <= 6) cout << res << endl;else cout << "-1" << endl;}return 0;
}

遞歸實現組合型枚舉

題目?

算法解析?

考慮一下組合型枚舉和排列型枚舉的區別

組合型枚舉實際上是排列型枚舉的一種特殊情況，在排列型枚舉中(1,3,2)實際上是和(1,2,3)是完全不同的兩個結果

但在組合型枚舉中(1,3,2)和(1,2,3)是相同的，(1,3,2)和(3,2,1)也是相同的，只有當兩個結果數組中有至少一個元素不同時才會記作答案

所以我們可以約定，組合型枚舉的答案數組一定是單調遞增的，即假設有3個元素1,2,3，那么我們只枚舉(1,2,3)而不枚舉(2,1,3)和(3,2,1)這兩種不是單調遞增的情況。這實際上完成了排列型枚舉剪枝成組合型枚舉

如何實現？

當我們枚舉第u個元素時，從第u-1選擇的元素+1開始枚舉即可

代碼：

#include <iostream>
using namespace std;
const int N = 25;
int path[N] , n , m;void dfs(int u)
{if(u > m) // 如果已經選了m個元素{for(int i = 1 ; i <= m ; ++i)cout << path[i] << " ";cout << endl;return;}for(int i = path[u-1] + 1 ; i <= n ; ++i){path[u] = i;dfs(u+1);}
}int main()
{cin >> n >> m;dfs(1); //從第1個位置開始考慮return 0;
}

帶分數

題目?

算法解析?

簡單來說，該題就是輸入一個n，枚舉出a、b、c三個數，使得a + b/c = n。具體要求如下：

a + b / c = n
b必須能整除c ，即b % c = 0
a、b、c中所有位數，必須包含1-9，這9個數

通過如上分析我們可以得出如下做法：

枚舉全排列(排列型枚舉) 1-9的數
枚舉的全排列一定包含且只出現一次1-9的數
把全排列分成三段，枚舉全排列中a、b、c的值
檢查上述具體要求是否滿足即可?

?時間復雜度：全排列的復雜度和枚舉位數的復雜度：9! * 9 * 45?(盡管有些高，但經過測試還是能過得)

如下代碼：

#include <iostream>
using namespace std;
const int N = 10;
int path[N]; //全排列數組
bool st[N]; //判重數組，用于求全排列
int n;
int res; //結果bool check(int a , int b , int c)
{if(!a || !b || !c) return false; //題目要求不能出現0if(a + b / c == n && b % c == 0) return true; return false;
}void dfs(int u)
{if(u == 9){for(int i = 0 ; i < 9 ; ++i){for(int j = i + 1 ; j < 9 ; ++j){//[0,i) = a//[i,j) = b//[j,9) = cint a = 0 , b = 0 , c = 0;int k = 0;while(k < i){a = a * 10 + path[k];++k;}while(k < j){b = b * 10 + path[k];++k;}while(k < 9){c = c * 10 + path[k];++k;}if(check(a,b,c)) res ++; //判斷a、b、c是否滿足題目要求}}}for(int i = 1 ; i <= 9 ; ++i){if(!st[i]){path[u] = i;st[i] = true;dfs(u+1);st[i] = false;}}
}
int main()
{cin >> n;dfs(0);cout << res << endl;return 0;
}

?飛行員兄弟

?題目

算法解析?

?這題與費解的開關很類似，都是類似于是否按開關的問題，首先考慮他們兩個的區別：

這題的按開關所產生的影響比費解的開關要大的多。在費解的開關中每一次按開關僅僅會影響上下左右四個格子，正因為這種性質，我們可以從1-n-1層開關的按法，唯一的確定第n層的按法。但這題按下開關后，一行一列都會受到影響，換句話來說對于第一層開關的狀態不能將下一層唯一確定，因為它會受到下面所有層的按開關的影響
幸運的是這題的數據范圍比較小，只有4x4的矩陣，且無多組測試用例，這也就意味著我們可以枚舉所有的可能的方案，因為每一個開關只會存在是否按兩種狀態，枚舉所有的按法，也就一定包含了正解

所以最終解法就是：枚舉所有的按法，確定結果的按法。

注意：該題需要我們輸出最小解，如果存在多個最小解則按照從上到下，從左到右的方案來輸出

我們在枚舉按法時，i是從0到2^16次方的，只需要遇到相同步數的解時不要更新結果，當遇到比當前解更小的解時才更新結果即可保證這個性質

時間復雜度：具體的真不好算了，粗略算成2^16 * 16吧，反正能擦邊過

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;
const int N = 5;
char g[N][N] , backup[N][N];void turn(int x , int y)
{for(int i = 0 ; i < 4 ; ++i)if(g[x][i] == '+') g[x][i] = '-';else g[x][i] = '+';for(int i = 0 ; i < 4 ; ++i)if(g[i][y] == '+') g[i][y] = '-';else g[i][y] = '+';if(g[x][y] == '+') g[x][y] = '-';else g[x][y] = '+';
}int main()
{for(int i = 0 ; i < 4 ; ++i)scanf("%s",g[i]);memcpy(backup,g,sizeof g); //保存一下原始狀態vector<PII> path; //結果路徑int res = 1e9; //最小解//1.先枚舉所有的按法for(int i = 0 ; i < 1 << 16 ; ++i){int step = 0;vector<PII> temp;for(int j = 0 ; j < 16 ; ++j){if(i >> j & 1) // 如果為1則表示按下開關，否則表示不按{turn(j / 4 , j % 4);step++;temp.push_back({j / 4 , j % 4});}}bool has_sol = true; //判斷是否有解for(int j = 0 ; j < 4 ; ++j)for(int k = 0 ; k < 4 ; ++k)if(g[j][k] == '+') has_sol = false;if(has_sol && step < res) //如果有解，且比當前的最小解還小就更新一下{res = min(res , step);path = temp;}memcpy(g,backup,sizeof backup);//還原原始狀態}cout << res << endl;for(int i = 0 ; i < path.size() ; ++i){//題目中下標是從1開始的所以需要+1cout << path[i].first + 1 << " " << path[i].second + 1<< endl;}return 0;
}

翻硬幣

題目?

算法解析?

對于第一個字符串來說，它的第i個位置的狀態僅由第i-1個位置和第i個位置決定

依次類推，第i-1個位置的狀態僅由i-2位置和i-1位置決定，直到第0個位置，僅由第0個位置決定

那么第0個位置是不是要翻取決于它是否與目標字符串第0個位置相等，同理第1個位置是否要翻取決于遍歷到第1個位置時它是否與目標字符串第1個位置相等

換句話來說，我們從前往后遍歷第一個字符串，當第i個位置與目標字符串不符合時我們就翻一下硬幣，最終如果有解那么一定會翻成跟目標字符串一樣且是最小的解

代碼如下：

#include <iostream>
#include <string>
using namespace std;string src , dst;
void turn(int i)
{src[i] = (src[i] == '*' ? 'o' : '*');if(i+1 < src.size())src[i+1] = (src[i+1] == '*' ? 'o' : '*');
}
int main()
{cin >> src >> dst;int res = 0;for(int i = 0 ; i < src.size() ; ++i){if(src[i] != dst[i]){turn(i);res++;}}cout << res << endl;return 0;
}