晴天的魔法乐园——谢尔宾斯基地毯（递归打印图形）「建议收藏」

全栈程序员站长

发布于 2022-09-14 11:14:42

3850

发布于 2022-09-14 11:14:42

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

题目链接：https://judger.net/problem/1061

Problem Description

谢尔宾斯基地毯是一种分形图案，它的定义如下：令F(n)表示嵌套n层的谢尔宾斯基地毯，那么（下面的“空”均表示空格，仅为示意，实际输出时应仍为空格）当n=1时，F(1)为：空当n=2时，F(2)为：空空空空X空空空空一般地，如果F(n-1)表示嵌套n-1层的谢尔宾斯基地毯，则F(n)的递归定义如下： F(n-1)F(n-1)F(n-1)F(n-1)X(n-1)F(n-1)F(n-1)F(n-1)F(n-1) 其中X(n)表示边长为n的正方形，其内部被字符X完全填充。现在输入一个正整数n，请画出嵌套n层的谢尔宾斯基地毯F(n)。

Input

每个输入文件一组数据。第一行一个正整数N（N<=7），表示谢尔宾斯基地毯的嵌套层数。

Output

输出嵌套n层的谢尔宾斯基地毯。为了让输出看起来更像地毯，请用加号+将结果完整包裹起来。

Sample Input 1

Sample Output 1

+++
+ +
+++

Sample Input 2

Sample Output 2

+++++
+   +
+ X +
+   +
+++++

Sample Input 3

Sample Output 3

+++++++++++
+         +
+ X  X  X +
+         +
+   XXX   +
+ X XXX X +
+   XXX   +
+         +
+ X  X  X +
+         +
+++++++++++

Sample Input 4

Sample Output 4

+++++++++++++++++++++++++++++
+                           +
+ X  X  X  X  X  X  X  X  X +
+                           +
+   XXX      XXX      XXX   +
+ X XXX X  X XXX X  X XXX X +
+   XXX      XXX      XXX   +
+                           +
+ X  X  X  X  X  X  X  X  X +
+                           +
+         XXXXXXXXX         +
+ X  X  X XXXXXXXXX X  X  X +
+         XXXXXXXXX         +
+   XXX   XXXXXXXXX   XXX   +
+ X XXX X XXXXXXXXX X XXX X +
+   XXX   XXXXXXXXX   XXX   +
+         XXXXXXXXX         +
+ X  X  X XXXXXXXXX X  X  X +
+         XXXXXXXXX         +
+                           +
+ X  X  X  X  X  X  X  X  X +
+                           +
+   XXX      XXX      XXX   +
+ X XXX X  X XXX X  X XXX X +
+   XXX      XXX      XXX   +
+                           +
+ X  X  X  X  X  X  X  X  X +
+                           +
+++++++++++++++++++++++++++++

1、分析

递归打印，打印方法同上一篇博客：晴天的魔法乐园——盒分形，唯一的区别是每次递归的时候有两个打印，即四周的和中央。

2、代码

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

void fill(int n, int x, int y){
	if(n == 1){
		return;
	}else if(n == 2){
		matrix[x][y] = 'X';
		return;
	}
	//画四周图形 
	for(int i = 0; i < 9; i++){
		int newX = x + X[i] * pow(3, n - 2);
		int newY = y + Y[i] * pow(3, n - 2);
		fill(n - 1, newX, newY);
	}
	//画中央图形
	for(int i = 0; i < 9; i++){
		int newX = x + X[i] * pow(3, n - 3);
		int newY = y + Y[i] * pow(3, n - 3);
		fill(n - 1, newX, newY);
	} 
} 

int main(){
	int n;
	scanf("%d", &n);
	fill(n, 400, 400);
	int scale = pow(3, n - 1);
	for(int i = 400 - scale / 2 - 1; i <= 400 + scale/2 + 1; i++){
		for(int j = 400 - scale / 2 - 1; j <= 400 + scale / 2 + 1; j++){
			//打印四周的'+' 
			if(j == 400 - scale / 2 - 1 || j == 400 + scale / 2 + 1 || i == 400 - scale / 2 - 1 || i == 400 + scale / 2 + 1){
				printf("+");
			}else if(matrix[i][j] == 'X'){
				printf("X");
			}else{
				printf(" ");
			}
		}
		printf("\n");
	}
	return 0;
}