Kurs maturalny z języka angielskiego!
kurs-maturalny-jezyk-angielski

PROGRAMOWANIE I ALGORYTMY

Zajęcia maturalne z informatyki
Olimpiada Informatyczna Juniorów
    Prowadzący: Marcin Kasprowicz
  • właściciel serwisu algorytm.edu.pl
  • wrzesień 2024 — start zajęć
  • czytaj więcej

NWD - Algorytm Euklidesa


powrót

Algorytm Euklidesa służy do wyznaczania największego wspólnego dzielnika dwóch liczb całkowitych. Największy wspólny dzielnik dwóch liczb a i  b, to taka liczba, która dzieli te liczby bez reszty 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 zaznaczyć, że ten algorytm jest bardzo niewydajny. Gdy dobierzemy odpowiednio liczby, to 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 przejść pętli. Dla większych liczb algorytm może nie sprostać zadaniu.

Algorytm można testować na automatycznej sprawdzarce tutaj.

Rozwiązanie iteracyjne:

//algorytm.edu.pl
#include<iostream>
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;
   
    return 0;
}

Rozwiązanie rekurencyjnie:

//algorytm.edu.pl
#include<iostream>
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 ab. 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++:

//algorytm.edu.pl
#include<iostream>
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;

    return 0;
}

Rozwiązanie rekurencyjne:

//algorytm.edu.pl
#include<iostream>
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;

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