Główna zawartość
Informatyka
Course: Informatyka > Jednostka 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
Silnia rekurencyjna
Dla dodatnich wartości n, możemy zapisać n, !, jak już robiliśmy wcześniej, jako iloczyn liczb zaczynając od n i idąc w dół aż do 1: n, ! = n, dot, left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1. Ale zauważ, że left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1 to po prostu inny sposób zapisania left parenthesis, n, minus, 1, right parenthesis, !, więc możemy napisać, że n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, !. Widziałeś, co przed chwilą zrobiliśmy? Napisaliśmy n, ! jako iloczyn, w którym jednym z czynników jest left parenthesis, n, minus, 1, right parenthesis, !. Powiedzieliśmy, że możesz obliczyć n, ! poprzez obliczenie left parenthesis, n, minus, 1, right parenthesis, ! a następnie pomnożenie wyniku otrzymanego z left parenthesis, n, minus, 1, right parenthesis, ! przez n. Możesz obliczyć silnię z n najpierw obliczając wartość silni z n, minus, 1. Powiedzieliśmy zatem, że obliczenie left parenthesis, n, minus, 1, right parenthesis, ! jest podproblemem który rozwiązujemy aby obliczyć n!
Spójrzmy na przykład: obliczyć 5!
- Możesz obliczyć 5! jako 5, dot, 4, !.
- Teraz musisz rozwiązać podproblem obliczenia 4!, który możesz policzyć jako 4, dot, 3!
- Teraz musisz rozwiązać podproblem obliczenia 3!, które wynosi 3, dot, 2, !.
- Teraz 2!, które jest równe 2, dot, 1, !.
- Teraz musisz obliczyć 1!. Mógłbyś powiedzieć, że 1! jest równe 1, ponieważ jest to iloczyn wszystkich liczb całkowitych od 1 do 1. Lub możesz zastosować regułę, że 1, !, equals, 1, dot, 0, !. Zróbmy to przez zastosowanie formuły.
- Zdefiniowaliśmy 0! jako równe 1.
- Teraz możesz policzyć 1, !, equals, 1, dot, 0, !, equals, 1.
- Mając obliczone 1, !, equals, 1, możesz policzyć 2, !, equals, 2, dot, 1, !, equals, 2.
- Mając obliczone 2, !, equals, 2, możesz policzyć 3, !, equals, 3, dot, 2, !, equals, 6.
- Mając obliczone 3, !, equals, 6, możesz policzyć 4, !, equals, 4, dot, 3, !, equals, 24.
- W końcu, mając obliczone 4, !, equals, 24, możesz zakończyć przez obliczenie 5, !, equals, 5, dot, 4, !, equals, 120.
Poznaliśmy zatem inny sposób myślenia o tym jak można policzyć wartość n, !dla nieujemnych liczb całkowitych n:
- Jeśli n, equals, 0, to z definicji n, !, equals, 1.
- W przeciwnym przypadku n musi być dodatnie. Rozwiąż podproblem obliczenia left parenthesis, n, minus, 1, right parenthesis, !, pomnóż wynik przez n i ogłoś, że n, ! równa się wynikowi tego mnożenia.
Kiedy w ten sposób obliczamy n, !, odwołujemy się do pierwszego przypadku, w którym natychmiast znamy odpowiedź, czyli przypadku bazowego, a następnie wywołujemy drugi przypadek, w którym liczymy tą samą funkcję, ale przy użyciu innych wartości, czyli przypadek rekurencyjny.
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