Vi ho appallato abbastanza ? Per oggi credo di si...
mercoledì 6 ottobre 2004
Soluzione del Quiz
L'algoritmo di cui al post precedente calcola .. il massimo comun divisore di 2 interi positivi ! Per definizione, il MCD è il più grande numero intero positivo che divide esattamente ambedue i numeri di partenza. Sembrerebbe quindi che per trovarlo dobbiamo fare un sacco di divisioni, o almeno la scomposizione in fattori primi dei 2 numeri (e già vedo la pelle d'oca impossessarsi di molti dei miei lettori ..). Il fatto interessante, che semplifica alquanto le cose, almeno quando si tratta di computers, è che il MCD(x,y) è uguale al MCD(x,|x-y|) .. il mio algoritmo prende in considerazione coppie di numeri sempre più piccoli, e poiché il MCD esiste sempre e al minimo è 1 (in tal caso i 2 numeri si dicono "primi fra loro"), l'algoritmo arriva sempre alla fine (altrimenti non sarebbe un algoritmo, come sanno benissimo quelli che hanno studiato informatica, vero ?).
