If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Wielokrotna rekurencja na przykładzie Trójkąta Sierpińskiego

Jak dotąd przedstawione tu przykłady rekurencji, wymagały od ciebie tylko jednego wywołania rekurencyjnego za każdym razem. Ale czasem trzeba wykonać wiele wywołań rekurencyjnych. Oto dobry przykład: matematyczna konstrukcja, będąca fraktalem, zwana Trójkątem Sierpińskiego:
Pełen trójkąt Sierpińskiego
Jak widać, jest to kolekcja małych kwadratów narysowanych według szczególnego wzoru na kwadratowym obszarze. Oto jak ją narysować. Zacznijmy od dużego kwadratu, stanowiącego cały obszar, i podzielmy go na cztery równe obszary jak poniżej:
Trójkąt Sierpińskiego 2 na 2
Weźmy teraz pod uwagę trzy kwadraty zaznaczone × czyli — górny z lewej strony, górny z prawej strony i dolny z prawej strony — i podzielmy je na cztery obszary w taki sam sposób jak powyżej:
Trójkąt Sierpińskiego 4 na 4
Powtarzaj te same operacje. Dziel każdy kwadrat oznaczony × na cztery obszary i umieszczaj × w kwadratach: górnym lewym, górnym prawym i dolnym prawym, ale nigdy nie w dolnym lewym.
Trójkąt Sierpińskiego 8 na 8
Trójkąt Sierpińskiego 16 na 16
Trójkąt Sierpińskiego 32 na 32
Trójkąt Sierpińskiego 64 na 64
Gdy kwadraty są już wystarczająco małe, przestań je dzielić. Wypełnij teraz kolorem każdy kwadrat zawierający ×, ale pomiń pozostałe kwadraty. W ten sposób dostajesz Trójkąt Sierpińskiego. Oto on jeszcze raz:
Pełen trójkąt Sierpińskiego
Podsumowując, oto jak narysować trójkąt Sierpińskiego w kwadracie:
  • Sprawdź, jak mały jest ten kwadrat. Jeśli jest dostatecznie mały, aby stać się przypadkiem bazowym, wypełnij kwadrat. Musisz zdecydować, co to znaczy "dostatecznie mały".
  • Jeśli nie jest dostatecznie mały, podziel kwadrat na cztery mniejsze kwadraty: górny lewy, górny prawy, dolny lewy i dolny prawy kwadrat. Użyj rekurencji, aby "rozwiązać" trzy podproblemy:
    1. Narysuj dywan Sierpińskiego w lewym górnym kwadracie.
    2. Narysuj dywan Sierpińskiego w prawym górnym kwadracie.
    3. Narysuj dywan Sierpińskiego w prawym dolnym kwadracie.
Zauważ, że potrzebujesz wykonać tu nie tylko jedno, ale trzy odwołania rekurencyjne. Dlatego właśnie rozważaliśmy rysowanie trójkąta Sierpińskiego jako przykład wielokrotnego wywołania rekurencyjnego.
Możesz wybrać jakikolwiek trzy z czterech kwadratów, w których rekurencyjnie narysujesz trójkąt Sierpińskiego. Rezultatem będzie po prostu rysunek odwrócony o jakąś wielokrotność 90 stopni w stosunku do podawanego tu przykładu. (Jeśli narysujesz trójkąt Sierpińskiego z jakąkolwiek inną liczbą kwadratów, nie dostaniesz interesującego wyniku).
Poniższyprogram rysuje dywan Sierpińskiego. Spróbuj skomentować lub usunąć komentarz z niektórych rekurencyjnych odwołań, aby otrzymać obrócone trójkąty:

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.

Chcesz dołączyć do dyskusji?

Na razie brak głosów w dyskusji
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.