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

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

Data aktualizacji: 15.12.2019

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.

Ranking hostingów

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

1 komentarz

Ostatnie komentarze

Statystyki

  • 178

    Liczba porad
  • 1 774

    Liczba komentarzy
  • 6

    Narzędzi online

© 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.