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

Bartosz

Bartosz Stefanicki Poniedziałek, 22.04.2024

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.

Warto zobaczyć

Szukasz hostingu?

Jest dużo firm oferujących hosting, ale którą wybrać? Przedstawiamy zestawienie najciekawszych propozycji i ranking hostingów (Czerwiec 2024).

Data publikacji: Środa, 8.12.2010. Tagi: pascal, skrypty. Źródło obrazka Pixabay, Font awesome.

3 komentarzy


© 2005-2024 itporady.pl. Wszystkie prawa zastrzeżone.

Strona korzysta z plików cookies w celu realizacji usług i zgodnie z Polityką prywatności. Możesz określić warunki przechowywania lub dostępu do plików cookies w Twojej przeglądarce.