Algoritmo di Euclide per il calcolo del MCD in Excel

QUI ho accennato all'Algoritmo di Euclide per il calcolo del Massimo Comune Divisore (MCD) di due numeri interi (positivi).
L'algoritmo di Euclide (Euclide lo descrisse nel suo libro degli Elementi) è un procedimento che permette di calcolare il MCD di due numeri mediante l'esecuzione di sottrazioni successive oppure di divisioni successive.
Supponiamo di voler calcolare il MCD di due numeri interi a e b.
Nel primo caso si procede, praticamente, in questo modo:
Si esegue la sottrazione a-b con differenza d;
[se a è minore di b, si considera il valore assoluto della differenza, cioè il numero senza il segno. E così per tutte le differenze successive]
si esegue quindi la sottrazione b- d con differenza d_1;
si esegue la sottrazione d - d_1 con differenza d_2 ;
si procede in questo modo fino a che l'ultima differenza ottenuta risulta uguale a zero (0).
Il valore che origina la differenza uguale a zero è il MCD cercato.
Seguiamo meglio mediante un piccolo esempio:
Calcoliamo il MCD di 18 e 12:
18-12 = 6
12-6 = 6
6-6 = 0
6 è il MCD di 18 e 12 (la differenza che ha dato luogo al valore zero).
In certi casi questo algoritmo può richiedere numerosissimi passaggi.

Euclide con i suoi Elementi:-)

E' possibile renderlo più veloce ricorrendo ad una serie di divisioni successive anziché sottrazioni.
Si considera il resto delle divisioni.
Calcoliamo il MCD di due numeri interi a e b.
Praticamente si procede così:
si esegue la divisione a:b con resto r
si esegue la divisione b:r con resto r_1
si esegue la divisione r : r_1
si procede in questo modo fino a che il l'ultimo resto ottenuto è zero(0).
Il resto che precede quello uguale a zero è il MCD cercato.
Si comprende meglio con un esempio:
Calcoliamo il MCD di 28 e 16
28: 16 = 1 con resto 12
16:12 = 1 con resto 4
12:4 = 3 con resto 0
MCD (28;16) = 4 (il resto precedente quello uguale a zero).
Rimando ancora a questa pagina per una spiegazione per ... più adulti!
Si può vedere anche qui.

In Excel si può applicare l'algoritmo euclideo utilizzando le funzioni RESTO() e ASS().
ASS() restituisce il valore assoluto, il numero privo di segno, di un numero reale.
Un'immagine del file:

La verifica con formula utilizza la funzione di excel MCD(num1;num2;...)
In cella G3 è immessa la formula: =MCD(A3;A4)
Da scaricare AlgoritmoEuclideoMCD.xls
Ci si può esercitare!

Articoli correlati per categorie