Algoritmo di Euclide

L’algoritmo di Euclide è un metodo per trovare il massimo comune divisore tra due numeri interi.

Ricordiamo che il massimo comune divisore, MCD, tra due numeri interi è il più grande divisore comune ad entrambi.

Come si determina? Si calcola per ognuno l’elenco dei divisori e tra i due gruppi si individua il numero più grande.

Ricordo che vi avevo presentato l’algoritmo in questa lezione: massimo comune divisore con scratch.

Ma Euclide riuscì a risolvere il problema senza calcolare tutti i divisori!

L’idea è stata questa: anzichè calcolare il MCD tra i due numeri a e b, si divide a per b e si calcola il resto r.

Dopo si ricava il MCD tra b ed r e si procede fino a quando si ha resto 0. L’ultimo divisore è il MCD cercato.


Facciamo un esempio:

Prendiamo i due numeri 40 e 15 e procediamo secondo l’algoritmo di Euclide.

Primo passaggio: a/b cioè 40/15=2 resto 10

Secondo passaggio scambiamo a con b e b con r cioè 15/10=1 resto 5

Terzo passaggio scambiamo a con b e b con r cioè 10/5=2 resto 0.

Abbiamo trovato resto zero, quindi il MCD è 5.


Facciamo ancora un altro esempio:

Condideriamo i due numeri 84 e 48.

Avremo questi passaggi:

84/48=1 resto 36

48/36=1 resto 12

36/12=3 resto 0

Allora MCD è 12.


Algoritmo di Euclide per il MCD con scratch

Bene una volta capito il procedimento sviluppiamo l’algoritmo di Euclide con scratch.

Innnazitutto scegliamo uno sfondo e uno sprite qualsiasi.

euclide

Dopo creiamo le variabili necessarie:

variabili algoritmo di euclide

Poi realizziamo il nostro codice a blocchi.

– Prendiamo inizialmente i nostri due numeri in input.

– Dopo finchè il secondo numero non diventa zero facciamo queste operazioni:

– Memorizziamo nella variabile resto il resto della divisione di numero1 per numero2.

– Nella variabile numero1 memorizziamo il valore di numero2 e nella variabile numero2 memorizziamo il resto.


Provando con l’esempio sopra:

numero1=84 e numero2=48

quindi resto=numero1%numero2 cioè resto=84%48 ovvero resto=36.

Poi memorizziamo in numero1 il valore di numero2 e in numero2 il valore di resto e quindi numero1=48 e numero2=36.

E così via, faccio questi passaggi finchè non ottengo più il resto.


Notate che dopo il ciclo ho inserito un’istruzione condizionale: se il numero1 che corrisponde al nostro massimo comune divisore è negativo allora diventa positivo. Perchè ad esempio il MCD(84,48)=MCD(-84,48)=MCD(84, -48)=MCD(-84, -48).

Ecco il diagramma a blocchi completo.


Chiaramente si poteva introdurre il controllo per verificare che i numeri presi in input siano interi. Provate a farlo, vi darò la soluzione in un prossimo articolo.

Come si nota l’algoritmo di Euclide per il massimo comune divisore è una soluzione molto più semplice rispetto alla precedente.

Alcuni link utili:

Area e perimetro con scratch

Divisori di un numero con scratch

Multipli di un numero con scratch

Numeri pari con scratch

Esercizi con scratch

Potenze con scratch

Quoziente potenze stessa base con scratch

Palindroma con scratch

Storiella con scratch

Serie buffa con scratch

Operazioni matematiche con scratch

Come sommare un intervallo di numeri con scratch

Anno bisestile con scratch

Selezione con scratch

Olimpiadi di informatica con scratch

Olimpiadi di matematica con scratch

Figure equivalenti con scratch


Autore dell'articolo: cristina

Avatar per Coding Creativo

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *