Matura z informatyki - rozwiązania zadań  

Algorytmy

Iteracyjna i rekurencyjna realizacja algorytmu Euklidesa

Algorytm Euklidesa służy do wyznaczania największego wspólnego dzielnika (NWD). Największy wspólny dzielnik dwóch liczb a i  b to taka liczba, która dzieli te liczby i jest ona możliwie największa. Można go zastosować do skracania ułamków lub wyznaczenia najmniejszej wspólnej wielokrotności NWW.

Euklides opracował prosty i efektywny algorytm wyznaczania. Dla danych dwóch liczb a i b polega on na tym, że od liczby większej odejmujemy liczbę mniejszą. Gdy liczby są równe otrzymamy NWD.

Przykład:

24 6 24-6 = 18

18 6 18-6 = 12

12 6 12-6 = 6

6 6 NWD = 6

Realizacja iteracyjna w C++

#include <iostream>

using namespace std;

int main()
{
    cout << "Program wyznacza najwiekszy wspolny dzielnik metoda iteracyjna." << endl;
    int a, b;
    cout << "Podaj a: ";
    cin >> a;
    cout << "Podaj b: ";
    cin >> b;
    cout << "NWD(" << a << "," << b << ") = ";
    while (a != b) {
        if (a < b)
            b -= a;
        else
            a -= b;
    }
    cout << a << endl;
    return 0;
}

NWD możemy też wyznaczyć następująco: załóżmy, że wyznaczamy NWD dwóch liczb naturalnych a i b. W każdym przejściu pętli wykonujemy dwie operacje

a=b

b=a mod b

Czynności te powtarzamy do momentu, gdy zmienna b osiągnie wartość zero. Zmienna a będzie przechowywać wtedy największy wspólny dzielnik liczb podanych na wejściu. Przeanalizujmy przykład:

NWD(12,18)=6:

12 | 18

18 | 12 mod 18 = 12

12 | 18 mod 12 = 6

6 | 12 mod 6 = 0

Realizacja rekurencyjna w C++

#include <iostream>
#include <cstdlib>

using namespace std;

int NWD(int a, int b)
{
    if (b != 0) {

        return NWD(b, a % b);
    }

    return a;
}

int main()
{
    int a, b;

    cout << "Podaj dwie liczby: ";
    cin >> a >> b;

    cout << "NWD(" << a << "," << b << ") = " << NWD(a, b) << endl;

    system("pause");
    return 0;
}
© 2017 MaturaInformatyka.pl || Kontakt: admin(malpa)maturainformatyka.pl

Search