Strona główna » Algorytmy » Artykuły » Potęgowanie bez mnożenia
 

Potęgowanie bez mnożenia

https://mattomatti.com/a0026

Wstęp

Zapis potęgowy definiuje się jako skrócony zapis mnożenia. Jest on bardzo wygodny i pozwala zaoszczędzić bardzo dużo czasu. Jednak potęgowanie można zdefiniować poprzez operację dodawania. W tym artykule zostanie omówiona metoda potęgowania, która nie wymaga znajomości mnożenia, a jedynie potęgowania.

Metoda

Załóżmy, że należy wyliczyć an, gdzie obie liczb należą do liczb naturalnych. Przypatrzmy się uważnie zapisowi potęgowemu an = a·a·..·a, gdzie po prawej stronie stoi dokładnie n czynników a. Z kolei każde mnożenia można zapisać jako a·a = a+a+..+a, gdzie po prawej stronie stoi a czynników a. Przykładowo jeśli weźmie się 23 = 2·2·2 = (2 + 2)·2 = (2 + 2) + (2 + 2) = 8. Wprowadźmy więc następujący algorytm obliczania potęgi.

  1. Wczytaj dane
  2. Rozpisz potęga na iloczyn n czynników
  3. Dopóki liczba czynników jest większa od 1 to:
    • Pobierz dwa pierwsze czyniki a1, a2
    • Dodaj a1 a2 razy
    • Wstaw wyliczoną sumę jako pierwszy czynnik

Zobaczmy działanie rozpisanego algorytmu dla 34. Na początek utwórzmy listę Czynniki

CzynnikiOperacja
{3, 3, 3, 3}a1 = 3, a2 = 3, suma = 3 + 3 + 3 = 9
{9, 3, 3}a1 = 9, a2 = 3, suma = 9 + 9 + 9 = 27
{27, 3}a1 = 27, a2 = 3, suma = 27 + 27 + 27 = 81
{81}Zwróć wynik 81

Implementacja

Prosta

Przedstawiona poniżej funkcja potega() oblicza określoną potęge przy założeniu, że a i n to liczby naturalne. W przedstawionym przykładzie pętla dopóki została zamieniona na pętle for, ponieważ z góry wiadomo ile razy trzeba będzie ją wywołać.

  1. int potega(int a, int n) {
  2.   if (n == 0)
  3.     return 1;
  4.   int suma = a;
  5.   int czynnik = a;
  6.   for (int i = 1; i < n; i++) {
  7.     for (int j = 1; j < a; j++) {
  8.       czynnik += suma;
  9.     }
  10.     suma = czynnik;
  11.   }
  12.   return czynnik;
  13. }

W funkcji (2.) wyróżniony został przypadek podnoszenia potęgi do 0. Następnie deklarowane są zmienne (3.) w - do niej będzie zapisywana suma w pełnej iteracji oraz (4.) suma - aktualna wartość pierwszego czynnika. Wykonując (5.) n - 1 pętli składającej się z (6. - 8.) wyliczenia sumy i (9.) przyjęcia jej za nowy, pierwszy czynnik. Na koniec (11.) Wynik znajduje się w zmiennej suma.

Ugólnienie

Jednak ograniczenie do samych liczb naturalnych nie jest zbyt przyjazne użytkownikowi, ani programiście, dlatego w nowej wersji algorytmu zostanie uwzględnione, że a może należeć do liczb całkowitych. Na początek należy sprawdzić czy liczba a jest ujemna. Jeśli tak to należy usunąć minusa, a potem go ponownie dołożyć jeśli potęga jest nieparzysta.

Nowy kod jest niemalże identyczny do poprzedniego, ale jego funkcjonalność jest zdecydowanie rozszerzona:

  1. int potega(int a, int n) {
  2.   if (n == 0)
  3.     return 1;
  4.   bool minus = a < 0;
  5.   a = abs(a);
  6.   int suma = a;
  7.   int czynnik = a;
  8.   for (int i = 1; i < n; i++) {
  9.     for (int j = 1; j < a; j++) {
  10.       czynnik += suma;
  11.     }
  12.     suma = czynnik;
  13.   }
  14.   if (minus && n % 2 == 1)
  15.     czynnik = -czynnik;
  16.   return czynnik;
  17. }

Dodane zostały linijki, które (5.) pamiętają czy a było początkowe ujemna oraz (6.) zapewniają, że liczba a jest zawsze dodatnia. Dodatkowo na koniec (14.) jeśli a było początkowo ujemna oraz potęga do której liczba jest podnoszona jest nieparzyste to (15.) dodawany jest minus.

Testowanie funkcji

Poniżej został przedstawiony kod funkcji main(), która wczytuje od użytkownika dane i wyświetla wyliczoną potęge. Należy pamiętać, że w przypadku pierwszego kodu a musi być liczbą dodatnią - inaczej program działa niepoprawnie.

  1. int main() {
  2.   int a, n;
  3.   cout << "Podaj liczbe a: ";
  4.   cin >> a;
  5.   cout << "Podaj potege n: ";
  6.   cin >> n;
  7.   cout << a << "^" << n << " = " << potega(a, n);
  8.   system("pause");
  9.   return 0;
  10. }

Zadania

Zadanie 1

Napisz rekurencyjną wersję algorytmu przedstawionego w artykule do wyliczania potęgi bez używania mnożenia. W algorytmie pamiętaj, aby uwzględnić, że a może należeć do liczb całkowitych. Wskazówka: napisz na początek algorytm potęgowania tylko dla a naturalnego.