Algoritmo di Euclide: differenze tra le versioni

Versione delle 18:54, 26 nov 2021

Versione delle 01:07, 16 dic 2021

Riga 4:

Dati due [[numero naturale|numeri naturali]] <math>a</math> e <math>b</math>, l'algoritmo prevede che si controlli se <math>b</math> è zero (questa prima fase rientra ovviamente nell'ambito di un uso moderno dell'algoritmo ed era ignorata da Euclide e dai suoi predecessori, che non conoscevano il concetto di zero). Se lo è, <math>a</math> è il MCD. Se non lo è, si

deve dividere <math>\frac{a}{b}</math> e definire <math>r</math> come il resto della divisione (operazione indicata con "a modulo b" più sotto). Se <math>r=0</math> allora si può affermandoaffermare che <math>b</math> è il MCD cercato, altrimenti occorre assegnare <math>a'=b</math> e <math>b'=r</math> e ripetere nuovamente la divisione.

L'algoritmo può essere espresso in modo naturale utilizzando la [[Algoritmo ricorsivo#Ricorsione in coda|ricorsione in coda]].