Euklido algortimas (DBD) Spausdinti
( 12 Votes )

Parašė Aurimas Šimkus   

Euklido algoritimas reikalingas norint rasti dviejų skaičių didžiausią bendrą daliklį (DBD). Į funkciją siunčiame du sveikuosius skaičius, o rezultatas - sveikasis skaičius, gaunamas funkcijos vardu.

Kodas, parašytas C++ kalba:

int DBD(int sk1, int sk2)
{
 if (sk2 == 0)
 return sk1;
 else
 return DBD(sk2, sk1 % sk2);
}

 

Naudojant Euklido algoritimą, nesunkiai galima gauti ir mažiausią bendrą kartotinį (MBK):

int MBK = sk1 / DBD(sk1, sk2) * sk2;