AcWing 118. 分形(递归)
原题链接
简单
作者:
Limited
,
2021-02-06 00:55:12
,
所有人可见
,
阅读 545
思路
- n级盒子边长为$3^{(n-1)}$
- 观察坐标关系,中心点的’X’正好位于边长中点$\frac{3^{(n-1)}}2$,n级盒子中心与四个对角n-1级盒子中心差了$3^{(n-2)}$
- 递归子级盒子的中心点坐标和等级,直到1级盒子在中心点画’X’结束递归分支
C++代码
#include <iostream>
using namespace std;
int pow3[10], dx[] = {-1, -1, 0, 1, 1}, dy[] = {-1, 1, 0, -1, 1};
char f[2500][2500];
void draw(int x, int y, int n) {
// 等级为1时 画'X'并结束递归
if (n == 1) {
f[x][y] = 'X';
return;
}
// 通过盒子中心确定位置 递归左上、右上、中心、左下、右下的子级盒子
// 参考样例 观察到n级盒子的中心'X'与n-1级正好差了【3^(n-2)】对应pow3[n - 2]
for (int i = 0; i < 5; i++)
draw(x + dx[i] * pow3[n - 2], y + dy[i] * pow3[n - 2], n - 1);
}
int main() {
// 3的n次方打表
pow3[0] = 1;
for (int i = 1; i < 10; i++) pow3[i] = pow3[i - 1] * 3;
int n;
while (cin >> n, n != -1) {
// 对于n级盒子分形 图像长宽均为3^(n-1) 对应pow3[n-1]
// 赋初始值 ' '
for (int i = 0; i < pow3[n - 1]; i++)
for (int j = 0; j < pow3[n - 1]; j++)
f[i][j] = ' ';
// 盒子分形中心点正好在长宽的中点 递归画分形
draw(pow3[n - 1] >> 1, pow3[n - 1] >> 1, n);
// 输出
for (int i = 0; i < pow3[n - 1]; i++) {
for (int j = 0; j < pow3[n - 1]; j++)
cout << f[i][j];
cout << endl;
}
cout << '-' << endl;
}
return 0;
}