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