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;

}