Euklido algoritmas
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e1/Euclids-algorithm-example-1599-650.gif/220px-Euclids-algorithm-example-1599-650.gif)
Euklido algoritmas – algoritmas surasti dviejų sveikųjų skaičių didžiausią bendrąjį daliklį (DBD), remiantis padalijimu iš liekanos. Algoritmas principas: pirmiausia didžiausias skaičius padalijamas su liekana iš mažiausio, o po to kiekviename tolesniame žingsnyje ankstesnės operacijos daliklis dalijamas iš gautos liekanos. Algoritmo rezultatas yra paskutinė gauta nenulinė liekana. Tai yra vienas iš seniausių žinomų algoritmų.
Istorija
[redaguoti | redaguoti vikitekstą]Senovės graikų matematikas Euklidas, iš kurio vardo kilo šis algoritmas, iš pradžių suformulavo dviejų skaičių didžiausio bendrojo daliklio radimą geometriškai – kaip didžiausią bendrą dviejų atkarpų matą. Tokiu atveju iš ilgesnės atkarpos buvo atimama trumpiausia dalis, tada iš trumpesnės atkarpos atimama likusioji dalis ir taip toliau.
Tokia forma algoritmas pasirodė Euklido „Pradmenyse“ apie 300 pr. m. e.[1] Nors taip pat buvo žinomas net 200 metų anksčiau. Pavyzdžiui, Aristotelis užsiminė apie šį algoritmą savo knygoje „Temos“ (gr. Τοπικων, Topikon) apie 330 pr. m. e.[2]
Apibrėžimas
[redaguoti | redaguoti vikitekstą]Algoritmas dviejų skaičių ir DBD rasti užrašomas taip:
- Jeigu yra nulis, tuomet DBD yra
- Kitaip,
- ←
- ← dalybos iš liekana
- Kartojame nuo pirmo žingsnio
Šio algoritmo realizavimas Pascal programavimo kalba:
while (a > 0) and (b > 0) do if a > b then a := a mod b else b := b mod a; dbd := a + b;
C/C++ kalba:
while (abs(a) && abs(b)) if (abs(a) > abs(b)) a %= b; else b %= a; dbd = a + b;
Taip pat skaitykite
[redaguoti | redaguoti vikitekstą]Šaltiniai
[redaguoti | redaguoti vikitekstą]- ↑ Euklido algoritmas. Visuotinė lietuvių enciklopedija (tikrinta 2023-02-07).
- ↑ „Pirmasis algoritmas – Euklido algoritmas didžiausiam bendrajam dalikliui rasti — Informatikos olimpiados: algoritmai ir taikymo pavyzdžiai“. inf-knyga.nmakademija.lt. Nuoroda tikrinta 2023-02-07.