Ile trójkątów na obrazku?

Zagadka

Ile jest trójkątów na poniższym obrazku? Grafika powstała poprzez zastosowanie pewnej reguły, której znajomość pozwoli na wyliczenie liczby, która będzie odpowiedzią na zadane pytanie.

Rozwiązanie

Odpowiedź

Na obrazku znajdują się 40 trójkątów. Grafika przedstawia trójkąt Sierpińskiego.

Wyjaśnienie

W celu wyjaśnenia jak obliczyć ile trójkątów znajduje się na obrazku należy przyjrzeć się kolejnym etapom rysowania trójkąta Sierpińskiego i sprawdzić ile nowych trójkątów pojawia się w każdym etapie rysowania:

1 nowy

3 nowe

9 nowych

27 nowych

Jak można zauważyć za każdym razem powstaje 3^{i - 1} nowych trójkątów, gdzie i to numer iteracji. Bardzo ważne jest również to, że na i-tym rysunku są wszystkie dotychczasowe "nowe" trójkąty. Zadanie można rozpisać w tabelce:

Iteracja	Nowych trójkątów	Łącznie
1	1	1
2	3	4
3	9	13
4	27	40
5	81	121
..	..	..

Kolejne sumowane wyrazy tworzą ciąg geometryczny. Oznacza to, że dla dowolnej iteracji wartość można wyliczyć przy pomocy następującego wzoru: S_i = (3^{i + 1} - 1) / 2

Implementacja

Poniżej zostaną przedstawione trzy sposoby na wyliczenie ile trójkątów znajduje się w trójkącie Sierpińskiego i-tego stopnia. Każda technika charakteryzuje się inną złożonością czasową jak i pamięciową.

Wersja rekurenycjna

Liczbę rysowanych trójkątów można obliczyć w sposób rekurencyjny czyli w taki sam sposób jak się taką grafikę rysuje. Ze względu na to, że funkcja potęgowa bardzo szybko rośnie to nie jest to najbardziej efektywna metoda. Oto kod:

1. int ileTrojkatowRek(int i) {
2.   if (i <= 1) return i;
3.   return 3 * ileTrojkatowRek(i - 1) + 1;
4. }

Funkcja zostanie wywołana dokładnie i-razy, więc ma ona złożoność porównywalną z iteracyjną, ale należy pamiętać, że im głębsza rekurencja tym więcej pamięci potrzebuje.

Wersja iteracyjna

W wersji iteracyjnej będą dodawane kolejne potęgi liczby 3. W celu zwiększenia wydajności każdy następny składnik zostanie wyliczony na podstawie poprzedniego składnika sumy. W ten sposób liczba potrzebnych mnożeń zostanie zminimalizowana. Algorytm ma złożoność liniową O(n) i jest on bardziej wydajny od algorytmu rekurencyjnego.

1. int ileTrojkatowIter(int i) {
2.   int suma = 0;
3.   int skladnik = 1;
4.   while (i-- > 0) {
5.     suma += skladnik;
6.     skladnik *= 3;
7.   }
8.   return suma;
9. }

(2.) Początkowo suma ma wartość 0, a (3.) dodawany składnik to jeden. (4.) Dopóki są elementy do zsumowania to: (5.) dodajemy aktualnie wyliczony i (6.) obliczamy następny. Na koniec (8.) zwrócona zostaje obliczona suma.

Wzór

Oczywiście najszybszą metodą jest wyliczenie wartości ze wzoru. Pomijają złożoność potęgowania to algorytm ma złożoność czasową O(1).

1. int ileTrojkatowWzor(int i) {
2.   return (pow(3, i) - 1) / 2;
3. }

Testowanie funkcji

Poniższy fragment kodu wczytuje od użytkownika dla jakiej iteracji ma wypisać ile jest łącznie trójkątów w trójkącie Sierpińskiego i wypisuje tę wartość:

1. int main() {
2.   int i;
3.   cout << "Podaj ile iteracji\n i = ";
4.   cin >> i;
5.   cout << ileTrojkatowWzor(i);
6.   system("pause");
7.   return 0;

• Kod źródłowy Implementacja