Fractal
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 8341 | Accepted: 3965 |
Description
A fractal is an object or quantity that displays self-similarity, in a somewhat technical sense, on all scales. The object need not exhibit exactly the same structure at all scales, but the same "type" of structures must appear on all scales.
A box fractal is defined as below :
A box fractal is defined as below :
- A box fractal of degree 1 is simply
X - A box fractal of degree 2 is
X X
X
X X - If using B(n - 1) to represent the box fractal of degree n - 1, then a box fractal of degree n is defined recursively as following
B(n - 1) B(n - 1)
B(n - 1)
B(n - 1) B(n - 1)
Your task is to draw a box fractal of degree n.
Input
The input consists of several test cases. Each line of the input contains a positive integer n which is no greater than 7. The last line of input is a negative integer −1 indicating the end of input.
Output
For each test case, output the box fractal using the 'X' notation. Please notice that 'X' is an uppercase letter. Print a line with only a single dash after each test case.
Sample Input
1
2
3
4
-1
Sample OutputX
-
X X
X
X X
-
X X X X
X X
X X X X
X X
X
X X
X X X X
X X
X X X X
-
X X X X X X X X
X X X X
X X X X X X X X
X X X X
X X
X X X X
X X X X X X X X
X X X X
X X X X X X X X
X X X X
X X
X X X X
X X
X
X X
X X X X
X X
X X X X
X X X X X X X X
X X X X
X X X X X X X X
X X X X
X X
X X X X
X X X X X X X X
X X X X
X X X X X X X X
-
递归：
思路很巧妙，把每个左上角的点作为起点；开始递归；
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
#define mem(x,y) memset(x,y,sizeof(x))
#define SI(x) scanf("%d",&x);
char a[2500][2500];
void dfs(int x,int y,int cur){
if(cur==1){
a[x][y]='X';
return;
}
int n,m;
dfs(x,y,cur-1);
//左上
m=x;n=y+pow(3,cur-2)*2;
dfs(m,n,cur-1);
//右上
m=x+pow(3,cur-2)*2;n=y;
dfs(m,n,cur-1);
//左下
m=x+pow(3,cur-2)*2;n=y+pow(3,cur-2)*2;
dfs(m,n,cur-1);
//右下
m=x+pow(3,cur-2);n=y+pow(3,cur-2);
dfs(m,n,cur-1);
//中
}
int main(){
int N;
while(scanf("%d",&N),N!=-1){
int len=pow(3,N-1);
for(int i=0;i<len;i++){
for(int j=0;j<len;j++)
a[i][j]=' ';
a[i][len]='\0';
}
dfs(0,0,N);
for(int i=0;i<len;i++){
printf("%s\n",a[i]);
}
puts("-");
}
return 0;
}