wtorek, 23 września 2014

19248. Fraktal Cantora [FR_01_07]

Zadanie:
https://spoj.com/FRAKTAL/problems/FR_01_07
https://pl.spoj.com/problems/FR_01_07

Skrócony opis problemu:
Dla danego $n$ narysuj fraktal Cantora $n$-tego rzędu, zbudowanego ze spacji i znaków '_' (podłóg).

Rozwiązanie nr 1:
Po pierwsze warto zauważyć, ile znaków w linii będziemy musieli wypisać. Powiedzmy, że liczbę znaków w linii będziemy oznaczać przez $x$. Pierwsza linia zawiera zatem wszystkie $x$ znaków '_', druga $\frac{2}{3} \cdot x$, trzecia $\frac{2}{3}$ poprzedniej (a więc $\frac{4}{9} \cdot x$), itd. Ilość znaków '_' w linii wynosi więc: $a_i = \left(\frac{2}{3}\right)^{i} \cdot x$, dla $i = 0, 1, \ldots, n-1$. Np. dla $n = 3$: $x = 9$, $a_0 = \left(\frac{2}{3}\right)^0 \cdot 9 = 9$, $a_1 = \left(\frac{2}{3}\right)^1 \cdot 9 = 6$, $a_2 = \left(\frac{2}{3}\right)^2 \cdot 9 = 4$. Jak widzimy, $a_2 = 4$ nie jest podzielne przez 3, więc nie wypiszemy już następnej linii. A zatem, $n$ będzie wynosiło tyle, ile razy uda nam się pomnożyć bez reszty $x$ przez $\frac{2}{3}$. Oczywiście mnożenie przez 2 jest dla nas bez różnicy, więc $n$ równe jest wykładnikowi maksymalnej potęgi 3, przez którą podzielimy $x$, powiększone o 1 (bo wypisujemy również pierwszą linię z samymi znakami '_', bez spacji). Tak więc $n = 1 + log_3 x$. Jako że znamy $n$, możemy obliczyć $x$. Na początku przenosimy 1 na drugą stronę równania: $n-1 = log_3 x$, a następnie obie podstawy traktujemy jako wykładnik podstawy 3: $3^{n-1} = 3^{log_3 x}$. Przypominam, że $a^{log_a b} = b$. Otrzymujemy więc: $x = 3^{n-1}$. Można to było oczywiście zauważyć bez zbędnych obliczeń, ale nie zaszkodziło tego pokazać.

Wiemy już, ile linii oraz ile znaków w linii wypisać. Pozostaje tylko zdecydować dla każdego znaku czy powinna nim być spacja czy '_'. Jak to zrobić? Ano sprawdźmy czy dla danego wiersza można wydedukować jak będzie wyglądał następny. Pierwsza rzecz, która może rzucić nam się w oczy są spacje. Jeśli w danej linii w którymś miejscu była spacja, to w następnej linii w tym miejscu również będzie spacja. Wynika to z tego, że wraz z kolejnymi liniami ilość spacji rośnie, a ilość '_' maleje. A co zrobić dla podłóg? Ano dla każdego ciągu podłóg musimy wypisać ich $\frac{1}{3}$, następnie tyle samo spacji i znów tyle samo podłóg. Mamy już zatem algorytm! Zaczynamy od $3^{n-1}$ znaków '_', a następnie dla każdej z pozostałych $n-1$ linii sprawdzamy każdy znak z poprzedniej linii. Jeśli dany znak nie jest spacją, to inkrementujemy zmienną $nonempty$, która zawiera ilość podłóg z poprzedniego ciągu do danego momentu. Jeśli znak jest spacją, to go nie zmieniamy, ale za to sprawdzamy czy zmienna $nonempty$ jest niezerowa. Jeśli tak to znaczy, że trafiliśmy na pierwszą spację po ciągu '_'. Przechodzimy więc poprzednie $nonempty$ znaków i zamieniamy $\frac{1}{3}$ ze środka na spacje. Na koniec, dla spacji zerujemy $nonempty$. Po przejściu całego ciągu wykonujemy jeszcze raz operacje, które robiliśmy dla pierwszej spacji po ciągu '_'. Dlaczego? Bo ostatnie znaki są zawsze podłogami, a po nich nie ma spacji - gdybyśmy tego nie zrobili poza pętlą, to ostatni ciąg '_' nie miałby w środku spacji.

