Implementacja algorytmu szybkiego potęgowania
Implementacja algorytmu szybkiego potęgowania (wersja rekurencyjna)
To klasyczna implementacja „dziel i zwyciężaj”:
Linia 1. int szybkie podkreślnik potegowanie podkreślnik rek otwórz nawias okrągły int podstawa przecinek int wykladnik zamknij nawias okrągły otwórz nawias klamrowy.
Linia 2. if otwórz nawias okrągły wykladnik znak równości znak równości 0 zamknij nawias okrągły return 1 średnik.
Linia 3. if otwórz nawias okrągły wykladnik znak równości znak równości 1 zamknij nawias okrągły return podstawa średnik.
Linia 5. int polowa znak równości szybkie podkreślnik potegowanie podkreślnik rek otwórz nawias okrągły podstawa przecinek wykladnik prawy ukośnik 2 zamknij nawias okrągły średnik.
Linia 7. if otwórz nawias okrągły wykladnik procent 2 znak równości znak równości 0 zamknij nawias okrągły.
Linia 8. return polowa asterysk polowa średnik.
Linia 9. else.
Linia 10. return polowa asterysk polowa asterysk podstawa średnik.
Linia 11. zamknij nawias klamrowy.
Jak to działa?
Algorytm wykorzystuje fakt, że:
jeśli jest parzyste, to
jeśli jest nieparzyste, to
Dzięki temu zamiast mnożyć a n razy, wykonujemy tylko około kroków.
Wykładnik dzielony jest przez 2 w każdym kroku, dlatego to podejście nazywamy szybkim potęgowaniem.
Implementacja algorytmu szybkiego potęgowania (wersja iteracyjna)
Linia 1. int szybkie podkreślnik potegowanie otwórz nawias okrągły int podstawa przecinek int wykladnik zamknij nawias okrągły otwórz nawias klamrowy.
Linia 2. int wynik znak równości 1 średnik.
Linia 4. while otwórz nawias okrągły wykladnik zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy.
Linia 6. prawy ukośnik prawy ukośnik jeśli wykładnik jest nieparzysty.
Linia 7. if otwórz nawias okrągły wykladnik procent 2 znak równości znak równości 1 zamknij nawias okrągły otwórz nawias klamrowy.
Linia 8. wynik znak równości wynik asterysk podstawa średnik prawy ukośnik prawy ukośnik lub wynik asterysk znak równości podstawa.
Linia 9. zamknij nawias klamrowy.
Linia 11. podstawa znak równości podstawa asterysk podstawa średnik prawy ukośnik prawy ukośnik lub podstawa asterysk znak równości podstawa.
Linia 12. wykladnik znak równości wykladnik prawy ukośnik 2 średnik prawy ukośnik prawy ukośnik lub wykladnik prawy ukośnik znak równości 2.
Linia 13. zamknij nawias klamrowy.
Linia 15. return wynik średnik.
Linia 16. zamknij nawias klamrowy.
Podsumujmy:
Jeśli wykładnik jest nieparzysty, mnożymy wynik przez podstawę.
Następnie podnosimy podstawę do kwadratu.
Dzielimy wykładnik przez 2 (całkowicie).
Powtarzamy te kroki, dopóki wykładnik nie stanie się równy zero.
Gdywykładnik osiągnie zero, aktualna wartość
wynikjest obliczoną potęgą.