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.