例題

AcWing 92. 遞歸實現(xiàn)指數(shù)型枚舉

從 1～n 這 n 個整數(shù)中隨機選取任意多個，輸出所有可能的選擇方案。

輸入格式
輸入一個整數(shù) n。

輸出格式
每行輸出一種方案。

同一行內(nèi)的數(shù)必須升序排列，相鄰兩個數(shù)用恰好 1 個空格隔開。

對于沒有選任何數(shù)的方案，輸出空行。

本題有自定義校驗器（SPJ），各行（不同方案）之間的順序任意。

數(shù)據(jù)范圍

1≤n≤15

輸入樣例：

3

輸出樣例：

3 2 2 3 1 1 3 1 2 1 2 3

思路 ：

• 實際上每個數(shù)只要考慮選（1）和不選（2）這兩個狀態(tài)，也就是說回溯回來不需要恢復成0，相當于每個結點有兩個分叉，所以是 $2^n$ 指數(shù)型枚舉
• dfs時，結束遞歸時一定要return

#include <iostream> using namespace std;const int N = 16;int n; int st[N]; // 0表示還沒考慮 1表示選 2表示不選void dfs(int u) {if (u > n){for (int i = 1; i <= n; i ++ )if (st[i] == 1)printf("%d ", i);puts("");return ;}st[u] = 2;dfs(u + 1);// st[u] = 0;st[u] = 1;dfs(u + 1);// st[u] = 0; }int main() {scanf("%d", &n);dfs(1);return 0; }

AcWing 94. 遞歸實現(xiàn)排列型枚舉

把 1～n 這 n 個整數(shù)排成一行后隨機打亂順序，輸出所有可能的次序。

輸入格式
一個整數(shù) n。

輸出格式
按照從小到大的順序輸出所有方案，每行 1 個。

首先，同一行相鄰兩個數(shù)用一個空格隔開。

其次，對于兩個不同的行，對應下標的數(shù)一一比較，字典序較小的排在前面。

數(shù)據(jù)范圍

1≤n≤9

輸入樣例：

3

輸出樣例：

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

思路 ：

• 有$n?(n?1)?...?1$種排列方式，因此是排列型枚舉
• 每次遞歸決定當前這個盒子中放什么數(shù)字，由于不重復放，因此開一個數(shù)組記錄當前是否用過這個數(shù)字，因此回溯要恢復現(xiàn)場

#include <iostream> using namespace std;const int N = 10;int n; int state[N]; bool st[N];void dfs(int u) {if (u > n){for (int i = 1; i <= n; i ++ )printf("%d ", state[i]);puts("");return ;}for (int i = 1; i <= n; i ++ ){if (!st[i]){st[i] = true;state[u] = i;dfs(u + 1);// state[u] = 0;st[i] = false;}} }int main() {scanf("%d", &n);dfs(1);return 0; }

AcWing 717. 簡單斐波那契

以下數(shù)列 0 1 1 2 3 5 8 13 21 … 被稱為斐波納契數(shù)列。

這個數(shù)列從第 3 項開始，每一項都等于前兩項之和。

輸入一個整數(shù) N，請你輸出這個序列的前 N 項。

輸入格式
一個整數(shù) N。

輸出格式
在一行中輸出斐波那契數(shù)列的前 N 項，數(shù)字之間用空格隔開。

數(shù)據(jù)范圍

0<N<46

輸入樣例：

5

輸出樣例：

0 1 1 2 3 // 遞推 #include <iostream> using namespace std;int main() {int n; scanf("%d", &n);int a = 0, b = 1, c;for (int i = 0; i < n; i ++ ){printf("%d ", a);c = a + b, a = b, b = c;} } #include <iostream> using namespace std;const int N = 47;int n; int f[N];int dfs(int u) {if (u == 1 || u == 2 || f[u]) return f[u];return f[u] = dfs(u - 1) + dfs(u - 2); }int main() {scanf("%d", &n);f[1] = 0, f[2] = 1;dfs(n);for (int i = 1; i <= n; i ++ ) cout << f[i] << ' ' ;return 0; }

AcWing 95. 費解的開關

你玩過“拉燈”游戲嗎？

25 盞燈排成一個 5×5 的方形。

每一個燈都有一個開關，游戲者可以改變它的狀態(tài)。

每一步，游戲者可以改變某一個燈的狀態(tài)。

游戲者改變一個燈的狀態(tài)會產(chǎn)生連鎖反應：和這個燈上下左右相鄰的燈也要相應地改變其狀態(tài)。

我們用數(shù)字 1 表示一盞開著的燈，用數(shù)字 0 表示關著的燈。

下面這種狀態(tài)

10111
01101
10111
10000
11011
在改變了最左上角的燈的狀態(tài)后將變成：

01111
11101
10111
10000
11011
再改變它正中間的燈后狀態(tài)將變成：

01111
11001
11001
10100
11011
給定一些游戲的初始狀態(tài)，編寫程序判斷游戲者是否可能在 6 步以內(nèi)使所有的燈都變亮。

