Algorytm Euklidesa

Algorytm Euklidesa

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

Euklides był greckim matematykiem, żył on ok. IV w p.n.e. Zajmował się głównie geometrią, metryką oraz stworzył pewien algorytm, który postaram się wytłumaczyć. 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

Wykonujemy te kroki, aż liczby m i n będą takie same.

Można przedstawić ten algorytm w postaci schematu blokowego

Mam nadzieje, że pomogłem. Dziękuje za uwage.