Trójkąt Sierpińskiego w języku C++ generowany rekurencyjnie

Aby napisać algorytm pozwalający narysować na ekranie fraktalfraktalfraktal zwany trójkątem Sierpińskiego, musimy zastanowić się, w jaki sposób chcemy przechowywać tę strukturę w programie. Utworzymy dwuwymiarową tablicę, w której wielokrotnie umieścimy znaki składające się na trójkąty. Wynikiem działania programu będzie wypisanie struktury podobnej do przedstawionej niżej (różniącej się rozmiarem lub użytymi znakami):

#
##
# #
####
#   #
##  ##
# # # #
########
#       #
##      ##
# #     # #
####    ####
#   #   #   #
##  ##  ##  ##
# # # # # # # #
################

Struktura taka może zostać utworzona za pomocą globalnej tablicy typu bool, zadeklarowanej w następujący sposób:

const int STOPIEN = 4;
bool trojkat[1 << STOPIEN][1 << STOPIEN];

Wiele osób może zdziwić taka deklaracja, ale za chwilę wszystko się wyjaśni. Operator << oznacza, że dokonujemy przesunięcia bitowegoprzesunięcie bitoweprzesunięcia bitowego. Na potrzeby bieżącego e‑materiału możemy przyjąć, że prawdziwa jest następująca zależność:

Dzięki zastosowaniu operacji przesunięcia bitowego jesteśmy w stanie obliczyć kolejne potęgi liczby 2 bez potrzeby użycia funkcji. W rezultacie możemy zadeklarować tablicę, której rozmiar zostanie obliczony w momencie kompilacji. Warto zapamiętać powyższą własność, gdyż zostanie ona wykorzystana również w dalszej części programu.

Po zadeklarowaniu tablicy globalnie, możemy przejść do realizacji głównej części programu. Napiszmy funkcję, która wypełni tablicę znakami składającymi się na trójkąt Sierpińskiego. Ponieważ chcemy wykorzystać rekurencję, funkcja musi przyjmować odpowiednie parametry. W wypadku fraktala najważniejszy jest jego stopień. Trójkąt Sierpińskiego składa się z trzech mniejszych trójkątów Sierpińskiego oraz z jednego „białego” (pustego) trójkąta w środku; potrzebnymi parametrami będą zatem współrzędne, od których tablica zostanie wypełniona kolejnym trójkątem. Przez współrzędne rozumiemy górny wierzchołek trójkąta, który rysujemy. Deklaracja funkcji może wyglądać następująco:

void utworzTrojkat(int stopien, int x, int y);

W każdej funkcji rekurencyjnej należy określić moment zakończenia jej działania. W rozpatrywanym przypadku będzie to etap, gdy stopień fraktala osiągnie wartość 0. Uzupełnimy wówczas pojedynczy element tablicy (zawierający opis pojedynczego elementu trójkąta) wartością true. Zapiszmy zatem warunek, dzięki któremu zostanie wykryty moment zakończenia rekurencji:

void utworzTrojkat(int stopien, int x, int y) {
	// warunek końcowy
	if (stopien == 0) {
		trojkat[y][x] = true;
	} else {
		// kolejne wywołania rekurencyjne
	}
}

Obecnie funkcję można wywołać tylko z parametrem stopien = 0. W przeciwnym razie nie zostanie wykonana żadna operacja. Zastanówmy się, w jaki sposób należy uruchomić kolejne etapy rekurencji.

Musimy zlecić narysowanie trzech trójkątów Sierpińskiego (których stopień będzie o 1 mniejszy) przy użyciu odpowiednich współrzędnych tablicy, a także narysować „białą” część trójkąta wewnątrz. Współrzędne pierwszego trójkąta są oczywiste, ponieważ musimy narysować go w górnym wierzchołku, czyli w tym samym miejscu, w którym się znajdujemy. Pierwsze wywołanie kolejnej rekurencji będzie wyglądać zatem następująco:

void utworzTrojkat(int stopien, int x, int y) {
	// warunek końcowy
	if (stopien == 0) {
		trojkat[y][x] = true;
	} else {
		// kolejne wywołania rekurencyjne
		// pierwszy trójkąt:
		utworzTrojkat(stopien - 1, x, y);
	}
}

Chcąc narysować kolejne trójkąty, musimy najpierw obliczyć ich rozmiary. Określą one przesunięcie w kierunku następnych współrzędnych. W tym celu ponownie posłużymy się przesunięciem bitowym. Wówczas możemy zlecić rysowanie kolejnych trójkątów w następujący sposób:

