Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 1
Lekcja 6: Algorytmy rekurencyjne- Rekurencja
- Funkcja silnia
- Wyzwanie: silnia iterowana
- Silnia rekurencyjna
- Wyzwanie: silnia rekurencyjna
- Własności algorytmów rekurencyjnych
- Wykorzystanie rekurencji do zbadania czy słowo jest palindromem
- Wyzwanie: czy ten ciąg znaków to palindrom?
- Obliczanie potęgi danej liczby
- Wyzwanie: Potęgi rekurencyjne
- Wielokrotna rekurencja na przykładzie Trójkąta Sierpińskiego
- Ulepszanie wydajności funkcji rekurencyjnych
- Projekt: Sztuka rekurencji
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
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:
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:
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:
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.
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:
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:
- Narysuj dywan Sierpińskiego w lewym górnym kwadracie.
- Narysuj dywan Sierpińskiego w prawym górnym kwadracie.
- 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