Implementazioni di algoritmi/Algoritmo di Euclide: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
cambio avanzamento a 25% |
Nessun oggetto della modifica |
||
Riga 1:
{{implementazioni di algoritmi}}
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.
===Implementazione in [[C]]===
<source lang="c">
Line 8 ⟶ 12:
return mcd(b, a % b);
} ;
</source>
===Implementazione in [[Python]]===
<source lang="python">
def mcd(a,b):
if b==0:
return a
else:
return mcd(b,(a%b))
</source>
[[Categoria:Implementazioni di algoritmi|Algoritmo di Euclide]]
| |||