分形

分形

一个图形按照如下规律变换

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 X

询问第n个图形，(nleq 7)。

解

比谁更蠢的一道题目

求证：谁更蠢

法一：递推

注：最蠢的作者的办法

设(f_i)为第i个图形，那么(f_i)就是由5个(f_{i-1})分别放在左上右上中间左下有下而来的，我们只要暴力复制图形即可。

#include <iostream>
#include <cstdio>
#define il inline
#define ri register
using namespace std;
int base[8];
bool s[8][735][735];
int main(){
	s[1][1][1]=1,base[0]=1;
	for(int i(1);i<8;++i)base[i]=base[i-1]*3;
	for(int i(2),j,k;i<=7;++i){
		for(j=1;j<=base[i-2];++j)
			for(k=1;k<=base[i-2];++k)
				s[i][j+base[i-2]][k+base[i-2]]=s[i][j+base[i-2]*2][k]=
					s[i][j+base[i-2]*2][k+base[i-2]*2]=
					s[i][j][k+base[i-2]*2]=s[i][j][k]=s[i-1][j][k];
	}int n;
	while(scanf("%d",&n),n>=0){
		for(int i(1),j;i<=base[n-1];putchar('
'),++i)
			for(j=1;j<=base[n-1];++j)
				if(s[n][i][j])putchar('X');
				else putchar(' ');puts("-");
	}
	return 0;
}

法二：

注：聪明的你的骚操作

无限分形图显然需要用分治算法+递归实现是最简单，但是注意到拼接子问题的时候要暴力复制，这显然不会有人愿意去打的（除了最蠢的作者），但是如果我们保存图形的左上角的坐标来分治的话，就无需中途暴力复制了。

#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
using namespace std;
int base[8];
char s[735][735];
void divide(int,int,int);
int main(){
	base[0]=1;int n;
	for(int i(1);i<8;++i)
		base[i]=base[i-1]*3;
	while(scanf("%d",&n),n>=0){
		memset(s,0,sizeof(s));
		divide(1,1,n);
		for(int i(1),j;i<=base[n-1];putchar('
'),++i)
			for(j=1;j<=base[n-1];++j)
				if(s[i][j])putchar(s[i][j]);
				else putchar(' ');puts("-");
	}
	return 0;
}
void divide(int y,int x,int n){
	if(n==1)return (void)(s[y][x]='X');
	divide(y,x,n-1);
	divide(y,x+base[n-2]*2,n-1);
	divide(y+base[n-2]*2,x,n-1);
	divide(y+base[n-2],x+base[n-2],n-1);
	divide(y+base[n-2]*2,x+base[n-2]*2,n-1);
}

总上所素，作者最蠢