Euklido algoritmas

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 
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. Nors taip pat buvo žinomas net 200 metų anksčiau. Pavyzdžiui, Aristotelis užsiminė apie šį algoritmą savo knygoje „Temos“ (, Topikon) apie 330 pr. m. e.

 Apibrėžimas 
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;

PHP kalba:

  while ($a && $b) [$a, $b] = [$b % $a, $a];
  $dbd = abs($a + $b);

Javascript kalba:

  while (a && b) [a, b] = [b % a, a];
  dbd = Math.abs(a + b);

 Taip pat skaitykite 
 Išplėstinis Euklido algoritmas

 Šaltiniai 

Kategorija:Algoritmai
Kategorija:Skaičių teorija