Informacje o nowych artykułach oraz akcjach edukacyjnych prosto na Twojej skrzynce e-mail!

Algorytm Euklidesa, wyznaczanie NWD

Algorytm Euklidesa, służy do wyznaczania największego wspólnego dzielnika dowolnie wybranych dwóch liczb naturalnych. Został on stworzony w IV wieku p.n.e. przez Eudoksosa z Knidos.

Pozwala on na wyznaczenie NWD nie rozkładając liczb na czynniki pierwsze. Cały algorytm opiera się na poniższym założeniu:

algorytm-euklidesa

Zasada działania:

  1. Użytkownik musi wprowadzić dwie liczby naturalne, do zmiennych a oraz b;
  2. do zmiennej c przypisujemy resztę z dzielenia a przez b;
  3. zmienną a zastępujemy wartością zmiennej b, a do b przypisujemy wartość c;
  4. jeżeli b = 0 to NWD = a, jeżeli nie przejdź do punktu 2.

Przykładowy program wykorzystujący algorytm Euklidesa (napisany w języku Pascal):

program NWD;
USES crt;
VAR
    a,b,c:integer;
BEGIN
    clrscr;
    writeln('Podaj dwie liczby naturalne:');
    readln(a);
    repeat
         writeln('Druga liczba musi być różna od O:');
         readln(b);
    until b <> 0;

    {obliczamy NWD}

    repeat
         c := a mod b;
         a := b;
         b := c;
    until b = 0;
    
    {wyświetlamy wynik}
    writeln('NWD = ', a);
    repeat until keypressed;
end.

Spodobało się?

Jeśli tak, to zarejestruj się do newslettera aby otrzymywać informacje nowych artykułach oraz akcjach edukacyjnych. Gwarantuję 100% satysfakcji i żadnego spamowania!

,

Dodaj komentarz

Odpowiedz

Twój adres e-mail nie zostanie opublikowany.

Pin It on Pinterest