Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek
Zmodyfikowano 21.12.2022

©2023 mgr Jerzy Wałaszek
I LO w Tarnowie

Materiały do matury z informatyki

Algorytm Euklidesa

SPIS TREŚCI

Euklides

Euklides był sławnym matematykiem i geometrą greckim, który działał w Aleksandrii, mieście założonym przez Aleksandra III Macedońskiego. Miasto to było w starożytności siedzibą nauki. Euklides napisał wspaniałe dzieło "Elementy", które nie straciło na wartości do dzisiaj. W szkole uczyłeś się geometrii w oparciu o to dzieło. Więcej na temat tego wspaniałego uczonego znajdziesz w Wikipedii.
Na początek:  podrozdziału   strony 

Algorytm Euklidesa

Wspólnym dzielnikiem dwóch liczb całkowitych a i b jest dodatnia liczba całkowita c, jeśli dzieli obie liczby a i b bez reszty. Na przykład dla liczb 18 i 24 ich wspólnymi dzielnikami są 1, 2, 3, 4 i 6 (liczby ujemne pomijamy).  Największym wspólnym dzielnikiem  jest tu liczba 6.

Sposób znajdowania największego wspólnego dzielnika opisał Euklides i sposób ten nosi nazwę algorytmu Euklidesa. Uczony grecki rozwiązał problem geometrycznie. Poszukiwał tzw. wspólnej miary dla dwóch odcinków. Co to jest wspólna miara? To najdłuższy odcinek, który można jednocześnie odłożyć w każdym z dwóch odcinków:

 

Euklides zauważył, iż jeśli dwa odcinki posiadają wspólną miarę, to również ich różnica posiada tę miarę:

Zatem, aby znaleźć tę miarę, należy od dłuższego odcinka odejmować mniejszy, aż oba odcinki będą równe. Wtedy, to co pozostanie, jest ich wspólną miarą. Przechodząc na liczby, algorytm ten formułujemy następująco:

Dane wejściowe: dwie dodatnie liczby całkowite a i b.
Dane wyjściowe: a = NWD liczb a i b.

Opis słowny:

Dopóki liczby a i b są różne, od większej liczby odejmujemy mniejszą. Gdy liczby się zrównają, to są równe NWD.

Pseudokod:

Dopóki ab, wykonuj:
    Jeśli a > b, to aa - b
    Inaczej bb - a

Schemat blokowy:

Lista kroków:

K01: Dopóki ab, wykonuj krok K02
K02:    Jeśli a > b, to aa - b
        Inaczej bb - a
K03: Zakończ

Program w języku C++:

// Algorytm Euklidesa
//-------------------

#include <iostream>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    unsigned long long a, b;

    cout << "Znajdowanie NWD" << endl
         << "---------------" << endl << endl
         << "Wpisz 2 liczby : ";

    cin >> a >> b;

    cout << endl;

    while(a != b)
        if(a > b) a -= b;
        else      b -= a;

    cout << "NWD = " << a << endl << endl;

    return 0;
}

Zobaczmy działanie tego algorytmu na przykładzie liczbowym:

a b operacja
18 30  
18 12 b ← b - a
6 12 a ← a - b
6 6 b ← b -a
6 6 NWD = 6

Do zapamiętania:

Na początek:  podrozdziału   strony 

Ulepszony algorytm Euklidesa

Przyglądnijmy się bliżej naszemu algorytmowi Euklidesa. W algorytmie występuje pętla, która od większej liczby odejmuje większą dotąd, aż odejmowanie nie będzie możliwe (mówimy tutaj o liczbach naturalnych, które nie mogą być ujemne). Na przykład, jeśli a = 23, b = 5, to pętla wewnętrzna wykona następujące odejmowania:

(1) a ← 23 - 5 = 18
(2) a ← 18 - 5 = 13
(3) a ← 13 - 5 =   8
(4) a ←   8 - 5 =   3

Zwróć uwagę, iż pętla wykonuje tu tyle obiegów, ile wynosi wynik dzielenia całkowitoliczbowego liczby większej przez mniejszą, a w liczba większa otrzymuje na końcu wartość reszty z tego dzielenia:

23 : 5 = 4 i reszta 3

Jeśli liczby różnią się bardzo, to pętla wykonuje dużo obiegów. Uruchom poprzedni program i wpisz liczby 2 i 40000000000. Zauważ, iż wykonanie 20 miliardów odejmowań zajmuje komputerowi pewną chwilę czasu (zależnie od szybkości mikroprocesora).

Znajdowanie NWD
---------------

Wpisz 2 liczby : 2 40000000000

NWD = 2


Process returned 0 (0x0) execution time : 55.005 s

Zamiast wykonywać odejmowania, możemy wykorzystać operację wyliczania reszty z dzielenia, którą i tak odejmowania wyliczają. Następne spostrzeżenie dotyczy reszt z dzielenia: reszta jest zawsze mniejsza od dzielnika:

