「學習筆記」遞推 & 遞歸
引入
假設我們想計算 \(f(x) = x!\)。除了簡單的 for 循環，我們也可以使用遞歸。
遞歸是什麼意思呢？我們可以把 \(f(x)\) 用 \(f(x – 1)\) 表示，即 \(f(x) = x \times f(x – 1)\)。這樣，我們就可以不斷地遞歸下去。
但是，這是永遠不會停止的。我們需要設立一個邊界條件，\(f(0) = 1\)。這樣，我們就可以寫出程式碼了。
int f(int x) {return x ? x * f(x - 1) : 1;}
實際上，遞歸有兩大要點：
- 自己調用自己；
- 回溯時還原現場。
如果你看到這裡，你或許已經懂了遞歸。那麼，遞推是什麼呢？把上面的計算階乘的遞歸改成遞推就是這樣的：
f[0] = 1;
for (int i = 1; i <= n; i++)
f[i] = f[i - 1] * i;
一個有趣的例子：什麼是遞歸？
「例題」數樓梯
原題目鏈接：Link。
我們用遞推的視角思考一下。假設我們要走到第 \(i\) 階台階，我們應該怎樣走？
記走第 \(i\) 階台階的走法為 \(f_i\)，則顯然，我們可以從第 \(i – 1\) 階台階上一階台階到第 \(i\) 階台階，也可以從第 \(i – 2\) 階台階上二階台階到第 \(i\) 階台階。根據加法原理，有 \(f_i = f_{i – 1} + f_{i – 2}\)。
遞推邊界可以根據題意得到。一階台階有 \(1\) 種走法，二階台階有 \(2\) 種走法，即 \(f_1 = 1, f_2 = 2\)。
// Python Version
n = int(input())
a, b = 1, 2
if n < 3:
print(n)
for i in range(n - 2):
c = a + b
a, b = b, c
if n >= 3:
print(c)
# 可以使用滾動數組來優化，這裡 a 相當於 f[i - 2]，b 相當於 f[i - 1]，c 相當於 f[i]
# 注意特判
// C++ Version
#include <bits/stdc++.h>
using namespace std;
int n;
long long f[5005] = {0, 1, 2};
int main() {
cin >> n;
for (int i = 3; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
cout << f[n] << endl;
return 0;
}
這裡 C++ 只能得到 \(60\) 分。這是因為我們得到的結果超出了 long long 的表示範圍，需要使用高精度。
五大遞推模型
Fibonacci 數列
Fibonacci 數列，一般譯為斐波那契數列。Fibonacci 數列的邊界為 \(f_1 = f_2 = 1\)，遞推柿為 \(f_i = f_{i – 1} + f_{i – 2}\)。上面的數樓梯就是 Fibonacci 數列從第 \(2\) 項開始的數列。
Fibonacci 數列還有一種表現形式，就是可愛的小兔子。
「例題」兔子的數量
原題目鏈接：Link。
可以輕鬆寫出程式碼。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
int a[MAXN] = {0, 1, 1}, n;
int main() {
cin >> n;
for (int i = 3; i <= n; i++)
a[i] = a[i - 1] + a[i - 2];
cout << a[n] << endl;
return 0;
}
Fibonacci 數列還有一個通項公式：\(f_n = \frac1{\sqrt5}[(\frac{1 + \sqrt5}{2}) ^ n – (\frac{1 – \sqrt5}{2}) ^ n]\)。
Catalan 數
Catalan 數的實際應用很多。這裡我們來通過一道 NOIP 的題目來引出 Catalan 數。
「例題」棧
原題目鏈接：Link。
我們可以設 \(i\) 個小球時，出管方式為 \(h_i\)。我們於是可以按最後一個出管的小球來討論。假設最後一個出管的為第 \(k\) 個小球，那麼比 \(k\) 早入管的小球為 \(k – 1\) 個，比 \(k\) 晚入管的小球為 \(n – k\) 個。這些小球全部出管之後，第 \(k\) 個小球才出管。根據乘法原理，最後一個出管的小球為第 \(k\) 個時，取法總數為 \(h_{k – 1} \times h_{n – k}\)。而 \(k\) 可以取 \(1\) 到 \(n\)。所以總共的取法總數就是 \(h_n = \sum_{i = 1} ^ n h_{i – 1} \times h_{n – i}\)。這就是 Catalan 數的遞推柿了。遞推邊界顯然：\(f_0 = f_1 = 1\)。
#include <bits/stdc++.h>
using namespace std;
int n, h[20] = {1, 1};
int main() {
cin >> n;
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
h[i] += h[j - 1] * h[i - j];
cout << h[n] << endl;
return 0;
}
Catalan 數列的應用：
- 把一個凸 \(n\) 邊形劃分為數個三角形的方案數（不相交）。
- 一個棧的進棧序列為 \(1, 2, 3, \dots, n\)，不同的出棧序列數。
- \(n\) 個節點可以構造多少個不同的二叉樹的方案數。
- 在圓上選擇 \(2 \times n\) 個點，把這些點成對連接起來使得所得到的 \(n\) 條線段不相交的方法數。
- 從點 \((0, 0)\) 到點 \((n, n)\)，不穿越但可以碰到對角線的最短走法數。
除了遞推，Catalan 數 \(h_n\) 還可以通過通項公式得到：\(h_n = \frac{C_{2n} ^ n}{n + 1} = C_{2n} ^ n – C_{2n} ^ {n – 1}\)。
Hanio 塔
Hanio 塔是一個非常經典的遞推（遞歸）問題。或許很多人在感受 C++ 的強大時，教練展示的第一個程式就是 Hanio 塔。
「例題」Hanio 塔問題
原題目鏈接：Link。
我們設 \(h_i\) 為移動 \(i\) 個盤子所需要的次數。顯然地，我們可以先把上面的 \(i – 1\) 個盤子移動到 B 柱上，再把第 \(i\) 的盤子移到 C 柱上，最後把 B 盤上的 \(i – 1\) 個盤子移到 C 柱上。那麼，遞推柿就出來了：\(h_i = 2 \times h_{i – 1} + 1\)，邊界 \(h_1 = 1\)。Hanio 塔同樣有通項公式 \(h_n = 2 ^ n – 1\)。
# Python Version
n = int(input())
# print(2 ** n - 1)
# 這樣可以直接輸出
a = 1
for i in range(n - 1):
a = a * 2 + 1
print(a)
// C++ version
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 65;
long long a[MAXN] = {0, 1};
int n;
int main() {
cin >> n;
for (int i = 2; i <= n; i++)
a[i] = a[i - 1] << 1 | 1;
cout << a[n] << endl;
return 0;
}
第二類 Stirling 數
「例題」合理放球
原題目鏈接：Link。
我們可以設 \(S_{n, m}\) 為 \(n\) 個不相同的球放入 \(m\) 個相同的盒子（不為空）里的放法總數。
思考對於第 \(n\) 個球的放法。我們可以把這第 \(n\) 個球單獨放一個盒子，那麼前面的 \(n – 1\) 個球就要擠占 \(m – 1\) 個盒子，方案數為 \(S_{n – 1, m – 1}\)；也可以把這第 \(n\) 個球與其他的球共佔一個盒子，那麼前面的 \(n – 1\) 個球就要擠占 \(m\) 個盒子（第 \(n\) 個球沒有額外佔用盒子），那麼方案數為 \((n – 1) \times S_{n – 1, m}\)。由加法原理知，\(S_{n, m} = S_{n – 1, m – 1} + (n – 1) \times S_{n – 1, m}\)。
遞推邊界：\(S_{n, n} = S_{n, 1} = S_{1, m} = 1\)。
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long S(int n, int m) {
if (n == 1 || m == 1 || n == m) return 1;
return S(n - 1, m - 1) + m * S(n - 1, m);
}
int main() {
scanf("%d %d", &n, &m);
printf("%lld\n", S(n, m));
return 0;
}
分割平面問題
這類問題比較多變，有時很困難，重點是要去找到規律（廢話）。
「例題」分割平面
題意簡述：設有 \(n\) 條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交於兩點，且任何三條封閉曲線不相交於同一點，問這些封閉曲線把平面分割成的區域個數。
數據範圍：\(1 \leq n \leq 46314\)。
觀察圖片，可以發現，如果設 \(f_n\) 表示由 \(n\) 條封閉曲線時，題意中的區域個數，則有 \(f_n = f_{n – 1} + 2 \times (i – 1)\)。\(f_1 = 2\)。
證明也比較顯然。當畫第 \(n\) 條曲線時，會與每條之前畫的 \(n – 1\) 條曲線形成 \(2\) 個交點，多一個交點就多一個區域，由此可得。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 46350;
int n;
long long a[MAXN] = {0, 2};
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++)
a[i] = a[i - 1] + ((i - 1) << 1);
printf("%lld\n", a[n]);
return 0;
}
讓我們再來看一道題，加深印象。
「例題」分割平面之二
題意簡述：同一平面內有 \(n\) 條直線，已知其中 \(p\) 條直線相交於同一點，則這 \(n\) 條直線最多能將平面分割成多少個不同的區域？
數據範圍：\(2 \leq p \leq n \leq 500\)。
與上一題類似地設出 \(f_n\)。畫圖容易發現 \(p\) 條直線相交於同一點會產生 \(2p\) 個區域，第 \(i\) 條直線會相交多產生 \(i\) 個區域，所以有 \(f_i = f_{i – 1} + i (i > p)\)，邊界為 \(f_p = 2p\)。
#include <bits/stdc++.h>
using namespace std;
int n, p;
int f[505];
int main() {
cin >> n >> p;
f[p] = p << 1;
for (int i = p + 1; i <= n; i++)
f[i] = f[i - 1] + i;
cout << f[n] << endl;
return 0;
}
記憶化
有些時候，使用遞歸會超時，原因是進行了大量的重複運算導致效率低下。而記憶化就可以提升效率。甚至於你可以用記憶化搜索來代替 DP。
「例題」Function
原題目鏈接：Link。
我們可以按題意容易地寫出樸素程式碼：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
#define LL long long
LL a, b, c;
int w(LL a, LL b, LL c) {
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
if (a < b && b < c) return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
return w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}
int main() {
while (~scanf("%lld %lld %lld", &a, &b, &c)) {
if (a == -1 && b == -1 && c == -1) break;
printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));
}
return 0;
}
試一試樣例，哇，只用了 \(22\) 毫秒就過了！
然後交上去，快樂 TLE。
這是為什麼呢？如果我們把 \(w\) 函數加上 cout << a << " " << b << " " << c << endl;，再運行，你會發現輸出了很多行，但其中有許多是重複的。
這啟發我們，可以用一個數組 \(f\) 來存儲 \(w_{a, b, c}\)，如果已經得到過這個值就可以直接返回，避免無效運算。這就是記憶化。在這道題中，我們使用 \(-1\) 表示沒有算過。具體地說，如果 \(f_{a, b, c} = -1\)，那麼沒有計算過，我們就直接計算，並把結果存儲在 \(f_{a, b, c}\) 中；否則算過就直接 return \(f_{a, b, c}\) 即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
#define LL long long
int f[MAXN][MAXN][MAXN];
LL a, b, c;
int w(LL a, LL b, LL c) {
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
if (a < b && b < c) {
if (f[a][b][c] != -1) return f[a][b][c];
// 如果已經得到值，直接返回
return f[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
// 否則計算這個值，並存儲起來，下一次就不會繼續遞歸了
}
if (f[a][b][c] != -1) return f[a][b][c];
// 同上
return f[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}
int main() {
memset(f, -1, sizeof(f)); // 全部初始化為 -1 表示沒有得到值
while (~scanf("%lld %lld %lld", &a, &b, &c)) {
if (a == -1 && b == -1 && c == -1) break;
printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));
}
return 0;
}
怎麼樣，你學廢了嗎？
讓我們一起來看一道 IOI 的題目（好吧是 \(1994\) 年的）。
「例題」數字三角形 Number Triangles
原題目鏈接：Link。
假設你不會遞推。我們可以設 \(f_{i, j}\) 表示從 \((i, j)\) 走到最底下的最大的和。那麼，顯然有 \(f_{i, j} = w_{i, j} + \max(f_{i + 1, j}, f_{i + 1, j + 1})\)。寫成程式碼就是這樣的：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n;
int w[MAXN][MAXN];
int f(int i, int j) {
if (i == n) return w[i][j]; // 已經不能再走了，直接返回 w[i][j]
return w[i][j] + max(f(i + 1, j), f(i + 1, j + 1));
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> w[i][j];
cout << f(1, 1) << endl;
return 0;
}
但這還是會超時，怎麼辦呢？
沒錯，我們可以使用記憶化。類似地，我們用 \(-1\) 表示沒搜過 \((i, j)\)，如果不等於 \(-1\) 直接 return 即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n;
int w[MAXN][MAXN], ans[MAXN][MAXN];
int f(int i, int j) {
if (i == n) return w[i][j];
if (ans[i][j] != -1) return ans[i][j];
return ans[i][j] = w[i][j] + max(f(i + 1, j), f(i + 1, j + 1));
}
int main() {
memset(ans, -1, sizeof(ans));
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> w[i][j];
cout << f(1, 1) << endl;
return 0;
}
其實，這已經有點 DP 的意味了。
雜題
「例題」鋪磚
題意簡述：有一個 \(2 \times n\) 的走道，現在用 \(1 \times 2\)，\(2 \times 2\) 的磚去鋪滿。問有多少種不同的鋪法？
數據範圍：多組數據，\(0 \leq n \leq 250\)。
先設 \(f_n\) 表示鋪成 \(2 \times n\) 的走道的方案數。\(2 \times n\) 的走道是怎麼鋪成的？可以由一個 \(1 \times 2\) 的磚豎著鋪在最右邊，問題就轉化為了鋪剩下的 \(2 \times (n – 1)\) 的走道，方案數即為 \(f_{n – 1}\)；也可以由兩個 \(1 \times 2\) 的磚橫著鋪在最右邊，問題就轉化為了鋪剩下的 \(2 \times (n – 2)\) 的走道，方案數即為 \(f_{n – 2}\)；還可以直接由一個 \(2 \times 2\) 的磚鋪在最右邊，問題就轉化為了鋪剩下的 \(2 \times (n – 2)\) 的走道，方案數也為 \(f_{n – 2}\)。綜上，我們可以得到遞推柿 \(f_i = f_{i – 1} + f_{i – 2} \times 2\)。邊界顯然為 \(f_1 = 1, f_2 = 3\)。
注意這裡是多測，所以可以提前處理出 \(f_3\) 至 \(f_{250}\)，一一回答即可。需要使用高精度。
「例題」統計奇數和偶數個 3
原題目鏈接：Link。
這裡有兩個維度：位數和奇偶。我們就可以把這兩個維度設出來：設 \(f_{n, 0}\) 表示 \(n\) 位正整數中有多少個數含偶數個數字 \(3\)，\(f_{n, 1}\) 表示 \(n\) 位正整數中有多少數含個奇數個數字 \(3\)。
\(n\) 位正整數中，含偶數個數字 \(3\) 的數是怎麼來的呢？有兩種情況：
- 前面 \(n – 1\) 位含奇數個數字 \(3\)，第 \(n\) 位是 \(3\)。個數為 \(f_{n – 1, 1}\)。
- 前面 \(n – 1\) 位含偶數個數字 \(3\)，第 \(n\) 位不是 \(3\)（是 \(0, 1, 2, 4, 5, 6, 7, 8, 9\)）。個數為 \(f_{n – 1, 0} \times 8\)。
所以可以得到 \(f_{n, 0} = f_{n – 1, 1} + f_{n – 1, 0} \times 8\)。同理有 \(f_{n, 1} = f_{n – 1, 0} + f_{n – 1, 1} \times 8\)。
「例題」螺旋矩陣
原題目鏈接：Link。
思考如何遞歸，發現矩陣外面那一圈兒都是可以直接算出來的（知道 \(n\)）。接著觀察除去外面那一圈兒後剩下的矩陣，發現只要減去 \(4n – 4\) 後就是一個新的矩陣。
拿這個圖舉個例子：
\(1 \sim 12\) 可以直接算出，而剩下的 \(13, 14, 15, 16\) 就相當於 \(12 + 1, 12 + 2, 12 + 3, 12 + 4\)。
程式碼如下：
#include <cstdio>
int n, i, j;
int f(int m, int x, int y) {
if (x == 1) return y;
if (x == m) return 3 * m - y - 1;
if (y == 1) return 4 * m - x - 2;
if (y == m) return m + x - 1; // 邊界情況，可以自己推導
return f(m - 2, x - 1, y - 1) + 4 * m - 4;
// 規模縮小，記得加上 4 * m - 4
}
int main() {
scanf("%d %d %d", &n, &i, &j);
printf("%d\n", f(n, i, j));
return 0;
}
「例題」無限的路
原題目鏈接：Link。
給出兩個點 \((x_1, y_1), (x_2, y_2)\)，要求連接的折線長度，為了方便計算，我們可以統一成到點 \((0, 0)\) 的折線長度，兩者相減就會抵消，剩下我們要求的答案。
現在，問題就轉化為給出點 \((x, y)\)，求它到點 \((0, 0)\) 的折線長度。
我們可以發現（結合圖食用更佳）：
- 當 \(x = 0\) 時，我們可以從 \((0, y)\) 走到 \((y – 1, 0)\)，再加上點 \((y – 1, 0)\) 到點 \((0, 0)\) 的折線長度。
- 當 \(y = 0\) 時，我們可以從 \((x, 0)\) 走到 \((0, x)\)，再加上點 \((0, x)\) 到點 \((0, 0)\) 的折線長度。
- 當 \(x \not= 0\) 且 \(y \not= 0\) 時，我們可以從 \((x, y)\) 走到 \((0, x + y)\)，再加上點 \((0, x + y)\) 到點 \((0, 0)\) 的折線長度。
然後用上我們小學二年級就學過的兩點間直線距離 \(\sqrt{(x_1 – x_2) ^ 2 + (y_1 – y_2) ^ 2}\) 就行了。邊界顯然是 \((0, 0)\)。
由於這裡是 double 類型，不好直接記憶化，所以我們可以開一個 bool 數組打標記。程式碼如下：
#include <cstdio>
#include <cmath>
double ans[205][205];
bool flag[205][205];
double f(int x1, int my1, int x2, int y2) {
return sqrt(pow(x1 - x2, 2) + pow(my1 - y2, 2));
} // 兩點間直線距離
int n, x1, x2, my1, y2; // y1 是關鍵字，隨便加個字母
double g(int x, int y) {
if (!x && !y) return 0; // (0, 0) 邊界
if (flag[x][y]) return ans[x][y]; // 已經搜過
flag[x][y] = true;
if (!x) return ans[x][y] = g(y - 1, 0) + f(x, y, y - 1, 0);
if (!y) return ans[x][y] = g(0, x) + f(x, y, 0, x);
return ans[x][y] = g(0, x + y) + f(x, y, 0, x + y); // 三種情況
}
int main() {
scanf("%d", &n);
while (n--) {
scanf("%d %d %d %d", &x1, &my1, &x2, &y2);
printf("%.3lf\n", fabs(g(x1, my1) - g(x2, y2))); // 記得加絕對值
}
return 0;
}
「例題」最大奇約數
原題目鏈接：Link。
每一個數都能表示成 \(x = 2 ^ k \times a\) 的形式（\(2 \nmid a\)），這道題的 \(f(x)\) 相當於求出 \(a\)。答案為 \(\sum _ {i = 1} ^ n f(i)\)。
如果老老實實地算 \(\sum _ {i = 1} ^ N f(i)\) 會超時，加上記憶化又會 MLE，這啟發我們令一個函數 \(g(n) = \sum _ {i = 1} ^ n f(i)\)。
然後我們推公式。
- 當 \(2 \nmid n\)，顯然 \(g(n) = n + g(n – 1)\)。
- 當 \(2 \mid n\)，發現 \(f(i)\) 可以根據奇偶性分成兩類，\(f(2k) = f(k)\)，而 \(f(2k + 1) = 2k + 1\)。從而也可以把 \(\sum _ {i = 1} ^ n f(i)\) 分成兩類，一類是 \(f(1) + f(3) + f(5) + \dots + f(n – 1) = 1 + 3 + 5 + \dots + (n – 1)\)，一類是 \(f(2) + f(4) + f(6) + \dots + f(n) = f(1) + f(2) + f(3) + \dots + f(\frac{n}{2})\)；前者可以等差數列求和暴算，而後者發現就等於 \(f(\frac{n}2)\)，直接遞歸即可。
#include <cstdio>
int n;
long long f(int x) {
if (x == 1) return 1; // 邊界條件
if (x & 1) return f(x - 1) + x;
return f(x >> 1) + (long long)x * x / 4;
// 因為 x * x 可能會溢出，所以先轉換成 long long 再乘
}
int main() {
scanf("%d", &n);
printf("%lld\n", f(n));
return 0;
}
「例題」Strange Towers of Hanoi
原題目鏈接：Link。
題目要求我們求 Hanoi 塔的移動步數。這個簡單，秒了！——真的這麼簡單嗎？啊，是 \(4\) 座塔！（一般的 Hanoi 塔是 \(3\) 座。）
不過，題目中有這樣一段話：
此演算法適用於 \(n \leq 12\)：塔 A 上的 \(k\)（\(k \geq 1\)）個盤子是固定的，其餘 \(n – k\) 個盤子使用四塔演算法從 A 移到 B。然後用三塔演算法把 A 上的 \(k\) 個盤子移到 D，最後使用四塔演算法將 B 上的 \(n – k\) 個盤子再次移動到 D。
可以設 \(n\) 個盤子時用三塔需要 \(g_n\) 步，我們有這樣的方案：把 A 最上面的 \(n – 1\) 個盤子移到 B，A 上的第 \(n\) 個盤子移到 C，然後把 B 上的 \(n – 1\) 個盤子移到 C。從而有 \(g_n = 2 \times g_{n – 1} + 1\)。
再設 \(n\) 個盤子時用四塔需要 \(f_n\) 步。因為題目已經告訴了我們公式，遍歷 \(k\) 取 \(\min\) 即可，不用白不用哇：
\]
「例題」棋子移動
原題目鏈接：Link。
首先，我們發現 \(n = 4\) 時僅有這一種固定移動方法：
4,5-->9,10
8,9-->4,5
2,3-->8,9
7,8-->2,3
1,2-->7,8
這顯然就是遞歸邊界。那當 \(n > 4\) 時呢（下面設 \(n = 5\)）？
〇〇〇〇〇●●●●●
容易想到，先把中間的移到最右邊。
〇〇〇〇[ ][ ]●●●●〇●
然後把最右邊的兩個黑棋子移到空位里去。
〇〇〇〇●●●●[ ][ ]〇●
發現左邊縮小規模成了 \(n – 1 = 4\) 的情況，繼續遞歸即可。
程式碼十分簡單：
#include <cstdio>
#include <iostream>
int n;
void print(int n) {
if (n == 4) {
puts("4,5-->9,10\n\n8,9-->4,5\n\n2,3-->8,9\n\n7,8-->2,3\n\n1,2-->7,8");
return;
}
std::cout << n << "," << n + 1 << "-->" << (n << 1 | 1) << "," << (n * 2 + 2) << std::endl << std::endl;
std::cout << 2 * n - 1 << "," << (n << 1) << "-->" << n << "," << n + 1 << std::endl << std::endl;
print(n - 1);
}
int main() {
std::cin >> n;
print(n);
return 0;
}
By the way，建議大家輸出複雜格式時還是用 printf，cout 要打死了。。。
「例題」分形圖1
原題目鏈接：Link。
題目要求我們輸出一個奇怪的 X 形分形圖。觀察發現，當規模為 \(n\) 時，其實就是由 \(5\) 個規模為 \(n – 1\) 的 X 形組合而成。一般對於這種分形圖，我們都會遞歸規模和坐標。
程式碼非常簡單：
#include <bits/stdc++.h>
using namespace std;
int n;
char ch[735][735];
void print(int n, int x, int y) { // n 是規模，(x, y) 是圖形左上角坐標
if (n == 1) {
ch[x][y] = 'X';
return;
} // 邊界情況
int t = pow(3, n - 2); // n - 1 規模圖形的長（寬）
print(n - 1, x, y); // 列印左上
print(n - 1, x + (t << 1), y); // 列印左下
print(n - 1, x + t, y + t); // 列印中間的
print(n - 1, x, y + (t << 1)); // 列印右上
print(n - 1, x + (t << 1), y + (t << 1)); // 列印右下
}
int main() {
while (cin >> n) {
memset(ch, 0, sizeof(ch)); // 記得清零
print(n, 1, 1);
int len = pow(3, n - 1);
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= len; j++)
if (ch[i][j]) putchar(ch[i][j]);
else putchar(' ');
// 沒填充到的地方默認是 0，直接輸出的話，肉眼看不出與空格的差別，但是會 WA
// 所以這裡特判一下
putchar('\n');
}
putchar('-');
putchar('\n');
}
return 0;
}
附上一個奇怪分形圖的程式碼：
#include <iostream>
using namespace std;
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
putchar((i & j) ? '#' : ' ');
putchar('\n');
}
return 0;
}
可以試試用遞歸實現。
