Massimo Comune Divisore con Scratch

In questa lezione studieremo come trovare il massimo comune divisore con Scratch.

Innanzitutto diamo la definizione di massimo comune divisore, che possiamo abbreviare più semplicemente con il simbolo MCD.

L’MCD è il più grande divisore comune dei numeri presi in considerazione.

Ad esempio consideriamo i numeri 15 e 5. Troviamo dapprima i divisori di 15 che sono: 1,3,5,15 e poi i divisori di 5 che sono:1,5.

Quindi il più grande divisore tra i due numeri è 5.

Se il più grande divisore è 1 si dice che i numeri sono coprimi ovvero primi tra di loro.

Nell’implementazione dell’esercizio faremo uso delle liste e dei blocchi.

Quando si è davanti ad un problema complesso conviene infatti dividerlo in sottoprogrammi per poter sviluppare le varie parti separatamente.

Procedimento per trovare il massimo comune divisore con Scratch

Ecco innanzitutto le variabili che ho utilizzato e che a mano ve ne spiegherò l’utilità.

Utilizzo della lista

Ci servirà una lista per contenere tutti i possibili divisori del primo numero preso in input.

Dunque creo una lista e la chiamo ad esempio divisori.

Utilizzo del blocco divisori

Creiamo il blocco divisori che serve a trovare tutti i divisori del primo numero preso in input, che è memorizzato nella variabile appositamente creata di nome numero.

Quindi utilizziamo la variabile div che rappresenta il divisore. Questa variabile la inizializziamo a 1. Dopo realizziamo un ciclo utilizzando l’istruzione ripeti fino a quando che si fermerà quando la variabile div sarà uguale al valore del numero preso in input.

Quindi controlliamo all’interno del ciclo se il resto della divisione del numero per il divisore è uguale a zero. Se è vero allora inseriamo la variabile div all’interno della lista divisori, altrimenti non facciamo nulla. In ogni caso incrementiamo la variabile div di uno per trovare altri divisori possibili del numero preso in input.

Utilizzo del blocco trova

Ci servirà adesso un altro blocco che chiamo ad esempio trova che servirà a trovare il divisore più grande possibile.

Come agirà questo blocco? Assegniamo alla variabile lunghezza il valore della lunghezza dei divisori. Dopo usiamo un indice i che scorre la lista dalla fine all’inizio. Appena trova un divisore, quello sarà il massimo comune divisore e quindi il programma si può fermare. Se arriva ad 1 vuol dire che i numeri sono coprimi.

N.B. Potevo anche fare a meno di utilizzare la variabile lunghezza, cambiando alcune impostazioni. Cioè portando i uguale alla lunghezza di divisori e cambiare il ciclo ripeti fino a quando lunghezza di divisori è uguale a zero.

Programma principale per trovare il massimo comune divisore con Scratch

Adesso dobbiamo sviluppare il programma principale.

Chiediamo il primo numero e se negativo lo trasformiamo in positivo, perché il procedimento è uguale. Per trasformare il numero in positivo o lo moltiplichiamo semplicemente per -1 oppure utilizziamo la funziona abs.

Dopo avviamo il blocco divisori.

Poi chiediamo il secondo numero e anche questo, se negativo, lo trasformiamo in positivo.

Infine avviamo il blocco trova che troverà il massimo comune divisore.