Algoritmo euclideo

Questa pagina visualizza il funzionamento dell’Algoritmo Euclideo per calcolare il massimo comune denominatore (MCD) fra due numeri.

Imposta i due numeri usando le due caselle di testo in alto e poi premi, più volte, il bottone “Avanti” per effettuare il calcolo.

I due numeri a e b corrispondono al numero di pallini sui due lati del rettangolo che si visualizza in figura; se un numero d è un divisore sia di a che di b, allora si possono scomporre i due lati del rettangolo in segmenti corrispondenti a d pallini e il rettangolo stesso si scompone in quadrati dxd, tutti uguali fra loro. Il MCD fra a e b è quindi il lato del quadrato più grande possibile per cui si possa realizzare questa scomposizione (è facile invece – e poco significativo! – trovare quello più piccolo possibile: è sempre quello 1×1, qualunque siano i numeri a e b). 

L’algoritmo euclideo viene chiamato anche algoritmo delle divisioni successive. In effetti, a ogni passo dell’algoritmo (cioè ogni volta che si schiaccia il tasto “Avanti”) si visualizzano in figura quoziente e resto di una divisione. Al primo passo, si tratta della divisione fra i due numeri a e b e si tolgono quindi al rettangolo axb il maggior numero possibile di quadrati di lato b (a>b): il numero di questi quadrati è proprio il quoziente della divisione di a per b; rimane poi un rettangolo di cui un lato è b (cioè il più piccolo dei due numeri da cui siamo partiti) e l’altro è il resto della divisione di a per b. Se questo resto è 0, l’algoritmo finisce, il quadrato dxd diventa arancione e tornando indietro vediamo il rettangolo diviso in quadrati, tutti uguali a quello arancione. Se il resto non è 0, si itera il procedimento sul rettangolo rimasto; i resti sono sempre più piccoli (e positivi) quindi non c’è rischio che l’algoritmo prosegua all’infinito: siamo sicuri che termina e l’ultimo resto positivo è proprio il MCD(a,b). 

Provate a impostare a=21 e b=13: vedrete spuntare in questo processo una famosa successione, quella dei numeri di Fibonacci.

 461 total views,  1 views today