NWD - Algorytm Euklidesa

powrót

Algorytm Euklidesa służy do wyznaczania największego wspólnego dzielnika. 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.

Artykuł opisuje dwie postacie algorytmu: nieoptymalną i optymalną.

Niezoptymalizowany algorytm Euklidesa

Sposób rozwiązania jest następujący.

Wybieramy większą z dwóch liczb i zamieniamy ją na różnicę większej i mniejszej. Czynność tą powtarzamy do momentu uzyskania dwóch takich samych wartości.

Prześledźmy przykład dla liczb $$12$$ i  $$18$$. Wiadomo, że $$NWD(12,18)=6$$.

euklides

Dla liczb $$28$$ i $$24\ NWD(28, 24) = 4$$:

euklides

Warto zauważyć, że ten algorytm jest bardzo niewydajny. Gdy dobierzemy odpowiednio liczby, ilość operacji znacznie się zwiększy. Przeanalizujmy takie liczby jak $$1$$ i $$10000$$:

euklides

W tym przypadku najmniejszy wspólny dzielnik jest równy jeden. Żeby to stwierdzić, należy wykonać $$9999$$ kroków pętli. Dla większych liczb algorytm może nie sprostać zadaniu.

Algorytm można testować na automatycznej sprawdzarce tutaj.

Rozwiązanie iteracyjne:

#include<iostream>
#include<cstdlib>
using namespace std;

int NWD(int a, int b)
{
    while(a!=b)
       if(a>b)
           a-=b; //lub a = a - b;
       else
           b-=a; //lub b = b-a
    return a; // lub b - obie zmienne przechowują wynik NWD(a,b)
}

int main()
{
    int a, b;
    
    cout<<"Podaj dwie liczby: ";
    cin>>a>>b;
    
    cout<<"NWD("<<a<<","<<b<<") = "<<NWD(a,b)<<endl;
     
    system("pause");
    return 0;
}

 

Rozwiązanie rekurencyjnie:

#include<iostream>
#include<cstdlib>
using namespace std;

int NWD(int a, int b)
{
   if(a!=b)
     return NWD(a>b?a-b:a,b>a?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;
}

 

Zakładamy, że liczby $$a > 0, b > 0$$.

 

Uwaga! NWD(a,0)=a, gdzie a>0, NWD(0, b)=b, gdzie b>0. Ten przypadek nie jest rozpatrzony w algorytmie.

 

Zoptymalizowany algorytm Euklidesa

W przypadku optymalnego rozwiązania NWD postępujemy 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łady:

Policzmy $$NWD(12,18) = 6$$:

euklides

Dla liczb $$28$$ i $$24$$:

euklides

Natomiast dla liczb $$10000$$ i $$1$$:

euklides

Rozwiązanie iteracyjne w C++:

#include<iostream>
#include<cstdlib>
using namespace std;
 
int NWD(int a, int b)
{
    int pom;
    
	while(b!=0)
    {
		pom = b;
		b = a%b;
		a = pom;	
	}
	
    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;
}

 

Rozwiązanie rekurencyjne:

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

 

Warto zauważyć, że algorytm poprawnie wyznacza $$NWD$$ w przypadku, gdy jedna z liczb jest równa zero.

Pamiętaj, że NWD dwóch zer nie istnieje!!!

 

Ciekawe rozwiązanie

int euklides(int a, int b)
{
	while(b)
		swap(a %= b, b);
	return a;
}