MCD divisioni successive (scuola media)

MCD divisioni successive (scuola media)

Calcolare il Massimo Comun divisore tra due numeri usando il metodo delle divisioni successive. Si può fruire di questo tutorial in forma di mappa mentale su wiki2map

Versione di Scratch utilizzata

La versione di scratch usata in questo progetto è scratch 3.0 online.

Cosa richiede l'esercizio

Forniti i due numeri, prima quello più grande e poi quello più piccolo, scratch con un ciclo il programma calcola il MCD.

Ripetere divisioni fino a trovare il MCD

Per chi non ama leggere: Matteo Ruffoni, MCD con divisioni successive, su YouTube, 31 gen 2020.
La velocità di calcolo del PC^VK permette di eseguire molti calcoli in poco tempo. Questa caratteristica è proprio quella che fa al caso nostro visto che per calcolare il MCD si devono ripetere delle divisioni fino ad ottenere quella che avrà resto uguale a zero.
Il metodo delle divisioni successive si può spiegare grazie alla osservazione che segue. Un divisore comune di due numeri è anche divisore del resto della divisione del più grande per il più piccolo dei due infatti, passando ad un esempio se $9$ è un divisore comune di $108$ e $45$ poiché
$108:45=2\ con\ resto\ di\ 18$
e quindi $108=45\cdot 2+18$, allora $9$ è anche sicuramente un divisore del $18=9\cdot 2$ che è il resto.
Scritto su una sola riga mettendo in evidenza il fattore $9$
$108=45\cdot 2+18=9\cdot 12=9\cdot 5\cdot 2+9\cdot 2$
Applicando questa proprietà di tutti i divisori comuni al MCD possiamo quindi affermare che il MCD di due numeri è uguale al MCD del più piccolo dei due e del resto della divisione del più grande con il più piccolo, che continuando a seguire l'esempio numerico:
$MCD(108,45)=MCD(45,18)$.
Possiamo quindi ripetere le divisioni fino a che il resto non diventi 0, e quindi il numero più piccolo, essendo divisore del più grande, diventa il MCD.
Da $45:18=2\ con\ resto\ di\ 9$ e da $18:9=2\ con\ resto=0$ ricaviamo che
$MCD(108,45)=MCD(45,18)=MCD(18,9)$.
concludendo $MCD(108,45)=9$

Variabili

Per questo progetto useremo uno stage molto scarno, nulla vieta a chi lo remixa di arricchire le funzioni di base con un output più prolisso. Le variabili necessarie (input) al funzionamento sono quattro NumeroGrande, NumeroPiccolo, MCD e il Resto, resto della divisione tra il numero grande e il numero piccolo che sostituisce il numero piccolo dopo che è stato messo al posto del grande. L'output sarà visibile nella variabile MCD che alla fine dell'esecuzione assumerà il valore di NumeroPiccolo.

Istruzioni	Immagini
NumeroGrande, NumerPiccolo, MCD e Resto

Input e Valori iniziali

Clikkata la bandiera verde, il Gatto ci chiederà di inserire NumeroGrande ed NumeroPiccolo, è opportuno che NumeroGrande sia più grande di NumeroPiccolo, ovviamente si può migliorare il programma inserendo dei controlli per eventuali errori.

Sprite	Blocchi codice	Istruzioni
		Il valore iniziale del Resto viene posto uguale a 0, non è necessario ma rende il progetto un po' più ordinato.
		NumeroGrande e NumeroPiccolo vengono richiesti e salvati nelle variabili.

Il ciclo repeat until

Questo ciclo si occupa di controllare il resto della divisione NumeroGrande diviso NumeroPiccolo. Finché il resto sarà un numero diverso da zero nel ciclo il NumeroGrande verrà sostituito dal NumeroPiccolo e si passerà a riprovare la divisione. La divisione che ha resto uguale a zero interrompe il ciclo ed il NumeroPiccolo è il MCD cercato.

Sprite	Blocchi codice	Istruzioni
		Il ciclo repeat che si ripete finché non si realizza la condizione Resto uguale a 0.
		La condizione Resto maggiore di 0, corrisponde all'operazione (NumeroGrande mod NumeroPiccolo) > 0, in italiano (resto della divisione di NumeroGrande diviso NumeroPiccolo) > 0.
		La prima istruzione del ciclo pone il Resto uguale al resto della divisione NumeroGrande diviso NumeroPiccolo.
		Questa istruzione sostituisce al NumeroGrande il NumeroPiccolo
		Ed infine rispettando l'ordine al NumeroPiccolo viene sostituito il Resto, il prossimo ciclo si ripeterà con numeri più bassi.
		Il ciclo repeat montato, attenzione all'ordine!

Output MCD

Appena la il calcolo del resto, operazione che possiamo chiamare a questo punto modulo, la prima coppia di valori che fa si che NumeroGrande modulo NumeroPiccolo = 0 interrompe il ciclo ed il NumeroPiccolo, essendo un divisore del grande, corrisponde al MCD, che per le considerazioni precedenti, è il MCD dei due numeri iniziali. quindi si pone MCD = NumeroPiccolo, ed il nostro programma è completato.

Sprite	Blocchi codice	Istruzioni
		Output finale.

Codice completo MCD con divisioni successive

Con questo codice il MCD viene restituito nella casella MCD, mentre nelle altre caselle presenti sullo schermo i numeri diventano quelli della divisione NumeroGrande diviso NumeroPiccolo che produce Resto uguale a zero. Si possono aggiungere le variabili ed i blocchi necessari per avere un output dal gatto più comprensibile.

Sprite	Blocchi codice	Istruzioni
		Codice completo del progetto.

Schema progetto da montare

A questo link https://scratch.mit.edu/projects/363725183/ si trova il progetto scratch smontato va remixato e montato nella sequenza corretta.

Bibliografia

• Guida all’uso di Scratch Versione Studenti; Alberto Barbero, Marco Marchisotti, Alberto Davì; Associazione Dschola, Iniziativa realizzata nell’ambito del progetto Diderot della Fondazione CRT, 2014

Collegamenti esterni

• http://scratchblocks.github.io
• Guida all’uso di Scratch Versione Studenti