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.
Kategorie: Pozostałe. Tagi: #pascal, #skrypty. Źródło obrazków: Pixabay, Font awesome.
Zobacz także
3 komentarzy
Autor
Nowy
Odpowiedz
Autor
Nowy
Odpowiedz
Pokaż więcej komentarzy
