2012-02-05 10:56:01 (2012-09-08 18:34:18)dark24

Algorytm Euklidesa

Algorytm Euklidesa służy do obliczania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych. Co ciekawe pomysłodawcą algorytmu był Eudoksos z Knidos. Euklides, którego imię nosi algorytm postanowił jedynie umieścić opis dzieła Eudoksosa w swojej lekturze pod tytułem "Elementy".

Sposób wykonywania algorytmu jest bardzo prosty. Spójrz na schemat zamieszczony poniżej. Mamy dwie liczby naturalne, których policzymy największy wspólny dzielnik. Są to 30 i 21.



Niech A będzie pierwszą z tych liczb (30), a B drugą (21). Z kolei A mod B jest resztą z dzielenia liczby A przez liczbę B. To próbujemy. 30 : 21 = 1 i reszta 9. Po wykonaniu każdego dzielenia liczbie A przepisuje się wartość liczby B z poprzedniego, a B otrzymuje wielkość reszty. Skoro B wynosiło 21 - to teraz A będzie równe 21. Nowe B wyniesie 9, bo taką wyliczyliśmy resztę z dzielenia. To jedziemy dalej. 21 : 9 = 2 i reszta 3. Przepisujemy jak poprzednio i wychodzi dzielenie 9 : 3 = 3 i reszta 0. Kolejnym krokiem byłoby działanie 3 : 0. Z matematyki wiemy jednak, że przez 0 się nie dzieli. To sygnał, że wykonaliśmy cały algorytm Euklidesa. NWD zostaje liczba B z kroku, w którym reszta z dzielenia wyniosła 0. Tutaj jest to 3.

Lista kroków

Dane wejściowe: dwie dowolne liczby A i B.
Dane wyjściowe: liczba NWD, będąca największym wspólnym dzielnikiem liczb A i B.

1. Wczytaj dwie liczby naturalne A i B.
2. Oblicz R będące resztą z dzielenia A przez B.
3. Jeśli R=0, zwróć NWD=B. W przeciwnym razie przejdź do kroku 4.
4. Zamień pozycję A liczbą B, a pozycję B liczbą R. Przejdź do kroku 2.

Schemat blokowy

Program iteracyjny w Pascalu

program algorytm_euklidesa;

uses crt;

function nwd(a, b:integer):integer;
var r:integer;
begin
  repeat
    r:=a mod b;
    if r<>0 then
    begin
      a:=b;
      b:=r;
    end;
  until
    r=0;
  nwd:=b;
end;

begin

  clrscr;
  writeln(nwd(30, 21));
  readln;

end.

Program rekurencyjny w Pascalu

program algorytm_euklidesa;

uses crt;

function nwd(a, b:integer):integer;
var r:integer;
begin
  r:=a mod b;
  if r<>0 then
    nwd:=nwd(b, r)
  else
    nwd:=b;
end;

begin

  clrscr;
  writeln(nwd(30, 21));
  readln;

end.

Program iteracyjny w C++

#include <iostream.h>
#include <conio.h>

int nwd(int a, int b)
{
  int r;
  while (r!=0)
    {
    r=a%b;
    if (r!=0)
      {
      a=b;
      b=r;
      }
    }
  return b;
}

int main()
{
  cout << nwd(30, 21) << endl;
  getch();
  return 0;
}

Przykłady na innych liczbach


ABA mod B
124244
2440

ABA mod B
2460
Zaloguj się, by dodawać komentarze.
Copyright kompinf.cba.pl by dark24 © 2010-2014