Euklido algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

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

Algoritmas dviejų skaičių A ir B DBD rasti užrašomas taip:

  • Jeigu B yra nulis, tuomet DBD yra A
  • Kitaip,
  • AB
  • BA dalybos iš B 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[taisyti | redaguoti kodą]