Cerința

Se dă un număr natural n. Să se genereze o matrice pătratică de ordinul 3n, cu elemente din mulțimea {0, 1}, după modelul covorului lui Sierpinski.

Date de intrare

Fișierul de intrare sierpinski.in conține pe prima linie numărul n.

Date de ieșire

Fișierul de ieșire sierpinski.out va conține pe primele 3n linii câte 3n cifre binare, reprezentând elementele matricei.

Restricții și precizări

• 1 ≤ n ≤ 6
• Atenție la limita de memorie!

Exemplu

sierpinski.in

2

sierpinski.out

0 0 0 0 0 0 0 0 0 
0 1 0 0 1 0 0 1 0 
0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 0 0 0 
0 1 0 1 1 1 0 1 0 
0 0 0 1 1 1 0 0 0 
0 0 0 0 0 0 0 0 0 
0 1 0 0 1 0 0 1 0 
0 0 0 0 0 0 0 0 0 

Explicație

#include <bits/stdc++.h>

using namespace std;

ifstream fin("sierpinski.in");
ofstream fout("sierpinski.out");

int n;
char a[729][92]; 

bool get(int x, int y)
{
    char mask = (1 << (8 - y % 8 - 1));
    return a[x][y / 8] & mask;
}

void set(int x, int y, bool val)
{
    if(get(x, y) != val)
    {
        char mask = (1 << (8 - y % 8 - 1));
        a[x][y / 8] ^= mask;
    }
}

void sierpinski(int x, int y, int l)
{
    
    for(int i = 0; i < l / 3; i++)
        for(int j = 0; j < l / 3; j++)
            set(x + l / 3 + i, y + l / 3 + j, 1);
    if(l > 1)
    {
        sierpinski(x, y, l / 3);
        sierpinski(x, y + l / 3, l / 3);
        sierpinski(x, y + 2 * l / 3, l / 3);
        sierpinski(x + l / 3, y, l / 3);
        sierpinski(x + l / 3, y + 2 * l / 3, l / 3);
        sierpinski(x + 2 * l / 3, y, l / 3);
        sierpinski(x + 2 * l / 3, y + l / 3, l / 3);
        sierpinski(x + 2 * l / 3, y + 2 * l / 3, l / 3);
    }
}

void afisare(int l)
{
    for(int i = 0; i < l; i++)
    {
        for(int j = 0; j < l; j++)
            fout<<get(i, j)<<' ';
        fout<<'\n';
    }
}

int main ()
{
    fin>>n;
    sierpinski(0, 0, pow(3, n));
    afisare(pow(3, n));
}