Złożoność: $O\left(n \cdot 3^n\right)$, bo dla każdej z $n-1$ linii (pierwszą linię wypełniamy ręcznie) przechodzimy $3^{n-1}$ znaków. Złożoność pamięciowa: $O(3^n)$, bo potrzebujemy tylko jednego wiersza naszego fraktala, a ma on długość $x = 3^{n-1}$.

Algorytm:
int main()
{
        int n, i, j, k, nonempty, len;
        char cantor[178000];

        get(n);
        len = pow(3, n-1); // obliczamy długość linii
        for(cantor[len] = i = 0; i < len; ++i) // tworzymy pierwszą linię
                cantor[i] = '_';
        print(cantor); // wypisujemy pierwszą linię osobno
        for(i = 1; i < n; ++i) // dla każdej z n-1 linii
        {
                for(nonempty = j = 0; j < len; ++j)
                        if(cantor[j] == ' ')
                        {
                                // jeśli nonempty = 0 (czyli mamy którąś spację z kolei), to nie wykonamy żadnego obiegu, więc nic się nie stanie złego
                                // można by zrobić przed pętlą if(nonempty > 0), ale po co, skoro mamy niejawnego ifa w forze?
                                for(k = 0; k < nonempty/3; ++k) // wypełniamy 1/3 ciągu '_' spacjami (tą środkową)
                                        cantor[j-2*nonempty/3+k] = ' '; // od danego miejsca - j odejmujemy 2/3 długości ostatniego ciągu znaków '_'
                                nonempty = 0; // od teraz mamy 0 znaków '_'
                        }
                        else
                                 ++nonempty; // mamy kolejny znak '_'
                for(k = 0; k < nonempty/3; ++k) // robimy to samo co wyżej dla ostatniego ciągu '_'
                        cantor[len-2*nonempty/3+k] = ' ';
                print(cantor);
        }
}

Rozwiązanie nr 2:
Jak część z Was wie, fraktale naturalnie otrzymuje się rekurencyjnie. Możemy zatem również i fraktal Cantora otrzymać ową metodą. A zatem, jak napisać naszą funkcję... Powinna ona dzielić daną linię na mniejsze części i każdą kolejną tak samo. Na jakie części możemy podzielić daną linię? Ano na przykład na pusty środek i 2 niepuste boki. Jak bowiem widzimy, z każdego spójnego ciągu podłóg wychodzi poniżej pusty środek.

Wiemy już na jakie podzbiory podzielimy nasz fraktal. Kolejnym pytaniem jest: jakich zmiennych potrzebujemy dla każdego wywołania? Na pewno potrzebujemy wiedzieć którą linię przetwarzamy oraz od którego i do którego znaku rozpatrujemy podciąg. No i to nam tyle wystarczy. Te 3 zmienne jednoznacznie określą nam ciąg, na którym będziemy operowali.

Utwórzmy sobie więc macierz (tablicę tablic) znaków o rozmiarze $n$ na $3^{n-1}$. Pierwszy (o indeksie 0) rząd wypełniamy sobie podłogami. Następnie wywołujemy naszą funkcję (nazwijmy są $fractalize$) dla linii zerowej, początku w 0 i końcu w $3^{n-1}-1$ (jako że indeksujemy tablicę od 0). Co potem? Ano pod środkową częścią naszego pierwszego wiersza wszystkie znaki będą spacjami, jak widać na poniższym przykładzie:
_________________________________________________________________________________
___________________________                           ___________________________
___   ___         ___   ___                           ___   ___         ___   ___
_ _   _ _         _ _   _ _                           _ _   _ _         _ _   _ _

Tak więc dla linii $line$ oraz znaków od $start$ do $end$ włącznie, wykonujemy następujące czynności. Najpierw wypełniamy spacjami wszystkie linie od $line+1$ do $n-1$ w przedziale od $start+\frac{x}{3}$ do $start+\frac{2 \cdot x}{3}-1$, gdzie $x$ to $\frac{1}{3}$ długości ciągu, który rozpatrujemy. A jaką długość ma nasz ciąg? Ano $end-start+1$. Np. ciąg od znaku o indeksie 7 do znaku o indeksie 12 ma długość 12-7+1=6. Pozostałe znaki w linii $line+1$ wypełniamy '_', a następnie uruchamiamy 2 wywołania rekurencyjne: $fractalize\left(line+1, start, start+\frac{x}{3}-1\right)$ oraz $fractalize\left(line+1, start+\frac{2 \cdot x}{3}, end\right)$. Skąd takie wartości zmiennych? Pierwszy parametr w obu wywołaniach to $line+1$, bo w będziemy zajmować się następną linią. Dodatkowo, pierwsze wywołanie rozpocznie się od tego samego znaku, więc $start$ się nie zmieni. Zmieni się jednak indeks ostatniego znaku, gdyż przecież dzielimy ciąg na 3 części. Dodajemy więc do $start$ wartość $\frac{x}{3}-1$. W drugim wywołaniu nie zmieni się z kolei ostatni parametr, bo drugi ciąg podłóg z następnej linii trwa do końca poprzedniego podciągu. A pierwszy parametr drugiego wywołania wynosi $start+\frac{2 \cdot x}{3}$, bo ciąg '_' zaczyna się od dwóch trzecich poprzedniego ciągu (i trwa do końca, jak już ustaliliśmy).