輸入格式
第一行輸入正整數(shù) n，代表數(shù)據(jù)中共有 n 個待解決的游戲初始狀態(tài)。

以下若干行數(shù)據(jù)分為 n 組，每組數(shù)據(jù)有 5 行，每行 5 個字符。

每組數(shù)據(jù)描述了一個游戲的初始狀態(tài)。

各組數(shù)據(jù)間用一個空行分隔。

輸出格式
一共輸出 n 行數(shù)據(jù)，每行有一個小于等于 6 的整數(shù)，它表示對于輸入數(shù)據(jù)中對應的游戲狀態(tài)最少需要幾步才能使所有燈變亮。

對于某一個游戲初始狀態(tài)，若 6 步以內(nèi)無法使所有燈變亮，則輸出 ?1。

數(shù)據(jù)范圍

0<n≤500

輸入樣例：

3 00111 01011 10001 11010 1110011101 11101 11110 11111 1111101111 11111 11111 11111 11111

輸出樣例：

3 2 -1

思路 ：

• 目標是把所有開關全部變成1，由于當上一行的狀態(tài)確定時，若上一行存在0的狀態(tài)，只能由下一行的位置影響上一行的0（注意這是四連通），因此可以使用遞推
• 只要第0行開關狀態(tài)確定，則所有開關的狀態(tài)都可以遞推出來，因此只要枚舉第一行狀態(tài)的所有情況，有$2^5$種
• 從第0行遞推出第1到第4行的所有狀態(tài)，若當前行狀態(tài)已確定，且存在開關是0狀態(tài)的，則需要下一行的位置對開關進行切換，影響當前行開關是0的狀態(tài)
• 最后枚舉最后一行，若該狀態(tài)全部是1，則表示成功，更新最小步數(shù)

語法 ：

• char二維數(shù)組的輸入方式
• 第一行一共32種狀態(tài)，也就是$[0,31]$，op >> i & 1
• 每種枚舉方式中，一開始用backup備份g，最后再備份回來
• 如果res大于6，直接賦值為-1
• 即使g二維數(shù)組是char類型，但可以g[a][b]^=1，0變成1，1變成0

#include <iostream> #include <cstring> using namespace std;const int N = 6;char g[N][N], backup[N][N]; int dx[5] = {0, 1, 0, -1, 0}, dy[5] = {1, 0, -1, 0, 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 > 4 || b < 0 || b > 4) continue;g[a][b] ^= 1;} }int main() {int _; scanf("%d", &_);while (_ -- ){for (int i = 0; i < 5; i ++ ) cin >> g[i];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 ++ )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 backup);}if (res > 6) res = -1;printf("%d\n", res);} }

習題

AcWing 93. 遞歸實現(xiàn)組合型枚舉

從 1～n 這 n 個整數(shù)中隨機選出 m 個，輸出所有可能的選擇方案。

輸入格式
兩個整數(shù) n,m ,在同一行用空格隔開。

輸出格式
按照從小到大的順序輸出所有方案，每行 1 個。

首先，同一行內(nèi)的數(shù)升序排列，相鄰兩個數(shù)用一個空格隔開。

其次，對于兩個不同的行，對應下標的數(shù)一一比較，字典序較小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

數(shù)據(jù)范圍

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第一個參數(shù)為當前放到第i個位置（一共m個），第二個參數(shù)為這一次開始選擇的數(shù)字（比上一次的大）
• 枚舉邊界為放到第m+1個位置，也就是說放完了
• 剪枝，加上后面放的數(shù)不足m個

#include <iostream> using namespace std;const int N = 30;int n, m; int state[N];void dfs(int u, int start) {if (u + n - start < m) return ;if (u == m + 1){for (int i = 1; i <= m; i ++ )cout << state[i] << ' ';cout << endl;return ;}for (int i = start; i <= n; i ++ ){state[u] = i;dfs(u + 1, i + 1);} }int main() {cin >> n >> m;dfs(1, 1);return 0; }

AcWing 1209. 帶分數(shù)

100 可以表示為帶分數(shù)的形式：100=3+69258714
還可以表示為：100=82+3546197
注意特征：帶分數(shù)中，數(shù)字 1～9 分別出現(xiàn)且只出現(xiàn)一次（不包含 0）。

類似這樣的帶分數(shù)，100 有 11 種表示法。

輸入格式
一個正整數(shù)。

輸出格式
輸出輸入數(shù)字用數(shù)碼 1～9 不重復不遺漏地組成帶分數(shù)表示的全部種數(shù)。

數(shù)據(jù)范圍

1≤N<106

輸入樣例1：

100

輸出樣例1：

11

輸入樣例2：

105

輸出樣例2：

6

思路 ：

• 給一個數(shù)n，問有多少組$a+\frac{b}{c}=n$，且abc三個數(shù)不重不漏地涵蓋1-9這9個數(shù)字
• 暴力枚舉9個數(shù)的全排列，然后用一個長度為9的數(shù)組保存全排列的結果
• 從全排列的結果中用兩重循環(huán)暴力分解出三段，每段代表一個數(shù)
• 驗證枚舉出的三個數(shù)是否滿足題干條件，若滿足則計數(shù)

