Esercizio 2: doppia emozione... un algoritmo difficile!!!

L'algoritmo di Euclide è un algoritmo per trovare il massimo comun divisore (indicato di seguito con MCD) tra due numeri interi. È uno degli algoritmi più antichi conosciuti, essendo presente negli "Elementi di Euclide" intorno al 300 a.C.; tuttavia, probabilmente l'algoritmo non fu scoperto da Euclide, ma era noto anche 200 anni prima. Certamente era conosciuto da Eudosso di Cnido intorno al 375 a.C.; Aristotele (intorno al 330 a.C.) ne fece cenno ne "I topici", 158b, 29-35.

Descrizione in linguaggio naturale

Dati due numeri interi positivi a e b, si controlla se b è zero. Se lo è, a è il MCD. Se non lo è, si divide a / b e si assegna ad r il resto della divisione. Se r = 0 allora si può terminare affermando che b è il MCD cercato, altrimenti occorre assegnare a = b e b = r e ripetere nuovamente la divisione.

Descrizione più formale e vicina a un programma

siano a, b, mcd ed r quattro variabili in grado di contenere un numero intero

porta r a un valore diverso da 0 (ad esempio, portala a 1)

chiedi all'utente di inserire il valore di a

porta a al valore inserito dall'utente

chiedi all'utente di inserire il valore di b

porta b al valore inserito dall'utente

se b è uguale a 0

porta mcd al valore di a

altrimenti

ripeti le istruzioni seguenti fino a quando r non diventa uguale a 0

porta r al valore dell'espressione "resto della divisione di a diviso b"

se r è uguale a 0

porta mcd al valore di b

altrimenti

porta a al valore di b

porta b al valore di r

comunica all'utente il valore di mcd

Il mio secondo programma in scratch!

Anche il secondo programma Scratch che implementa il calcolo dell'MCD di due numeri interi positivi inseriti dall'utente ricalca esattamente la struttura della descrizione formale che abbiamo fornito.