Przeczytaj

Podanie jednej definicji pojęcia fraktal nie jest łatwe. Możemy powiedzieć, że jest to obiekt samopodobny. W wielu przypadkach można stwierdzić, że gdy mamy do czynienia z fraktalem, cała figura podobna jest do składających się na nią elementów. Taką definicję określamy mianem rekurencyjnej.

Znamy już wiele przykładów fraktali. Ten materiał poświęcimy generowaniu wybranych fraktali za pomocą programu w języku Java.

Trójkąt Sierpińskiego w języku Java

Najprostsza metoda konstruowania trójkąta Sierpińskiego wykorzystuje trójkąt Pascala. Zacznijmy od napisania funkcji generującej trójkąt Pascala o podanej wysokości.

Przypomnijmy najpierw, jak wygląda trójkąt Pascala:

 0                     1
 1                   1   1
 2                 1   2   1
 3               1   3   3   1
 4             1   4   6   4   1
 5           1   5   10  10   5   1
 6         1   6   15  20  15   6   1
 7       1   7   21  35  35   21  7   1
 8     1   8   28  56  70  56   28  8   1
 9   1   9  36   84  126 126  84  36  9   1

Przeanalizujemy dwie metody budowania trójkąta Pascala. Niech $t (n, k)$ oznacza wartość elementu wchodzącego w skład trójkąta Pascala w rzędzie numer $n$ na pozycji numer $k$ . Numerowanie zaczynamy od zera przy założeniu, że $k \leq n$ . W takim przypadku:

t (n, 0) = 1

t (n, n) = 1

t (n, k) = t (n - 1, k) + t (n - 1, k - 1)

Istnieje również definicja, która wykorzystuje dwumian Newtonadwumian (symbol) Newtonadwumian Newtona:

t (n, k) = (\binom{n}{k})

W przypadku skorzystania z tej definicji konieczne jest jednak obliczanie silni. W rezultacie złożoność metody opartej na symbolu Newtona jest znacząco większa. Gdy interesuje nas wygenerowanie dużej części trójkąta Pascala, pierwsza metoda ma znaczącą przewagę.

Napiszmy funkcję, która wyświetli na ekranie trójkąt Pascala. Funkcja będzie przyjmować parametr n, który oznacza wysokość trójkąta.

Linia 1. public static void trojkatPascala otwórz nawias okrągły int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. prawy ukośnik prawy ukośnik utworzenie tablicy n x n. Linia 3. int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy tablica znak równości new int otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 5. prawy ukośnik prawy ukośnik wypełnienie tablicy. Linia 6. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości 1 średnik. Linia 8. tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 1 średnik. Linia 10. for otwórz nawias okrągły int j znak równości 1 średnik j otwórz nawias ostrokątny i średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości tablica otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy plus tablica otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 12. zamknij nawias klamrowy. Linia 13. zamknij nawias klamrowy. Linia 15. prawy ukośnik prawy ukośnik wypisanie tablicy. Linia 16. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny znak równości i średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. System kropka out kropka print otwórz nawias okrągły tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 19. zamknij nawias klamrowy. Linia 21. System kropka out kropka print otwórz nawias okrągły apostrof lewy ukośnik n apostrof zamknij nawias okrągły średnik. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy.

public static void trojkatPascala(int n) {
	// utworzenie tablicy n x n
	int[][] tablica = new int[n][n];

	// wypełnienie tablicy
	for (int i = 0; i < n; i++) {
		tablica[i][0] = 1;
		tablica[i][i] = 1;

		for (int j = 1; j < i; j++) {
			tablica[i][j] = tablica[i - 1][j - 1] + tablica[i - 1][j];
		}
	}

	// wypisanie tablicy
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			System.out.print(tablica[i][j] + " ");
		}
        
		System.out.print('\n');
	}
}

Zauważ, że w pierwszej pętli generujemy tablicę (linie 6–13), która przechowuje elementy trójkąta Pascala. Dzięki kolejnej pętli (linie 16–22) wyświetlamy elementy trójkąta. Wypisywanie mogłoby jednak zostać zrealizowane „przy okazji” wewnątrz poprzedniej pętli for.

Linie 7. oraz 8. to początkowe założenia – dwa pierwsze równania podane w definicji trójkąta Pascala. W linii 11. realizujemy trzecie równanie należące do definicji.

Spróbujmy uruchomić funkcję z parametrem n = 10. Na ekranie pojawi się następujący obraz:

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1

Trójkąt ten jest taki sam jak w przykładzie, który przedstawiliśmy wcześniej.

Zastanówmy się, jak zmienić trójkąt Pascala w trójkąt Sierpińskiego. Między tymi dwoma konstrukcjami istnieje pewna zależność. Parzyste liczby w trójkącie Pascala układają się w trójkąt Sierpińskiego. Jeżeli zatem rysując trójkąt Pascala zamiast liczby nieparzystej, wpiszemy np. znak #, a znakami spacji zastąpimy liczby parzyste, otrzymamy trójkąt Sierpińskiego. Sprawdźmy to, modyfikując linię 18. w funkcji trojkatPascala():

