题目链接
链接：AcWing 118. 分形
思路
不难发现，\(n\) 级图形的长度为 \(3^{n-1}\)，且 \(n\le 7 \implies 3^{n-1} < 10^3\)，于是可以开辟大小为 \(10^3\) 的二维布尔数组 \(a\) 与图形对应。
- 若 \(a[i][j]=0\)：表示该位置为空；
- 若 \(a[i][j]=1\)：表示该位置为
'X'。
设 \(n\) 级图形的长度为 \(m\)，则 \(n-1\) 级的图像长度
\[size=\frac{m}{3}
\]
从左上角 \((x,y)=(0,0)\) 开始递归。 由于 \(n\) 级图形由 \(5\) 个 \(n-1\) 级图形构成，于是需要 \(5\) 个递归分支，分别对应 \(n-1\) 级问题的左上角坐标。
- 左上角：递归到 \((size, x,y)\)；
- 右上角：递归到 \((size, x, y + 2 \cdot size)\)；
- 中间：递归到 \((size, x + size, y + size)\)；
- 左下角：递归到 \((size, x + 2 \cdot size, y)\)；
- 右下角：递归到 \((size, x + 2 \cdot size, y + 2 \cdot size)\)。
当 \(size=1\) 时，递归到简单情况，设置 \(a[x][y]=1\) 即可。
代码
#include <bits/stdc++.h>
using namespace std;constexpr int N = 1010;vector<vector<bool>> g(N, vector<bool>(N));void dfs(int m, int x, int y) {if (m == 1) {g[x][y] = 1;return;}int size = m / 3;dfs(size, x, y);dfs(size, x, y + 2 * size);dfs(size, x + size, y + size);dfs(size, x + 2 * size, y);dfs(size, x + 2 * size, y + 2 * size);
}int main() {int n;while (scanf("%d", &n) == 1 && n != -1) {for (int i = 0; i < N; i++)fill(g[i].begin(), g[i].end(), 0);int m = 1;for (int i = 1; i < n; i++)m *= 3;dfs(m, 0, 0);for (int i = 0; i < m; i++) {for (int j = 0; j < m; j++) {if (g[i][j]) putchar('X');else putchar(' ');}puts("");}puts("-");}return 0;
}
递归时间复杂度分析
长度 \(n\) 的问题于规模为 \(n-1\) 的关系满足
\[T(m) = 5T(\frac{m}{3}) + O(1)
\]
忽略 \(O(1)\)，并展开 \(k\) 次，直到 \(m=1\)，于是
\[T(m) = 5T(\frac{m}{3}) = 5^2(\frac{m}{3 ^ 2}) = ... = 5^k(\frac{m}{3 ^ k}) \implies m = 3^k \implies k = \log_3{m}
\]
于是
\[T(m) = 5^{\log_3{m}}
\]
又 \(m = 3^{n-1}\)，于是
\[T(n)= O(5^{n-1})
\]
优化
注意观察图形，事实上，我们只需一次递归求出左上角图形的状态，然后根据分型规律，复制到其他 \(4\) 个部分即可。
#include <bits/stdc++.h>
using namespace std;constexpr int N = 1010;vector<vector<bool>> g(N, vector<bool>(N));void dfs(int m) {if (m == 1) {g[0][0] = 1;return;}dfs(m / 3);int dx[] = {0, 1, 2, 2};int dy[] = {2, 1, 0, 2};int size = m / 3;for (int k = 0; k < 4; k++) {for (int i = 0; i < size; i++) {for (int j = 0; j < size; j++) {g[i + dx[k] * size][j + dy[k] * size] = g[i][j];}}}
}int main() {int n;while (scanf("%d", &n) == 1 && n != -1) {for (int i = 0; i < N; i++)fill(g[i].begin(), g[i].end(), 0);int m = 1;for (int i = 1; i < n; i++)m *= 3;dfs(m);for (int i = 0; i < m; i++) {for (int j = 0; j < m; j++) {if (g[i][j]) putchar('X');else putchar(' ');}puts("");}puts("-");}return 0;
}