Algorytm Euklidesa

Algorytm 

Euklidesa 

jest 

algorytmem 

rekurencyjnym,  chociaż  w  bardzo  prosty  sposób 

można  go  przekształcić  do  formy  iteracyjnej.  Jego 

idea  jest  następująca:  mając  do  policzenia  NWD(a,b) 

sprawdzamy,  czy  b=0.  Jeśli  tak  jest  to  NWD(a,b)=a. 

W  przeciwnym  wypadku  wywołujemy  rekurencyjnie 

algorytm dla liczb b i (a mod b), czyli liczymy NWD(b, 

(a mod b)). 

Dla tych którzy nie wiedzą - a mod b to reszta z 

dzielenia a przez b. Np. 7 mod 2=1, 15 mod 10=5, 8 

mod 4=0. 

 

 

Przykład:

Rozważmy  obliczenie  NWD  dla  liczb  54  i  69. 

Ponieważ   liczba  b,  czyli  69  nie  jest  równe  0  więc 

wykonujemy  algorytm  dla  b  i  (a  mod  b).  W  tym 

przypadku będą to liczby 69 i (54 mod 69), czyli 54. 

Proszę  zauważyć,  że  liczby  w  tym  przypadku 

zamieniły się miejscami. Tak więc liczby w algorytmie 

Euklidesa  nie  muszą  być  podane  w  odpowiedniej 

kolejności - zostaną one automatycznie odwrócone. 

 

 

Przykład c.d.:

Ponieważ  54  nie  jest  równe  0,  to  wykonujemy 

rekurencyjnie  algorytm  dla  liczb  54  i  (69  mod  54), 

czyli  15.  Znowu  druga  liczba  nie  wynosi  0. 

Wykonujemy 

dalej 

rekurencyjnie 

algorytm 

i 

otrzymujemy liczby 15 i (54 mod 15)=9. Liczba 9 nie 

jest 

zerem, 

więc 

wykonując 

dalej 

algorytm 

otrzymujemy  liczby  9  i  (15  mod  9),  czyli  6.  Jak 

poprzednio  6  nie  jest  równe  0,  tak  więc  po  kolejnym 

rekurencyjnym  wywołaniu  otrzymujemy  6  i  (9  mod 

6)=3.  Jak  wiadomo  3  to  nie  zero,  więc  wykonujemy 

algorytm dalej i otrzymujemy liczby 3 i (6 mod 3)=0. 

Ponieważ druga liczba jest równa 0 tak więc szukane 

NWD jest równe pierwszej liczbie, czyli 3.

 

 

NWD dla więcej niż dwóch liczb

Czasami  spotykamy  sytuację,  gdy  mamy 

policzyć  największy  wspólny  dzielnik  dla  kilku  liczb. 

Co  wtedy  robić?  Po  prostu  liczymy  NWD  dla  dwóch 

pierwszych 

liczb. 

Potem 

liczymy 

NWD 

dla 

otrzymanego wyniku i liczby trzeciej. Następnie NWD 

dla otrzymanego wyniku i czwartej liczby itd.
Na przykład - jak policzyć NWD dla 84, 96, 32 i 24:
NWD(84, 96, 32, 24) = 
= NWD(84, NWD(96, NWD(32, 24))) = 
= NWD(84, NWD(96, 8)) = NWD(84, 8) = 4

 

 

Po odczytaniu wartości 
liczb a i b 
rozpoczynamy pętlę, 
która przerwie się, gdy 
w wyniku działania 
algorytmu liczba a 
będzie równa liczbie b. 
W takim przypadku 
dowolna z tych liczb 
jest największym 
wspólnym dzielnikiem 
pierwotnych wartości i 
wyprowadzamy ją. W 
przeciwnym wypadku 
jedna z liczb a lub b 
jest większa od drugiej. 
Odejmujemy więc 
liczbę mniejszą od 
większej i 
kontynuujemy pętlę, aż 
do zrównania wartości 
a i b.

 

 

NWD dla więcej niż dwóch liczb

#include <iostream> 
using namespace std;

unsigned long NWD(unsigned long a, unsigned long b)
{ 

while(a != b) 

if(a > b) 

a -= b; 

else b -= a; 
return(a);

} 
int main(void)
{ 

unsigned long a,b; 
cout << "Podaj a = "; 
cin >> a; 
cout << "\nPodaj b = "; 
cin >> b; 
cout << endl;
if((a <= 0) || (b <= 0))

cout << "Zle dane!\n"; 

Else

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

system("PAUSE"); return 0; 

}