Algorytm Euklidesa, czyli największy wspólny dzielnik

Z pewnością każdy z nas miał do czynienia w szkole na lekcjach matematyki z pojęciem największego wspólnego dzielnika dwóch lub większej ilości liczb. W skrócie wyrażaliśmy to NWD (Największy Wspólny dzielnik). Algorytm Euklidesa został opisany przez greckiego matematyka Euklidesa już w 300 roku p.n.e. Okazuje się, iż istnieje efektywny algorytm liczenia NWD. Warto nadmienić, że jest to jeden z najstarszych algorytmów matematycznych. Bez względu na to, czy jesteś nowicjuszem w programowaniu czy doświadczonym programistą, zapraszam do odkrywania tego fascynującego zagadnienia!

Czym jest największy wspólny dzielnik?

Największy wspólny dzielnik (NWD) dwóch liczb całkowitych to największa liczba, która dzieli obie te liczby bez reszty. Innymi słowy, NWD jest to liczba, przez którą można podzielić obie liczby i otrzymać wynik całkowity, a nie ułamek.

Dlaczego warto poznać algorytm Euklidesa?

Algorytm Euklidesa to jeden z najbardziej efektywnych sposobów obliczania NWD dwóch liczb całkowitych. Jest to nie tylko ważne w kontekście matematyki, ale także w programowaniu. Zrozumienie tego algorytmu pozwoli Ci na rozwiązywanie różnych problemów związanych z liczbami całkowitymi w swoich programach.

Idea algorytmu Euklidesa

Algorytm Euklidesa jest algorytmem rekurencyjnym, chociaż w bardzo prosty sposób można go przekształcić do formy iteracyjnej. Jego idea jest następująca: mając do policzenia NWD(a,b) sprawdzamy, czy b=0. Jeśli tak jest to NWD(a,b)=a. W przeciwnym wypadku wywołujemy rekurencyjnie algorytm dla liczb b i (a mod b), czyli liczymy NWD(b, (a mod b)). Dla tych, którzy nie wiedzą – a mod b to reszta z dzielenia a przez b. Np. 7 mod 2=1, 15 mod 10=5, 8 mod 4=0.

Algorytm Euklidesa polega na powtarzaniu operacji dzielenia dwóch liczb, dopóki reszta z dzielenia nie będzie równa zero. Główną zasadą jest fakt, że NWD dwóch liczb nie zmienia się, gdy większa liczba jest zastępowana przez różnicę między nią a mniejszą liczbą.

Przykład

Rozważmy obliczenie NWD dla liczb 54 i 69. Ponieważ  liczba b, czyli 69 nie jest równe 0 więc wykonujemy algorytm dla b i (a mod b). W tym przypadku będą to liczby 69 i (54 mod 69), czyli 54. Proszę zauważyć, że liczby w tym przypadku zamieniły się miejscami. Tak więc liczby w algorytmie Euklidesa nie muszą być podane w odpowiedniej kolejności – zostaną one automatycznie odwrócone. Dobra, wróćmy do naszego przykładu. Teraz mamy liczby 69 i 54. Ponieważ 54 nie jest równe 0, to wykonujemy rekurencyjnie algorytm dla liczb 54 i (69 mod 54), czyli 15. Znowu druga liczba nie wynosi 0.

Wykonujemy dalej rekurencyjnie algorytm i otrzymujemy liczby 15 i (54 mod 15)=9. Liczba 9 nie jest zerem, więc wykonując dalej algorytm otrzymujemy liczby 9 i (15 mod 9), czyli 6. Jak poprzednio 6 nie jest równe 0, tak więc po kolejnym rekurencyjnym wywołaniu otrzymujemy 6 i (9 mod 6)=3. Jak wiadomo 3 to nie zero, więc wykonujemy algorytm dalej i otrzymujemy liczby 3 i (6 mod 3)=0. Ponieważ druga liczba jest równa 0 tak więc szukane NWD jest równe pierwszej liczbie, czyli 3.

Analizując po kolei wszystkie kroki naszego przykładu możemy napisać:

NWD(54,69)=NWD(69,54)=NWD(54,15)=NWD(15,9)=NWD(9,6)=NWD(6,3)=NWD(3,0)=3

Można udowodnić, że algorytm Euklidesa działa najgorzej dla liczb Fibonacciego.

NWD dla więcej niż dwóch liczb

Czasami spotykamy sytuację, gdy mamy policzyć największy wspólny dzielnik dla kilku liczb. Co wtedy robić? Najpierw liczymy NWD dla dwóch pierwszych liczb. Potem liczymy NWD dla otrzymanego wyniku i liczby trzeciej. Następnie NWD dla otrzymanego wyniku i czwartej liczby… itd.

Na przykład – jak policzyć NWD dla 84, 96, 32 i 24. Oto wynik:

NWD(84, 96, 32, 24) = NWD(84, NWD(96, NWD(32, 24))) = NWD(84, NWD(96, 8)) = NWD(84, 8) = 4

Przykładowy kod programu Algorytm Euklidesa (Największy Wspólny Dzielnik) w C++:

#include <iostream>
using namespace std;

int nwd(int a, int b) {
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int main() {
    int liczba1, liczba2;
    cout << "Podaj dwie liczby calkowite: ";
    cin >> liczba1 >> liczba2;
    cout << "Najwiekszy wspolny dzielnik to: " << nwd(liczba1, liczba2) << endl;
    return 0;
}

Wyjaśnienie kluczowych elementów kodu:

1. Funkcja nwd(int a, int b):
   • Jest to funkcja obliczająca największy wspólny dzielnik dwóch liczb całkowitych.
   • Wykorzystuje pętlę while do powtarzania operacji dzielenia, dopóki druga liczba nie będzie równa zero.
   • W każdej iteracji następuje zamiana miejscami liczb oraz obliczenie reszty z dzielenia, aby znaleźć nowe wartości.
2. Funkcja main():
   • Pobiera dwie liczby od użytkownika za pomocą funkcji cin.
   • Wywołuje funkcję nwd() i wyświetla obliczony największy wspólny dzielnik.

Podsumowanie: Algorytm Euklidesa

Algorytm Euklidesa to potężne narzędzie w arsenale każdego programisty. Dzięki niemu możemy szybko i skutecznie obliczać największy wspólny dzielnik dwóch liczb całkowitych. Zrozumienie działania tego algorytmu może być kluczowe dla rozwiązania wielu problemów w programowaniu, dlatego warto zgłębić jego tajniki już teraz!

Zachęcam do eksperymentowania z powyższym kodem i odkrywania różnych zastosowań algorytmu Euklidesa w swoich projektach. Powodzenia w nauce i programowaniu!

Sprawdź również nasze pozostałe poradniki dotyczące elementów programowania: przejdź