Algorytm Euklidesa - znajdowanie największego wspólnego dzielnika
Stronę tą wyświetlono już: 19929 razy
Algorytm Euklidesa stanowi wstęp do utworzenia jego rozszerzonej wersji ważnej przy szyfrowaniu danych szyfrem RSA z kluczem prywatnym i publicznym. Podstawowy model tego algorytmu operuje na różnicach dwóch liczb całkowitych a i b tak długo, aż te liczby osiągną taką samą wartość. Ważne jest aby odejmować od największej mniejszą liczbę.
O wiele lepszym i efektywniejszym rozwiązaniem jest użycie algorytmu wykorzystującego reszty z dzielenia liczb a i b. Po każdym kroku liczba a przyjmuje wartość dzielnika, czyli liczby b, która w kolejnych krokach przyjmuje wartość a % b (czyli reszty z dzielenia a przez b). Oto przykładowy kod napisany w Pythonie pokazujący obie te metody wyznaczania największego wspólnego dzielnika dwóch liczb a i b:
Przykład działania powyższego programu dla liczb a = 121 i b = 21:
Podaj pierwszą liczbę całkowitą dodatnią: 121 Podaj drugą liczbę całkowitą dodatnią: 21 Metoda z wydajniejsza: a = 121; b = 21 a = 21; b = 16 a = 16; b = 5 a = 5; b = 1 a = 1; b = 0 Największy wspólny dzielnik liczb 121 i 21 jest równy: 1 Obliczanie NWD metodą klasyczną: a = 121; b = 21 a = 100; b = 21 a = 79; b = 21 a = 58; b = 21 a = 37; b = 21 a = 21; b = 16 a = 16; b = 5 a = 11; b = 5 a = 6; b = 5 a = 5; b = 1 a = 4; b = 1 a = 3; b = 1 a = 2; b = 1 a = 1; b = 1 Największy wspólny dzielnik liczb 121 i 21 jest równy: 1 Aby kontynuować, naciśnij dowolny klawisz . . .
Jak widać liczba operacji koniecznych do wyznaczenia wspólnego dzielnika liczb a i b w przypadku klasycznego algorytmu Euklidesa wymaga wykonania znacznie większej liczby operacji niż w przypadku algorytmu wykorzystującego resztę z dzielenia.
Tytuł:
Algorytmy. Ilustrowany przewodnik
Autor:
Aditya Bhargava
Tytuł:
Algorytmy. Struktury danych i złożoność obliczeniowa
Autor:
Feliks Kurp
Tytuł:
Algorytmy w Pythonie. Techniki programowania dla praktyków
Autor:
Piotr Wróblewski
Tytuł:
Matematyka dyskretna dla praktyków. Algorytmy i uczenie maszynowe w Pythonie
Autor:
Ryan T. White, Archana Tikayat Ray
Tytuł:
Algorytmy kryptograficzne w Pythonie. Wprowadzenie
Autor:
Shannon W. Bray
Tytuł:
Algorytmy sztucznej inteligencji. Ilustrowany przewodnik
Autor:
Rishal Hurbans
Tytuł:
Algorytmy bez tajemnic
Autor:
Thomas H. Cormen
Tytuł:
Algorytmy dla bystrzaków
Autor:
John Paul Mueller, Luca Massaron
Tytuł:
Algorytmy Data Science. Siedmiodniowy przewodnik. Wydanie II
Autor:
David Natingga
Tytuł:
Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji
Autor:
Giuseppe Bonaccorso