Euklido algoritmas

Euklido algoritmasalgoritmas 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ų.

Euklido algoritmas pavaizduotas skaičiais 1599 ir 650

Istorija redaguoti

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

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

Šaltiniai redaguoti

  1. Euklido algoritmas. Visuotinė lietuvių enciklopedija (tikrinta 2023-02-07).
  2. „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.