Matura - programowanie w C++

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 a ≠ b, wykonuj:
    Jeśli a > b,
    to a ← a - b
    Inaczej b ← b - a

Schemat blokowy:

Lista kroków:

K01: Dopóki a ≠ b,
     wykonuj krok K02
K02:    Jeśli a > b,
        to a ← a - b
        Inaczej b ← b - 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:

18

30

18

12

b ← b - a

 6

12

a ← a - b

 6

 6

b ← b -a

 6

 6

NWD = 6

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

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:

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:   

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:

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:

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 b ≠ 0, wykonuj:
    r ← a mod b
    a ← b
    b ← r

Schemat blokowy:

Lista kroków:

K01: Dopóki b ≠ 0:
     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:

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

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:

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

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

Wprowadź 2 liczby : 24 18

NWW(24,18) = 72

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

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.