5 : 3 = 1 i reszta 2; 2 < 3

Zatem większa liczba, po umieszczeniu w niej reszty z dzielenia stanie się liczbą mniejszą i teraz ona powinna być dzielnikiem. Aby nad tym zapanować, użyjmy dodatkowej zmiennej r, w której będziemy przechowywać chwilowo resztę z dzielenia. Plan jest następujący:

Umawiamy się, że w zmiennej a będzie zawsze większa liczba, a w b mniejsza, co zwolni nas od sprawdzania warunków. Obliczamy resztę z dzielenia a (liczby większej) przez b (liczbę mniejszą) i wynik zapamiętujemy w zmiennej r. Teraz większą liczbą stanie się b, przenosimy zatem b do a. Obliczoną wcześniej resztę umieszczamy w b (w liczbie mniejszej) i obliczenia powtarzamy dotąd, aż liczba b stanie się równa 0 (bo już dalej nie można dzielić). Wtedy NWD znajduje się w a (ostatnia niezerowa reszta).

Pętla przyjmie następujący wygląd:

Dopóki b ≠ 0, wykonuj:
    rreszta z a : b
    ab
    br

Zobaczmy jak to działa na przykładzie liczb 32 i 12:   

a b r  
32 12 8  
12 8 4  
8 4 0  
4 0   NWD = 4

Zwróć uwagę, iż w trakcie działania tego algorytmu zawartości zmiennych przesuwają się z b do a, z r do b. Gdy b osiągnie 0, algorytm kończy działanie.

Założyliśmy, że a jest liczbą większą, a b jest liczbą mniejszą. A co się stanie, gdy będą równe? Zobaczmy:

a b r  
12 12 0  
12 0   NWD = 12

Algorytm zakończy pracę po jednym obiegu.

A co będzie, jeśli liczby są w złej kolejności (tzn. większa - mniejsza)? Sprawdźmy:

a b r  
12 32 12  
32 12 8  
12 8 4  
8 4 0  
12 0   NWD = 12

Co się okazało? Jeśli dane są w złej kolejności, to pierwszy obieg je uporządkuje (dlaczego?) i algorytm w efekcie wykona o jeden obieg więcej niż dla danych uporządkowanych. To bardzo dobra cecha algorytmu - odporność na niekorzystną konfigurację danych wejściowych.

Dane wejściowe: dwie nieujemne liczby całkowite a i b.
Dane wyjściowe: a = NWD liczb a i b.

Opis słowny:

Dopóki b jest różne od zera, zastąp a liczbą b, a b zastąp resztą z dzielenia pierwotnego a przez b.

Pseudokod:

Dopóki b0, wykonuj:
    ra mod b
    ab
    br

Schemat blokowy:

Lista kroków:

K01: Dopóki b0, wykonuj kroki K02...K04
K02:    r ← a mod b
K03:    a  b
K04:    b  r
K05: Zakończ

Program w języku C++:

// Algorytm Euklidesa
//-------------------

#include <iostream>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    unsigned long long a, b, r;

    cout << "Znajdowanie NWD" << endl
         << "---------------" << endl << endl
         << "Wpisz 2 liczby : ";

    cin >> a >> b;

    cout << endl;

    while(b) // dopóki b różne od zera!
    {
        r = a % b;
        a = b;
        b = r;
    }
  
    cout << "NWD = " << a << endl << endl;

    return 0;
}

Uruchom ten program z danymi, które poprzednio spowodowały długi czas obliczeń:

Znajdowanie NWD
---------------

Wpisz 2 liczby : 2 40000000000

NWD = 2


Process returned 0 (0x0) execution time : 11.352 s

Wynik otrzymujemy praktycznie natychmiast, czas pokazany powyżej dotyczy czasu wprowadzania danych z klawiatury.

Ta postać algorytmu Euklidesa jest preferowana w informatyce.

Do zapamiętania:

Na początek:  podrozdziału   strony 

Skracanie ułamków

Algorytm Euklidesa ma wiele zastosowań praktycznych. Jednym z nich jest skracanie ułamka do postaci prostszej, np:

Aby skrócić ułamek, znajdujemy NWD licznika i mianownika, po czym dzielimy licznik i mianownik przez NWD.

Dane wejściowe: lk – licznik ułamka, mk – mianownik ułamka, lk, mk – liczby nieujemne, mk różne od 0.
Dane wyjściowe: lk – licznik ułamka skróconego, mk – mianownik ułamka skróconego

Lista kroków:

K01: a ← lk
K02: b ← mk
K03: Algorytm Euklidesa, a = NWD
K04: lk ← lk : a
K05: mk ← mk : a
K06: Zakończ

Program w języku C++:

// Skracanie ułamka
//-----------------

