Algoritmo di Euclide in Python
L’algoritmo sostituisce la coppia con divisore e resto.
Che cos’è Algoritmo di Euclide?
L’algoritmo sostituisce la coppia con divisore e resto.
Calcola il massimo comune divisore.
Quando si usa?
- Comprendere algoritmi e strutture dati.
- Osservare ogni passaggio e gestire i casi limite.
- Confrontare tempo di esecuzione e memoria.
Codice di esempio
main.py
def gcd(first, second):
while second:
first, second = second, first % second
return abs(first)
print(gcd(48, 18))Output previsto
6Come funziona
Quando il resto diventa zero, l’altro valore è il MCD; complessità logaritmica.
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi pratici
Modifica gli input e verifica i casi limite prima di usare dataset più grandi.
- Prova input vuoto, un elemento e duplicati.
- Stampa lo stato dopo ogni passaggio.
- Confronta le prestazioni con un’altra soluzione.