Algorytm Euklidesa - obliczanie największego wspólnego dzielnika (NWD)

Algorytm Euklidesa - obliczanie największego wspólnego dzielnika (NWD)

Pozostałe Data aktualizacji: 15.12.2019

Algorytm Euklidesa - obliczanie największego wspólnego dzielnika (NWD)

Napisz funkcję, która będzie wykorzystywała algorytm Euklidesa do znajdowania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych.

Algorytm Euklidesa nie wymaga rozkładania liczb na czynniki pierwsze. Wykorzystywana jest zależność: NWD dwóch liczb (a, b) jest równy a gdy b=0, lub jest równy NWD(b, a mod b) gdy b>=1.

function nwd(m,n:word):word;
var r:word;

begin
while m>0 do
begin
r:=n mod m;
n:=m;
m:=r;
end;

nwd:=n;
end;

Powyżej jest zamieszczony kod funkcji algorytmu Euklidesa, teraz zobaczmy jak ją wywołać - czyli użycie w praktyce:

begin
writeln('Podaj m');
readln(m);

writeln('Podaj n');
readln(n);

writeln(nwd(m,n));
readln;
end.
dhosting

Autor: Bartosz Stefanicki. Data publikacji: 08.12.2010. Tagi: pascal, skrypty.

Komentarze