In questa lezione svilupperemo l’algoritmo Euclideo in Python.
L’algoritmo di Euclide è un metodo utilizzato per trovare il massimo comune divisore tra due numeri interi.
Per massimo comune divisore, MCD, tra due numeri interi indichiamo il più grande divisore comune ad entrambi.
Il metodo di Euclide consiste nel dividere i due numeri e considerare il resto. Il procedimento termina quando si trova il resto uguale a zero.
Facciamo degli esempi.
Primo esempio:
Prendiamo due numeri ad esempio 20 e 15 e procediamo secondo l’algoritmo di Euclide.
Primo passaggio: a/b cioè 20/15=1 resto 5 – il resto è diverso da zero, quindi continuo a dividere.
Sia avrà così il secondo passaggio scambiando a con b e b con r, cioè 15/5=3 resto 0.
Abbiamo trovato il resto uguale a zero, quindi il MCD è 5.
Secondo esempio:
Realizziamo un secondo esempio al fine di comprendere bene come funziona l’algoritmo di Euclide.
Prendiamo quindi i numeri 64 e 30.
64/30=2 resto 4 – il resto è diverso da zero, quindi continuiamo a dividere.
30/4=7 resto 2 – il resto è diverso da zero, quindi continuiamo a dividere.
4/2=2 resto 0
Il resto è zero, quindi il MCD è 2.
Algoritmo Euclideo in Python
Realizziamo adesso questo algoritmo in Python.
Innanzitutto prendiamo in input i due numeri a e b. Poi finché b è maggiore di 0, calcoliamo il resto della divisone di a diviso b e scambiamo a con b e b con r.
Dunque stampiamo a.
Ecco quindi il codice completo che rappresenta l’algoritmo Euclideo in Python:
a=int(input('Inserisci il primo numero: '))
b=int(input('Inserisci il secondo numero: '))
while b>0:
r=a%b
a,b=b,r
print(a)Questa è una possibile implementazione dell’algoritmo, nella prossima lezione faremo altri esempi sui cicli in Python.
Alcuni link utili
Indice tutorial sul linguaggio Python
1 – Introduzione al linguaggio Python
2 – Le variabili
3 – Operatori aritmetici e di assegnazione
4 – Stringhe
5 – Casting
6 – Input e print
8 – Errori in Python
9 – Script Python
10 – Scambio di variabili
