Implementazioni di algoritmi/Algoritmo di Euclide

Wikibooks, manuali e libri di testo liberi.

L'algoritmo di Euclide è un algoritmo per trovare il massimo comun divisore (indicato di seguito con MCD) tra due numeri interi. È uno degli algoritmi più antichi conosciuti, essendo presente negli Elementi di Euclide intorno al 300 a.C.; tuttavia l'algoritmo non è stato probabilmente scoperto da Euclide, ma potrebbe essere stato conosciuto anche 200 anni prima. Certamente era conosciuto da Eudosso di Cnido intorno al 375 a.C.; Aristotele (intorno al 330 a.C.) ne ha fatto cenno ne I topici, 158b, 29-35. L'algoritmo non richiede la fattorizzazione dei due interi.

Dati due numeri naturali a e b, si controlla se b è zero. Se lo è, a è il MCD. Se non lo è, si divide a / b e si assegna ad r il resto della divisione (operazione indicata con "a modulo b" più sotto). Se r = 0 allora si può terminare affermando che b è il MCD cercato altrimenti occorre assegnare a = b e b = r e si ripete nuovamente la divisione. L'algoritmo può essere anche espresso in modo naturale utilizzando la ricorsione in coda.

[modifica] Implementazione in C/C++ - versione ricorsiva

int mcd(int a, int b) {
  if (b == 0)
    return a;  
  else
    return mcd(b, a % b); 
} ;

[modifica] Implementazione in C/C++ - versione non ricorsiva

int mcd(int a, int b) {
  int t;
  while (b != 0) {
    t = b;
    b = a % b;
    a = t;
  }
  return a;
}

[modifica] Implementazione in Python - versione ricorsiva

def mcd(a,b):
  if b==0:
    return a
  else:
    return mcd(b,(a%b))

[modifica] Implementazione in Python - versione non ricorsiva

def mcd(a, b):
  while b:
    a, b = b, a%b
  return a

[modifica] Implementazione in Visual Basic .NET - versione non ricorsiva

    Public Function MCD(ByVal a As Integer, ByVal b As Integer) As Integer
        Dim m As Decimal
        If b = 0 Then Return a Else 
        Do
            m = a Mod b
            a = b
            b = m
        Loop Until b = 0
        Return a
    End Function