algorytm.org

Potęgowanie



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
Ocena użytkowników:***** / 101
SłabyŚwietny 
Wpisany przez Bartosz Bednarczyk, 08 września 2011 14:04

Jednym z pierwszych algorytmów uczonych w szkole jest algorytm potęgowania liczb naturalnych.
Chodzi mianowicie o to, że użytkownik podaje dwie zmienne: a oraz b o wartościach naturalnych, a program ma obliczyć ab. Przychodzi tutaj na myśl własność potęgowania, ze:
a^{b} = \underbrace{a * a * ... * a}_{ b}


Na podstawie tego spostrzeżenia, możemy ułożyć algorytm. Zacznijmy od pseudokodu:
  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

Algorytm ten możemy przedstawić również za pomocą schematu blokowego:

schemat blokowy - potęgowanie


Przykład:

Poniżej zamieszczam tabelę przedstawiającą przebieg algorytmu dla a = 6, b = 3.
abWynik
631
626
6136
60216

Początkowo zmienna a ma wartosc 6, a zmienna b 3. Następnie tworzymy zmienna Wynik, której przypisujemy wartość 1. Następnie wpadamy w pętlę, w której mnożymy wynik i a, a potem zmniejszamy b o 1. Kiedy b będzie równe 0, wychodzimy z pętli i wypisujemy wynik.

Jest to najprostsza wersja potęgowania, wydajniejszy ale też bardziej skomplikowany algorytm opisany jest w artykule: Szybkie potęgowanie modularne

Przykład w JavaScript:

Podstawa:
Wykładnik:



Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Bartosz BednarczykC#
.cs
.cs
***** / 11
Bartosz BednarczykC/C++C
.cpp
.cpp
***** / 2
Bartosz BednarczykC/C++C++
.cpp
.cpp
***** / 4
Adam CZC/C++C++, iteracyjnie
.cpp
.cpp
***** / 3
Adam CZC/C++C++, rekurencyjnie
.cpp
.cpp
***** / 32
Michał WitaszekDelphi/Pascal
.pas
.pas
***** / 2
Bartosz BednarczykJava
.java
.java
***** / 4
Dominik GoździukJavawersja rekurencyjna (a^b = a^(b-1)*a)
.java
.java
***** / 4
Dominik GoździukJavaScript
.js
.js
***** / 16
Tomasz LubińskiJava_Block
.jbf
.jbf
***** / 1
Dominik GoździukPerlwersja rekurencyjna
.pl
.pl
***** / 1
Bartosz BednarczykPhpdane z stdin
.php
.php
***** / 2
seveN.Php
.php
.php
***** / 26
Bartosz BednarczykPython
.py
.py
***** / 4
Nikodem SolarzRubymetoda obliczająca wynik potęgowania
.rb
.rb
***** / 1
 
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: 28 października 2012 15:34
Komentarze
photo
-4 # Jackon 2012-03-26 14:37
Chyba zapomniano o wykładnikach ujemnych...
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # Witamaster 2012-05-28 11:57
Z założenia algorytm ma liczyć potęgi z wykładnikami naturalnymi Cytat:
a oraz b o wartościach naturalnych
, czyli nieujemnych. Ale korzystając z własności łatwo przekształcić algorytm. Trzeba jeszcze zmienić warunek pętli:
Dopóki b mniejsze od 0 do zmiennej Wynik przypisz wartość Wynik * a oraz zwiększ b o 1.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # Morena 2013-02-14 11:22
Nie umie Pan tłumaczyc!
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz