分形
分形，具有以非整数维形式充填空间的形态特征。
通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状”，即具有自相似的性质。
现在，定义“盒子分形”如下：
一级盒子分形：
X
二级盒子分形：1
2
3X X
X
X X
如果用B(n - 1)代表第n-1级盒子分形，那么第n级盒子分形即为：1
2
3
4
5B(n - 1) B(n - 1)
B(n - 1)
B(n - 1) B(n - 1)
你的任务是绘制一个n级的盒子分形。
输入格式
输入包含几个测试用例。
输入的每一行包含一个不大于7的正整数n，代表要输出的盒子分形的等级。
输入的最后一行为-1，代表输入结束。
输出格式
对于每个测试用例，使用“X”符号输出对应等级的盒子分形。
请注意’X’是一个大写字母。
每个测试用例后输出一个独立一行的短划线。
输入样例：
1 | 1 |
输出样例
1 | X |
递归 + 递推优化(减少递归的分支数，减小时间复杂度)
对于n级来说，只用画 5 个n - 1级，递归终止条件为 n == 1 true时，然后进行回溯，画剩下的4个(由第n级的 n - 1级复制过来)然后往上继续回溯1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using namespace std;
const int N = 1005;
bool a[N][N]; //由于只有画与不画两种状态(要画的只有一种图形)，
int qsm(int a, int b) //快速幂，用来计算len的长度
{
int res = 1;
while(b)
{
if(b & 1) res *= a;
a = a * a;
b >>= 1;
}
return res;
}
void dfs(int n) //n级分形的规划
{
if(n == 1) //1级直接画
{
a[0][0] = true; //先画左上角
return ;
}
dfs(n - 1); //进行dfs，靠回溯来完善整个图形
int len = qsm(3, n - 2); //长度为n级的n - 1 级(n级由 5 个 n - 1级组成) ，那么表示就会表示为 3 ^ (n - 2)
int px[4] = {0, 1, 2, 2}, py[4] = {2, 1, 0, 2}; //n级里的 其它4个n - 1级的开始坐标(左上角)
for(int i = 0; i < 4; i ++ ) //4种情况
for(int j = 0; j < len; j ++ ) //i 表示4个 n - 1级的图形，j, k为横纵坐标(为了进行复制)
for(int k = 0; k < len; k ++ ) //4种情况，以len为基础
a[j + px[i] * len][k + py[i] * len] |= a[j][k]; //进行"等位"(加上中心偏移量)复制
}
int main()
{
dfs(7); //预先算出答案，空间换时间
int n;
while(cin >> n && n != -1)
{
int len = qsm(3, n - 1); //每级的长度为3 ^ n - 1
for(int i = 0; i < len; i ++ )
{
for(int j = 0; j < len; j ++ )
if(a[i][j]) cout << 'X'; //1状态输出'X', 否则为' '
else cout << ' ';
puts(""); //记得换行
}
cout << '-' << endl;
}
return 0;
}