晴天的魔法乐园——盒分形(递归打印图形)

编辑:谯胜平      分类:程序与算法      标签:晴天的魔法乐园      发布时间:2019-09-02      浏览次数:766

题目链接:https://judger.net/problem/1060

Problem Description

盒分形是一种分形图案,它的定义如下:
令F(n)表示嵌套n层的盒分形,那么
当n=1时,F(1)为:

X

当n=2时,F(2)为:

X X
 X
X X

一般地,如果F(n-1)表示嵌套n-1层的盒分形,则F(n)的递归定义如下:

F(n-1)      F(n-1)
      F(n-1)
F(n-1)      F(n-1)

现在输入一个正整数n,请画出嵌套n层的盒分形F(n)。

Input

每个输入文件一组数据。
第一行一个正整数N(N<=7),表示盒分形的嵌套层数。

Output

输出嵌套n层的盒分形。注意每行的长度应当是相同的,行末不要漏输出了空格。

Sample Input 1

1

Sample Output 1

X

Sample Input 2

2

Sample Output 2

X X
 X 
X X

Sample Input 3

3

Sample Output 3

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

Sample Input 4

4

Sample Output 4

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

1、分析

递归打印图形,刚开始考虑使用循环来实现,但是发现坐标操作太复杂,于是就换用递归了。这道题目还是有一点难度的,但是搞懂了递归的过程就简单了。根据观察可以发现,正整数n的图形横纵坐标跨度为3 ^ (n - 1),题目的最大n为7,3 ^ 6 = 729, 因此可以设置800*800的字符数组,以(400, 400)为中心。则生成的图形的横纵坐标范围为x, y∈[400 - 3 ^ (n - 1), 400 + 3 ^ (n - 1)]。

下面具体分析一下递归是怎么实现的。

①递归边界,n = 1时,给字符数组指定下标(x, y)赋值'X';

②当n ≠ 1时,可以发现,四周图形是中间图形的一个拷贝,且此时的四个拷贝和中央的图案是n - 1时的图形。

因此n时的状态就可以分四个方向+中间共五个部分转移到n - 1时的状态了。当n = 4时如下图所示:

ubang_image_20190902326543.png

相应的,当n = 2时可以从n = 3时的中心点向四个方向进行扩展,直到n = 2.

2、代码

#include<stdio.h>
#include<math.h>
const int maxn = 800;
char matrix[maxn][maxn];
//坐标 
int X[5] = {0, -1, 1, -1, 1};
int Y[5] = {0, -1, -1, 1, 1};

void fill(int n, int x, int y){
	if(n == 1){
		matrix[x][y] = 'X';
		return;
	}
	//分别在四个方向进行打印
	for(int i = 0; i < 5; i++){
		int newX = x + X[i] * pow(3, n - 2);
		int newY = y + Y[i] * pow(3, n - 2);
		fill(n - 1, newX, newY); 
	} 
} 

int main(){
	int n;
	scanf("%d", &n);
	fill(n, 400, 400);
	//以(400,400)为中心点,scale为横纵坐标的跨度 
	int scale = pow(3, n - 1);
	for(int i = 400 - scale / 2; i <= 400 + scale / 2; i++){
		for(int j = 400 - scale / 2; j <= 400 + scale / 2; j++){
			//没有赋值的地方直接打印空格 
			if(matrix[i][j] == 'X'){
				printf("X");
			}else{
				printf(" ");
			}
		}
		printf("\n");
	}
	return 0;
}


看不清?换一个