Linia 1. public static void trojkatSierpinskiego otwórz nawias okrągły int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. prawy ukośnik prawy ukośnik utworzenie tablicy n x n. Linia 3. int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy tablica znak równości new int otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 5. prawy ukośnik prawy ukośnik wypełnienie tablicy. Linia 6. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości 1 średnik. Linia 8. tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 1 średnik. Linia 10. for otwórz nawias okrągły int j znak równości 1 średnik j otwórz nawias ostrokątny i średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości tablica otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy plus tablica otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 12. zamknij nawias klamrowy. Linia 13. zamknij nawias klamrowy. Linia 15. prawy ukośnik prawy ukośnik wypisanie parzystości tablicy. Linia 16. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny znak równości i średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. if otwórz nawias okrągły tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy procent 2 znak równości znak równości 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. System kropka out kropka print otwórz nawias okrągły apostrof kratka apostrof zamknij nawias okrągły średnik. Linia 20. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 21. System kropka out kropka print otwórz nawias okrągły apostrof apostrof zamknij nawias okrągły średnik. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy. Linia 25. System kropka out kropka print otwórz nawias okrągły apostrof lewy ukośnik n apostrof zamknij nawias okrągły średnik. Linia 26. zamknij nawias klamrowy. Linia 27. zamknij nawias klamrowy.

public static void trojkatSierpinskiego(int n) {
	// utworzenie tablicy n x n
	int[][] tablica = new int[n][n];

	// wypełnienie tablicy
	for (int i = 0; i < n; i++) {
		tablica[i][0] = 1;
		tablica[i][i] = 1;

		for (int j = 1; j < i; j++) {
			tablica[i][j] = tablica[i - 1][j - 1] + tablica[i - 1][j];
		}
	}

	// wypisanie parzystości tablicy
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			if (tablica[i][j] % 2 == 1) {
				System.out.print('#');
			} else {
				System.out.print(' ');
			}
		}
        
		System.out.print('\n');
	}
}

Oto efekt wywołania funkcji z parametrem n = 10:

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

Łatwo zauważyć, że przedstawiona struktura przypomina trójkąt Sierpińskiego, jednak niewłaściwa jest jej wysokość. Problem polega na tym, że wysokość trójkąta Sierpińskiego musi być potęgą liczby 2. W takim przypadku otrzymamy poprawnie zbudowany fraktal. Wywołajmy zatem funkcję trojkatSierpinskiego() dla parametru n = 32:

Linia 1. kratka. Linia 2. kratka kratka. Linia 3. kratka kratka. Linia 4. kratka kratka kratka kratka. Linia 5. kratka kratka. Linia 6. kratka kratka kratka kratka. Linia 7. kratka kratka kratka kratka. Linia 8. kratka kratka kratka kratka kratka kratka kratka kratka. Linia 9. kratka kratka. Linia 10. kratka kratka kratka kratka. Linia 11. kratka kratka kratka kratka. Linia 12. kratka kratka kratka kratka kratka kratka kratka kratka. Linia 13. kratka kratka kratka kratka. Linia 14. kratka kratka kratka kratka kratka kratka kratka kratka. Linia 15. kratka kratka kratka kratka kratka kratka kratka kratka. Linia 16. kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka. Linia 17. kratka kratka. Linia 18. kratka kratka kratka kratka. Linia 19. kratka kratka kratka kratka. Linia 20. kratka kratka kratka kratka kratka kratka kratka kratka. Linia 21. kratka kratka kratka kratka. Linia 22. kratka kratka kratka kratka kratka kratka kratka kratka. Linia 23. kratka kratka kratka kratka kratka kratka kratka kratka. Linia 24. kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka. Linia 25. kratka kratka kratka kratka. Linia 26. kratka kratka kratka kratka kratka kratka kratka kratka. Linia 27. kratka kratka kratka kratka kratka kratka kratka kratka. Linia 28. kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka. Linia 29. kratka kratka kratka kratka kratka kratka kratka kratka. Linia 30. kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka. Linia 31. kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka. Linia 32. kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka.

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

Praca domowa

Zmodyfikuj funkcję trojkatSierpinskiego() w taki sposób, aby tablica, w której przechowujemy elementy trójkąta Pascala, była typu boolean.

Słownik

dwumian (symbol) Newtona

wzór stosowany w kombinatoryce w celu określenia liczby wszystkich k‑elementowych kombinacji bez powtórzeń ze zbioru n‑elementowego; zależność taka ma postać:

(\binom{n}{k}) = \frac{n!}{(n - k)! k!}

0 \leq k \leq n

Wprowadzenie

Symulacja interaktywna

Trójkąt Sierpińskiego w języku Java

Słownik