void utworzTrojkat(int stopien, int x, int y) {
	// warunek końcowy
	if (stopien == 0) {
		trojkat[y][x] = true;
	} else {
		// kolejne wywołania rekurencyjne
		// pierwszy trójkąt:
		utworzTrojkat(stopien - 1, x, y);
        
		// rozmiar stanowiący przesunięcie
		int rozmiar = 1 << (stopien - 1);
        
		// kolejne 2 trójkąty:
		utworzTrojkat(stopien - 1, x, y + rozmiar);
		utworzTrojkat(stopien - 1, x + rozmiar, y + rozmiar);
	}
}

Teraz pozostaje już tylko wypełnić środkowy „biały” trójkąt. Można to zrobić np. za pomocą dwóch zagnieżdżonych pętli for. Pamiętajmy, że środkowy trójkąt w powstałej strukturze ma mieć rozmiar o 1 mniejszy niż pozostałe trzy trójkąty.

void utworzTrojkat(int stopien, int x, int y) {
	// warunek końcowy
	if (stopien == 0) {
		trojkat[y][x] = true;
	} else {
		// kolejne wywołania rekurencyjne
		// pierwszy trójkąt:
		utworzTrojkat(stopien - 1, x, y);
        
		// rozmiar stanowiący przesunięcie
		int rozmiar = 1 << (stopien - 1);
        
		// kolejne 2 trójkąty:
		utworzTrojkat(stopien - 1, x, y + rozmiar);
		utworzTrojkat(stopien - 1, x + rozmiar, y + rozmiar);
        
		// 1 biały trójkąt w środku
		for (int i = 0; i < rozmiar - 1; ++i) {
			for (int j = i; j < rozmiar - 1; ++j) {
				trojkat[y + rozmiar + i][x + 1 + j] = false;
			}
		}
	}
}

Należy także przygotować funkcję, która wypisze zawartość utworzonej tablicy. Znowu posłużymy się przesunięciem bitowym oraz dwiema zagnieżdżonymi pętlami for:

void wypiszTrojkat() {
	for (int i = 0; i < (1 << STOPIEN); ++i) {
		for (int j = 0; j <= i; ++j) {
			std::cout << (trojkat[i][j] ? "#" : " ");
		}
        
		std::cout << std::endl;
	}
}

Po połączeniu wszystkich elementów oraz napisaniu funkcji main() otrzymujemy następujący kod:

#include <iostream>

const int STOPIEN = 4;
bool trojkat[1 << STOPIEN][1 << STOPIEN];

void utworzTrojkat(int stopien, int x, int y) {
	// warunek końcowy
	if (stopien == 0) {
		trojkat[y][x] = true;
	} else {
		// kolejne wywołania rekurencyjne
		// pierwszy trójkąt:
		utworzTrojkat(stopien - 1, x, y);

		// rozmiar stanowiący przesunięcie
		int rozmiar = 1 << (stopien - 1);

		// kolejne 2 trójkąty:
		utworzTrojkat(stopien - 1, x, y + rozmiar);
		utworzTrojkat(stopien - 1, x + rozmiar, y + rozmiar);

		// 1 biały trójkąt w środku
		for (int i = 0; i < rozmiar - 1; ++i) {
			for (int j = i; j < rozmiar - 1; ++j) {
				trojkat[y + rozmiar + i][x + 1 + j] = false;
			}
		}
	}
}

void wypiszTrojkat() {
	for (int i = 0; i < (1 << STOPIEN); ++i) {
		for (int j = 0; j <= i; ++j) {
			std::cout << (trojkat[i][j] ? "#" : " ");
		}
        
		std::cout << std::endl;
	}
}

int main() {
	utworzTrojkat(STOPIEN, 0, 0);
	wypiszTrojkat();
	return 0;
}

Po uruchomieniu programu na ekranie pojawi się figura:

#
##
# #
####
#   #
##  ##
# # # #
########
#       #
##      ##
# #     # #
####    ####
#   #   #   #
##  ##  ##  ##
# # # # # # # #
################

Taką właśnie strukturę chcieliśmy uzyskać. Można jeszcze uzupełnić funkcję wypiszTrojkat() o kolejną pętlę for dopisującą spacje (oraz dodać spacje podczas odczytywania elementów tablicy trojkat). W rezultacie powstanie lustrzane odbicie trójkąta.

void wypiszTrojkat() {
	for (int i = 0; i < (1 << STOPIEN); ++i) {
		for (int j = 0; j <= (1 << STOPIEN) - i - 2; ++j) {
			std::cout << " ";
		}
        
		for (int j = 0; j <= i; ++j) {
			std::cout << (trojkat[i][j] ? " #" : "  ");
		}
        
		std::cout << std::endl;
	}
}

Efekt działania zmodyfikowanego programu będzie następujący:

                #
               # #
              #   #
             # # # #
            #       #
           # #     # #
          #   #   #   #
         # # # # # # # #
        #               #
       # #             # #
      #   #           #   #
     # # # #         # # # #
    #       #       #       #
   # #     # #     # #     # #
  #   #   #   #   #   #   #   #
 # # # # # # # # # # # # # # # #

Słownik