Massimo comun divisore con l'algoritmo di Euclide in Python
In questa lezione troverai il massimo comun divisore (MCD) di due numeri con l'algoritmo di Euclide.
Introduzione
Il problema
Semplificare frazioni, dividere cose in gruppi uguali e molti rompicapi richiedono il numero più grande che divide due numeri. Provare tutti i candidati è lento con numeri grandi. Più di 2.000 anni fa Euclide trovò un metodo molto più veloce.
Immaginalo così
Il metodo di Euclide è come piastrellare un rettangolo con le piastrelle quadrate più grandi possibili. Ritagli il quadrato più grande che puoi da un rettangolo 48 × 18, poi da ciò che resta, e continui. Quando i pezzi combaciano esattamente senza avanzi, il lato dell'ultimo quadrato è la risposta.
first, second▭ Il rettangolo: 48 × 18first % second✂️ Ciò che resta dopo aver ritagliato quadrati del lato più piccolofirst, second = second, first % second🔁 Ripeti con il pezzo avanzatowhile second:✅ Non avanza niente: il lato è l'MCD, 6Il massimo comun divisore (MCD) di due interi è il più grande intero positivo che li divide entrambi. L'algoritmo di Euclide lo trova sostituendo la coppia (a, b) con (b, a % b) finché b è 0.
Punti chiave
first, second = second, first % secondsostituisce la coppia con il numero più piccolo e il resto.- Per 48 e 18 le coppie sono (48, 18), (18, 12), (12, 6), (6, 0).
while second:si ferma quando il resto diventa 0.return abs(first)dà un risultato positivo anche per input negativi.
Quando si usa?
- Semplificare frazioni e rapporti.
- Trovare il minimo comune multiplo: a * b
//gcd(a, b). - Rompicapi con i numeri, aritmetica modulare e basi della crittografia.
Quando non serve
- Codice vero:
math.gcdè già incluso in Python e nelle versioni recenti accetta un numero qualsiasi di argomenti. - Trovare tutti i divisori comuni: l'MCD dà solo il più grande.
Codice di esempio
def gcd(first, second):
while second:
first, second = second, first % second
return abs(first)
print(gcd(48, 18))
Risultato dell'esecuzione
6
Spiegazione del codice
A ogni passo, la coppia (first, second) viene sostituita da (second, first % second). Quando il resto arriva a 0, il valore rimasto in first è il MCD, quindi il MCD di 48 e 18 è 6. La funzione abs() garantisce che il risultato sia sempre positivo. Il numero di passi cresce molto lentamente con la grandezza dei numeri, circa O(log n).
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi di approfondimento
Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.
- Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
- Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
- Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Errori comuni
Usare la sottrazione invece del resto
Sottrarre ripetutamente dà la stessa risposta, ma è molto lento quando i due numeri sono molto diversi.
while first != second:
if first > second:
first -= second
else:
second -= first
while second:
first, second = second, first % second
Hai finito questa lezione?
Segnala come imparata per tenere traccia dei tuoi progressi.
Esercitati con una sfida
Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.
- Massimo Comun Divisore Trova il numero più grande che divide entrambi i valori. Facile
- Minimo Comune Multiplo Trova il più piccolo numero positivo divisibile da entrambi i valori. Facile
- Aritmetica Esatta con Frazioni Esegui operazioni tra frazioni e restituisci una frazione ridotta ai minimi termini. Media