Jeśli widzisz tę wiadomość oznacza to, że mamy problemy z załadowaniem zewnętrznych materiałów na naszej stronie internetowej.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Główna zawartość

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ć xn, gdzie xjakąś liczbą rzeczywistą a n jest dowolną liczbą całkowitą. Łatwo podać odpowiedź gdy n równa się 0, ponieważ x0=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: xaxb=xa+b dla dowolnej podstawy x oraz dowolnych wykładników a i b. Dlatego jeśli n jest dodatnie i parzyste, wtedy xn=xn/2xn/2. Jeśli miałeś policzyć y=xn/2 przy użyciu rekurencji, wtedy możesz obliczyć xn jako yy. Co w przypadku, gdy n jest dodatnie i nieparzyste? Wtedy xn=xn1x, an1 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ć xn1 przez zastosowanie rekurencji, a następnie użyć tego wyniku, aby obliczyć xn=xn1x.
Co w przypadku, gdy n jest ujemne? Wtedy xn=1/xn, a wykładnik n jest dodatni, ponieważ jest to liczba przeciwna do liczby ujemnej. Czyli możesz obliczyć xn 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 xn:
  • Bazowy przypadek występuje dla n=0, i x0=1.
  • Jeśli n jest dodatnie i parzyste, rekurencyjnie obliczamy y=xn/2, a wtedy xn=yy. Zauważmy, że w tym przypadku możemy wykonać tylko jedno wywołanie rekurencyjne, obliczając xn/2 tylko raz, a następnie mnożąc wynik tego wywołania przez siebie.
  • Jeśli n jest dodatnie i nieparzyste, rekurencyjnie obliczamy xn1, więc wykładnik jest równy 0 lub jest dodatni i parzysty. Wtedy xn=xn1x.
  • Jeśli n jest ujemne, rekurencyjnie obliczamy xn, więc wykładnik staje się liczbą dodatnią. Wtedy, xn=1/xn.
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.