Algorytm Euklidesa

Wytłumaczę tutaj zasadę działania algorytmu Euklidesa.

Zacznę od samego Euklidesa jako osoby. Otóż był on greckim matematykiem (żył ok IV w. p.n.e). Ma na swoim koncie wiele osiągnięć w dziedzinach geometrii, metryki oraz jest twórcą pewnego algorytmu na którym się dzisiaj skupię.

Algorytm ten pozwala nam na wyznaczenie największego wspólnego dzielnika dwóch podanych liczb. Zapiszmy najpierw działanie algorytmu w pseudokodzie:

1.Wpisz m, n;

2.m<>n?

3.Jeśli nie - NWD = m

3.Jeśli tak:

   m>n?

   Jeśli nie

      n=n-m 

      Wróć do punktu 3.

   Jeśli tak

      m=m-n

      Wróć do punktu 3

Program wykonuje się, aż liczby m i n będą równe. Przeanalizujmy algorytm jeszcze raz, tym razem na przykładzie liczb 138 i 108.

1. m=138, n=108

2.138<>108

3.138>108

   m=138-108=30

3.30<108

   n=108-30=78

3.30<78

   n=78-30=48

3.30<48

   n=48-30=18

3.30>18

   m=30-18=12

3. 12<18

   n=18-12=6

3.12>6

   m=12-6=6

m=n=6

NWD(130, 108) = 6

Zasadę działania algorytmu euklidesa można przedstawić również za pomocą schematu blokowego

Mam nadzieję, że dobrze wytłumaczyłem zasadę działania algorytmu Euklidesa i zapamiętacie go, bo a nuż się kiedyś przyda. Dziękuję za przeczytanie mojego bloga.