Materiały do matury z informatyki

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:

Dopóki a ≠ b, wykonuj:
    Jeśli a > b, to a ← a - b
    Inaczej b ← b - a

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

// 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:

Do zapamiętania:

• Co to jest Największy Wspólny Dzielnik NWD (ang. Greatest Common Divisor GCD).
• Podstawowy algorytm Euklidesa.
• Program dla algorytmu Euklidesa.

(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 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).

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:

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

Dopóki b ≠ 0, wykonuj:
    r ← reszta z a : b
    a ← b
    b ← r

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

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:

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:

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.

Dopóki b ≠ 0, wykonuj:
    r ← a mod b
    a ← b
    b ← r

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

// 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ń:

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:

• Algorytm Euklidesa wykorzystujący reszty z dzielenia.
• Program dla algorytmu Euklidesa.

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

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

// 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;
}

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ą:

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:

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

// 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;
}

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

// 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;
}

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