algorytm.org

Potęgowanie z uwzględnieniem wykładników ujemnych

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Potęgowanie z uwzględnieniem wykładników ujemnych
Ocena użytkowników:***** / 8
SłabyŚwietny 
Wpisany przez Michał Witaszek, 10 czerwca 2012 13:41

Pierwszą rzeczą która kojarzy nam się z potęgowaniem jest dobrze nam znany wzór ogólny działania.

a^{b} = \underbrace{a * a * ... * a}_{ b}


Najprościej opisuje samą operację potęgowania. Na jego podstawie możemy łatwo ułożyć algorytm.
W skrócie algorytm można przedstawić następująco:
  1. Wczytaj a, b.
  2. Utwórz zmienną Wynik i nadaj jej wartość 1.
  3. Dopóki b > 0 do zmiennej Wynik przypisz wartość Wynik * a oraz zmniejsz b o 1.
  4. Wypisz Wynik.

Dla a0, zawsze zwróci wartość 1, ponieważ jeszcze przed wykonaniem pętli, do zmiennej wynik przypisaliśmy wartość 1, więc algorytm spełnia założenie:
a0 = 1


Algorytm dokładnie jest opisany na stronach serwisu w artykule potęgowanie.

Jego wadą jest to że nie może zostać użyty do wyliczania potęg z wykładnikami ujemnymi. Możemy jednak łatwo przekształcić powyżej opisaną funkcję korzystając z własności:
a^{-n}=\frac{1}{a^{n}}=\left(\frac{1}{a}\right)^{n}


Dla przykładu:
2-4 = 1/24 = 1/(2*2*2*2) = 1/16, lub
2-4 = (1/2)4 = 1/2 * 1/2 * 1/2 * 1/2 = 1/16

Lepiej użyć pierwszej własności, ponieważ możemy wykorzystać opisany wcześniej algorytm i na końcu podzielić 1 przez uzyskany wynik, wówczas operację dzielenia wykonamy tylko raz. Ewentualnie moglibyśmy wykonać dzielenie na początku i mnożyć uzyskany ułamek dziesiętny, ale wtedy dopuścilibyśmy większy margines błędu np. 3-n = (1/3)n.

Przekształcając algorytm potęgowania z wykładnikami naturalnymi uzyskujemy funkcję, którą możemy przedstawić następującą listą kroków:
  1. Wczytaj a, b.
  2. Utwórz zmienną Wynik i nadaj jej wartość 1.
  3. Dopóki b < 0 do zmiennej Wynik przypisz wartość Wynik * a oraz zwiększ b o 1.
  4. Do zmiennej Wynik przypisz wartość 1/Wynik
  5. Wypisz Wynik.


Algorytm różni się tym że zmienna b, czyli wykładnik jest mniejsza od 0, więc będziemy wykonywać pętle dopóki b będzie mniejsze od 0 i przy każdej iteracji, będziemy zwiększać b o 1, zamiast zmniejszać.
Algorytm możemy przedstawić za pomocą następującego schematu:
schemat blokowy - potęgowanie z ujemnym wykładnikiem


Powyższa funkcja z kolei może zostać użyta do obliczenia potęg wyłącznie z wykładnikami ujemnymi. Aby wyliczyć potęgi zarówno z wykładnikami dodatnimi jak i ujemnymi, wykorzystamy obydwie funkcje. W ten sposób uzyskujemy algorytm, który można przedstawić za pomocą następującego schematu:
schemat blokowy - potęgowanie z wykładnikiem całkowitym


W tym przypadku jeśli wykładnik wynosi 0, algorytm od razu wypisze zmienną wynik by ominąć pętle i nie wykonywać zbędnej iteracji. Podobnie jak wcześniej na początku algorytmu przypisaliśmy do zmiennej wynik wartość 1, więc założenie a0 = 1 zostanie spełnione.

Przykład w JavaScript:

Podaj podstawe:
Podaj wykladnik:



Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Adam DudzicC#
.cs
.cs
***** / 0
skyfallC#
.cs
.cs
***** / 0
Michał WitaszekC/C++C++
.cpp
.cpp
***** / 0
Adam CZC/C++C++, funkcja obliczająca wynik
.cpp
.cpp
***** / 1
Michał WitaszekDelphi/Pascal
.pas
.pas
***** / 1
mariuszwroclawJava
.java
.java
***** / 0
Michał WitaszekJavaScript
.js
.js
***** / 0
seveN.Php
.php
.php
***** / 0
Michał WitaszekPython
.py
.py
***** / 1
Nikodem SolarzRubymetoda obliczająca potęgę (na postawie algorytmu)
.rb
.rb
***** / 0
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 10 czerwca 2012 14:12
Komentarze
photo
-1 # san 2012-11-09 09:19
Bardzo przydatna stronka, dziękuję i pozdrawiam! :*** papatki :)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # java 2013-07-30 13:03
A co jak b = 0?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # Witamaster 2013-08-14 17:44
Cytat:
(...) jeśli wykładnik wynosi 0, algorytm od razu wypisze zmienną wynik by ominąć pętle i nie wykonywać zbędnej iteracji.

Jeśli b = 0 algorytm zwróci wynik z wartością taką jak na początku algorytmu. Na początku ustaliliśmy że wynik=1, więc założenie a^0=1 jest spełnione.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-5 # Eee... 2013-08-04 14:08
Cytat:
A co jak b = 0?

Cytat:
Dla a^0, zawsze zwróci wartość 1, ponieważ jeszcze przed wykonaniem pętli, do zmiennej wynik przypisaliśmy wartość 1, więc algorytm spełnia założenie: a^0 = 1

Czytać nie umiesz?!
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Zdolnycool 2014-05-07 17:31
Mam pytanie, czy to jest tylko jako przykład algorytmu czy faktycznie w ten sposób trzeba to użyć podczas implementacji? Czy języki programowania nie mają gotowej funkcji potęgowania? Jestem początkujący w tym temacie stąd moje pytanie. Pozdrawiam
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz