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
Obliczanie potęgi danej liczby
JavaScript ma wprawdzie wbudowaną funkcję
pow
, która oblicza potęgi danej liczby ale korzystając z rekurencji możesz napisać taką funkcję samemu tak, by była bardzo wydajna. Jedyny szkopuł polega na tym że wykładnik potęgi musi być liczbą całkowitą.Załóżmy że chcesz obliczyć x, start superscript, n, end superscript, gdzie xjakąś liczbą rzeczywistą a n jest dowolną liczbą całkowitą. Łatwo podać odpowiedź gdy n równa się 0, ponieważ x, start superscript, 0, end superscript, equals, 1 niezależnie od tego ile wynosi x . To dobry przypadek bazowy.
Więc teraz zobaczmy, co stanie się kiedy n jest dodatnie. Zacznijmy od przypomnienia, że kiedy mnożysz potęgi zmiennej x, dodajesz wykładniki: x, start superscript, a, end superscript, dot, x, start superscript, b, end superscript, equals, x, start superscript, a, plus, b, end superscript dla dowolnej podstawy x oraz dowolnych wykładników a i b. Dlatego jeśli n jest dodatnie i parzyste, wtedy x, start superscript, n, end superscript, equals, x, start superscript, n, slash, 2, end superscript, dot, x, start superscript, n, slash, 2, end superscript. Jeśli miałeś policzyć y, equals, x, start superscript, n, slash, 2, end superscript przy użyciu rekurencji, wtedy możesz obliczyć x, start superscript, n, end superscript jako y, dot, y. Co w przypadku, gdy n jest dodatnie i nieparzyste? Wtedy x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x, an, minus, 1 wynosi albo 0, albo jest dodatnie i parzyste. Właśnie zobaczyliśmy jak obliczyć potęgi liczby x kiedy wykładnik jest równy 0 lub jest dodatni i parzysty. Dlatego możesz policzyć x, start superscript, n, minus, 1, end superscript przez zastosowanie rekurencji, a następnie użyć tego wyniku, aby obliczyć x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x.
Co w przypadku, gdy n jest ujemne? Wtedy x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript, a wykładnik minus, n jest dodatni, ponieważ jest to liczba przeciwna do liczby ujemnej. Czyli możesz obliczyć x, start superscript, minus, n, end superscript stosując rekurencję i wziąć odwrotność tej liczby.
Łącząc wszystkie powyższe rozważania w całość, otrzymujemy następujący algorytm rekurencyjny do obliczania x, start superscript, n, end superscript:
- Bazowy przypadek występuje dla n, equals, 0, i x, start superscript, 0, end superscript, equals, 1.
- Jeśli n jest dodatnie i parzyste, rekurencyjnie obliczamy y, equals, x, start superscript, n, slash, 2, end superscript, a wtedy x, start superscript, n, end superscript, equals, y, dot, y. Zauważmy, że w tym przypadku możemy wykonać tylko jedno wywołanie rekurencyjne, obliczając x, start superscript, n, slash, 2, end superscript tylko raz, a następnie mnożąc wynik tego wywołania przez siebie.
- Jeśli n jest dodatnie i nieparzyste, rekurencyjnie obliczamy x, start superscript, n, minus, 1, end superscript, więc wykładnik jest równy 0 lub jest dodatni i parzysty. Wtedy x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x.
- Jeśli n jest ujemne, rekurencyjnie obliczamy x, start superscript, minus, n, end superscript, więc wykładnik staje się liczbą dodatnią. Wtedy, x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript.
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