#include <iostream>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    unsigned a, b, r, lk,mk;

    cout << "Skracanie ułamka" << endl
         << "----------------" << endl << endl;

    cout << "Licznik   : "; cin >> lk;
    cout << "Mianownik : "; cin >> mk;
    cout << endl;

    a = lk; b = mk;

    // Algorytm Euklidesa
    //*******************

    while(b)
    {
        r = a % b;
        a = b;
        b = r;
    }

    //*******************

    lk /= a;
    mk /= a;

    cout << lk << endl
         << "---" << endl
         << mk << endl << endl;

    return 0;
}
Skracanie ułamka
----------------

Licznik   : 12
Mianownik : 8

3
---
2
Na początek:  podrozdziału   strony 

Najmniejsza Wspólna Wielokrotność, NWW

Wielokrotność liczby powstaje poprzez przemnożenie jej przez liczbę naturalną. Oto kilka kolejnych wielokrotności liczby 6:
6 × 1 = 6
6 × 2 = 12
6 × 3 = 18
...

Wspólną wielokrotnością dwóch liczb jest taka liczba, która stanowi wielokrotność każdej z nich, tzn. jest podzielna przez każdą z liczb. Np. wspólnymi wielokrotnościami liczb 6 i 9 są:

6 × 3 = 18 = 9 × 2
6 × 6 = 36 = 9 × 4
6 × 9 = 54 = 9 × 6
...

Najmniejszą wspólną wielokrotnością NWW dwóch liczb jest najmniejsza z liczb podzielnych przez każdą z nich. W powyższym przypadku NWW(6,9) jest równe 18, bo 18 dzieli się przez 6 i dzieli się przez 9 i jest najmniejszą z liczb o takiej własności.

Aby znaleźć NWW liczb a i b, dzielimy ich iloczyn przez ich NWD. Na przykład dla liczb 6 i 9, NWD(6,9) = 3, zatem:

Dane wejściowe: dwie dodatnie liczby całkowite a, b
Dane wyjściowe: nww - najmniejsza wspólna wielokrotność liczb a i b

Lista kroków:

K1: nww ← a · b
K2: Algorytm Euklidesa, a = NWD
K3: nww ← nww : a
K4: Zakończ

Program w języku C++:

// Najmniejsza Wspólna Wielokrotność
//----------------------------------

#include <iostream>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    unsigned a, b, r, nww;

    cout << "Najmniejsza Wspólna Wielokrotność" << endl
         << "---------------------------------" << endl << endl
         << "Wprowadź 2 liczby : ";
    cin >> a >> b;
    cout << endl;

    cout << "NWW(" << a << "," << b << ") = ";

    nww = a * b;

    // Algorytm Euklidesa
    //*******************

    while(b)
    {
        r = a % b;
        a = b;
        b = r;
    }

    //*******************

    nww /= a;

    cout << nww << endl << endl;

    return 0;
}
Najmniejsza Wspólna Wielokrotność
---------------------------------

Wprowadź 2 liczby : 24 18

NWW(24,18) = 72
Na początek:  podrozdziału   strony 

Sprawdzanie względnej pierwszości

Dwie liczby a i b są względnie pierwsze, gdy żadna z liczb mniejszych oprócz 1 nie dzieli ich jednocześnie, tzn. nie posiadają wspólnych dzielników. Sytuacja taka wystąpi, gdy NWD(a,b) = 1.

Dane wejściowe: dwie dodatnie liczby całkowite a, b
Dane wyjściowe: informacja, czy liczby a i b są, czy nie są względnie pierwsze

Lista kroków:

K1: Algorytm Euklidesa, a = NWD
K2: Jeśli a ≠ 1, to pisz "nie są względnie pierwsze"
    Inaczej pisz "są względnie pierwsze"
K4: Zakończ

Program w języku C++:

// Pierwszość względna
//--------------------

#include <iostream>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    unsigned a, b, r;

    cout << "Badanie względnej pierwszości" << endl
         << "-----------------------------" << endl << endl
         << "Wprowadź 2 liczby : ";
    cin >> a >> b;
    cout << endl;

    // Algorytm Euklidesa
    //*******************

    while(b)
    {
        r = a % b;
        a = b;
        b = r;
    }

    //*******************

    cout << "Liczby";

    if(a != 1) cout << " nie";

    cout << " są względnie pierwsze" << endl << endl;

    return 0;
}
Badanie względnej pierwszości
-----------------------------

Wprowadź 2 liczby : 12 15

Liczby nie są względnie pierwsze
Badanie względnej pierwszości
-----------------------------

Wprowadź 2 liczby : 12 25

Liczby są względnie pierwsze

Istnieje więcej zastosowań algorytmu Euklidesa, np. w kryptografii. Część z nich omówimy w dalszej części kursu.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2023 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.