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!
Stampa il post