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

Bartosz

Bartosz Stefanicki 15 grudnia 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.

Warto zobaczyć

Szukasz hostingu?

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

Data publikacji: 08.12.2010 r. Tagi: pascal, skrypty.

3 komentarzy


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

Używamy informacji zapisanych za pomocą cookies i podobnych technologii m.in. w celach reklamowych, statystycznych oraz dostosowania naszych serwisów do indywidualnych potrzeb użytkowników.