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. Ricordiamo che: 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.
Consideriamo due esempi per comprendere meglio l’algoritmo di Euclide:
Migliora le tue capacità di programmazione Python seguendo i nostri corsi in diretta!
Primo esempio funzionamento algoritmo euclideo:
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 funzionamento algoritmo euclideo:
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 l’algoritmo in Python.
Innanzitutto prendiamo in input i due numeri interi 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)
L’algoritmo di Euclide è un concetto fondamentale in matematica e informatica, e la sua implementazione in Python è semplice ed efficiente.
Conclusioni
L’algoritmo di Euclide è un’importante tecnica utilizzata per trovare il massimo comune divisore tra due numeri interi. La sua semplicità e efficacia lo rendono uno strumento fondamentale nella risoluzione di problemi matematici e di programmazione.
In questa lezione abbiamo esaminato il funzionamento dell’algoritmo di Euclide e abbiamo analizzato due esempi pratici per comprendere come applicarlo in situazioni reali. Abbiamo visto come l’algoritmo si basi sulla divisione e sul resto, iterando finché non si raggiunge un resto zero.
Abbiamo poi implementato l’algoritmo in Python, fornendo una spiegazione dettagliata del codice e dei passaggi coinvolti nel calcolo del massimo comune divisore. Questa implementazione ci ha mostrato come sia possibile tradurre concetti matematici complessi in codice Python semplice ed efficiente.
L’apprendimento dell’algoritmo di Euclide non solo arricchisce le nostre conoscenze matematiche, ma ci fornisce anche un’importante competenza nell’affrontare problemi di programmazione che richiedono la determinazione del massimo comune divisore.
Continua a esplorare il mondo della programmazione e approfondisci le tue conoscenze con ulteriori lezioni e esercizi pratici. La padronanza di concetti come l’algoritmo di Euclide ti renderà un programmatore più competente e preparato per affrontare sfide sempre più complesse.
Non dimenticare di prendere in considerazione la lettura del libro “50 Algoritmi per imparare Python” per approfondire le conoscenze su questo linguaggio.
Nelle prossime lezioni, esploreremo ulteriormente i concetti di programmazione in Python, approfondendo altri algoritmi e strutture dati utili per risolvere una vasta gamma di problemi.
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