Euklido algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Jump to navigation Jump to search

Euklido algoritmasalgoritmas, kurio autorystė prisikiriama Euklidui, skirtas surasti dviejų skaičių didžiausią bendrą daliklį (DBD).

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ą]