To wszystko! Powtórzę w skrócie kroki, które wykonujemy: dzielimy daną linię na 3 części. Środkową część musimy wypełnić spacjami, ale nie tylko 1 wiersz, ale wszystkie wiersze do końca (bo patrząc w dół na fraktala pod spacją zawsze są same spacje). Pozostałe 2 części znajdujące się po bokach wypełniamy '_', ale tylko w linii poniżej (bez następnych) i wywołujemy dla nich kolejne funkcje $fractalize$, ale z innymi parametrami. Wywołanie kończymy gdy $end-start < 2$, a więc gdy nie będziemy mogli już podzielić ciągu na 3 części.

Złożoność: $O\left(n \cdot 3^n\right)$ z takiej samej przyczyny co rozwiązanie nr 1. Złożoność pamięciowa: $O\left(n \cdot 3^n\right)$, bo musimy trzymać wszystkie $n$ linii cały czas. Dlaczego? Ano dlatego, że rekurencja idzie wgłąb (jak algorytm DFS), więc drugą linię otrzymamy dopiero pod koniec. Musimy zatem pamiętać wszystkie znaki, skoro nie możemy wypisywać linii po kolei. Jak widać, to rozwiązanie jest trochę gorsze od poprzedniego, gdyż ma gorszą złożoność pamięciową.

Algorytm:
void fractalize(int line, int start, int end)
{
        if(end-start < 2) // jeśli mamy za krótki ciąg, by go podzielić na 3 części, to kończymy wywołanie
                return;
        int i, j, x = end-start+1; // x to długość ciągu, który rozpatrujemy w danej chwili
        for(i = line+1; i < n; ++i) // każdą z następnych linii wypełniamy spacjami w środku tego ciągu
                for(j = 0; j < x/3; ++j)
                        cantor[i][start+x/3+j] = ' ';
        for(i = 0; i < x/3; ++i) // boki wypełniamy podłogami
                cantor[line+1][start+i] = cantor[line+1][start+2*x/3+i] = '_';
        fractalize(line+1, start, start+x/3-1); fractalize(line+1, start+2*x/3, end); // wywołania rekurencyjne z różnymi przedziałami
}
int main()
{
        int n, i, j, k, x, len;
        char cantor[15][178000];

        get(n);
        len = pow(3, n-1);
        for(i = 0; i < len; ++i) // wypełniamy pierwszy wiersz
                cantor[0][i] = '_';
        for(i = 0; i < n; ++i) // musimy zaznaczyć koniec każdej linii pustym znakiem (zerem)
                cantor[i][len] = 0;
        fractalize(0, 0, len-1); // wywołujemy fractalize dla całego ciągu
        for(i = 0; i < n; ++i) // wypisujemy kolejne linie
                print(cantor[i]);
}

Rozwiązanie nr 3:
Jak już wspomniałem, poprzednie rozwiązanie jest jak DFS, co oznacza, że idzie wgłąb fraktala, co sprawia, że nie możemy na bieżąco wypisywać kolejnych wierszy, ale musimy je tablicować. A gdyby zamienić DFSa na BFSa? Wtedy przeszukiwalibyśmy fraktala wszerz, więc wystarczyłoby trzymać tylko jeden wiersz. I faktycznie, możemy w funkcji $fractalize$ zamiast wywołań rekurencyjnych wrzucać owe trójki liczb do kolejki w odpowiedniej kolejności i dzięki temu wypisywać na bieżąco kolejne linie fraktala.

Złożoność: $O\left(n \cdot 3^n\right)$. Złożoność pamięciowa: $O\left(3^n\right)$, bo trzymamy tylko 1 wiersz fraktala.

Brak komentarzy:

Prześlij komentarz