#include <iostream> using namespace std;int n, cnt; bool st[10]; int state[10];int calc(int l, int r) {int res = 0;for (int i = l; i <= r; i ++ )res = res * 10 + state[i];return res; }void dfs(int u) {if (u == 10){for (int i = 1; i < 10; i ++ )for (int j = i + 1; j < 9; j ++ ){int a = calc(1, i);int b = calc(i + 1, j);int c = calc(j + 1, 9);if (a * c + b == n * c) cnt ++ ;}return ;}for (int i = 1; i <= 9; i ++ )if (!st[i]){state[u] = i;st[i] = true;dfs(u + 1);st[i] = false;} }int main() {cin >> n;dfs(1);cout << cnt << endl;return 0; }

AcWing 116. 飛行員兄弟

“飛行員兄弟”這個游戲，需要玩家順利的打開一個擁有 16 個把手的冰箱。

已知每個把手可以處于以下兩種狀態(tài)之一：打開或關閉。

只有當所有把手都打開時，冰箱才會打開。

把手可以表示為一個 4×4 的矩陣，您可以改變?nèi)魏我粋€位置 [i,j] 上把手的狀態(tài)。

但是，這也會使得第 i 行和第 j 列上的所有把手的狀態(tài)也隨著改變。

請你求出打開冰箱所需的切換把手的次數(shù)最小值是多少。

輸入格式
輸入一共包含四行，每行包含四個把手的初始狀態(tài)。

符號 + 表示把手處于閉合狀態(tài)，而符號 - 表示把手處于打開狀態(tài)。

至少一個手柄的初始狀態(tài)是關閉的。

輸出格式
第一行輸出一個整數(shù) N，表示所需的最小切換把手次數(shù)。

接下來 N 行描述切換順序，每行輸出兩個整數(shù)，代表被切換狀態(tài)的把手的行號和列號，數(shù)字之間用空格隔開。

注意：如果存在多種打開冰箱的方式，則按照優(yōu)先級整體從上到下，同行從左到右打開。

數(shù)據(jù)范圍

1≤i,j≤4

輸入樣例：

-+-- ---- ---- -+--

輸出樣例：

6 1 1 1 3 1 4 4 1 4 3 4 4

思路 ：

• 本題比較特殊，可以用代碼把所有情況枚舉一遍，會發(fā)現(xiàn)每種局面的操作方案是唯一的，所以第一次找到的解一定是最優(yōu)解。
• $2^{16}?16?16$

#include <iostream> #include <cstring> #include <vector> using namespace std;typedef pair<int, int> PII;char g[4][4], backup[4][4];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 ++ ){memcpy(backup, g, sizeof backup);vector<PII> temp;for (int i = 0; i < 4; i ++ )for (int j = 0; j < 4; j ++ )if (op >> get(i, j) & 1){turn_all(i, j);temp.push_back({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 backup);}cout << res.size() << endl;for (auto op : res) cout << op.first + 1 << ' ' << op.second + 1 << endl; }

AcWing 1208. 翻硬幣

小明正在玩一個“翻硬幣”的游戲。

桌上放著排成一排的若干硬幣。我們用 * 表示正面，用 o 表示反面（是小寫字母，不是零）。

比如，可能情形是：oo*oooo

如果同時翻轉(zhuǎn)左邊的兩個硬幣，則變?yōu)?#xff1a;oooo***oooo

現(xiàn)在小明的問題是：如果已知了初始狀態(tài)和要達到的目標狀態(tài)，每次只能同時翻轉(zhuǎn)相鄰的兩個硬幣,那么對特定的局面，最少要翻動多少次呢？

我們約定：把翻動相鄰的兩個硬幣叫做一步操作。

輸入格式
兩行等長的字符串，分別表示初始狀態(tài)和要達到的目標狀態(tài)。

輸出格式
一個整數(shù)，表示最小操作步數(shù)

數(shù)據(jù)范圍
輸入字符串的長度均不超過100。
數(shù)據(jù)保證答案一定有解。

輸入樣例1：

********** o****o****

輸出樣例1：

5

輸入樣例2：

*o**o***o*** *o***o**o***

輸出樣例2：

1

思路 ：

• 規(guī)則是每次翻轉(zhuǎn)兩個相鄰的硬幣，一個硬幣要翻轉(zhuǎn)必會使左右兩邊其中一個受到牽連，因此可以貪心單一方向進行牽連，就不會使之前翻好的硬幣重新翻轉(zhuǎn)

#include <iostream> #include <cstring> using namespace std;const int N = 110;int n; char s1[N], s2[N];void turn(int i) {if (s1[i] == '*') s1[i] = 'o';else s1[i] = '*'; }int main() {cin >> s1 >> s2;n = strlen(s1);int res = 0;for (int i = 0; i < n; i ++ )if (s1[i] != s2[i]){turn(i), turn(i + 1);res ++ ;}cout << res << endl; }

總結

以上是生活随笔為你收集整理的蓝桥杯C++ AB组辅导课 第一讲 递归与递推 Acwing的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。