Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

czytaj więcej

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 {tex}a{/tex} i  {tex}b{/tex} 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 {tex}12{/tex} i  {tex}18{/tex}. Wiadomo, że {tex}NWD(12,18)=6{/tex}.

euklides

Dla liczb {tex}28{/tex} i {tex}24\ NWD(28, 24) = 4{/tex}:

euklides

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

euklides

W tym przypadku najmniejszy wspólny dzielnik jest równy jeden. Żeby to stwierdzić, należy wykonać {tex}9999{/tex} 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 {tex}a > 0, b > 0{/tex}.

 

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 {tex}a{/tex} i {tex}b{/tex}. W każdym przejściu pętli wykonujemy dwie operacje

{tex}a = b{/tex}

{tex}b = a\ mod\ b{/tex}

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

Policzmy {tex}NWD(12,18) = 6{/tex}:

euklides

Dla liczb {tex}28{/tex} i {tex}24{/tex}:

euklides

Natomiast dla liczb {tex}10000{/tex} i {tex}1{/tex}:

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 {tex}NWD{/tex} 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;
}