Algorytm Euklidesa

Postaram się wytłumaczyć zasadę działania algortymu Euklidesa. 

Zacznijmy od tego co to jest algorytm.

Algorytm to skończony ciąg jasno zdefiniowanych czynności koniecznych do wykonania pewnego rodzaju zadań, sposób postępowania prowadzący do rozwiązania problemu. Zadaniem algorytmu jest przeprowadzenie systemu z pewnego stanu początkowego do pożądanego stanu końcowego.

Zanim przejdziemy dalej powiem Wam kim był Euklides. Był on greckim matematykiem żyjącym w IV w. p.n.e. Stworzył m. in. "Elementy". Ma również w swojej kolekcji wiele osiągnić z dziedziny metryki i geometrii. Stworzył on też algorytm któremu jest poświęcony ten wpis. Pozwala on nam na wyznaczenie największego wspólnego dzielnika dwóch podanych liczb. Zapisany w pseudokodzie wygląda następująco.

1.Wpisz m, n;

2.m<>n?

3.Jeśli nie - NWD = m

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

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

Mam nadzieję, że udało mi się wytłumaczyć zasadę działania algorytmu Euklidesa :)