Algoritmo di euclide

Calcolo del massimo comun divisore tra due numeri interi.

Consideriamo adesso un algoritmo classico, per il calcolo del Massimo Comun Divisore (MCD) tra due numeri interi, n ed m: l’Algoritmo di Euclide. Senza perdita di generalità, assumiamo n >= m > 0 e chiamiamo R il MCD. Possiamo descrivere l’Algoritmo di Euclide in un linguaggio pseudo-naturale:

Euclide(n,m)
x = n
y = m
while x /= y do
if x > y
then x = x - y
else y = y - x
endif
end
R = y

Questo algoritmo ha un ciclo di natura diversa da quelli visti in precedenza, perchè non si sa quante volte il ciclo stesso venga eseguito. Consideriamo il ciclo dell’algoritmo e scriviamolo esplicitando un contatore k del numero di cicli eseguiti:

dai valori xk-1 , yk-1 si giunge ai valori xk , yk

Otteniamo le seguenti condizioni:
Asserzione iniziale: n >= m > 0
Condizione iniziale: x0 = n, y0 = m
Condizione di terminazione: xt = yt per qualche t
Invariante: MCD(xk , yk ) = MCD(n,m)
Asserzione finale: R = MCD(xt , yt ) = MCD(n,m)
In questo caso, non si sa a priori quante volte venga eseguito il ciclo, perchè non si sa quando la condizione che lo controlla diventi vera. Nella Tabella A riportiamo l’esecuzione dell’algoritmo per n = 40 ed m = 16.


Tabella A























k

x

y

0

(n =) 40

(m = ) 16

1

24

16

2

8

16

3

8

8

La correttezza dell’algoritmo è dovuta alla seguente proprietà del MCD:

Supponendo, senza restrizione, che n >= m, se R = MCD(n,m), allora:

(a) n = h1 R, m = h2 R
(b) Non esiste un numero R’ > R tale che per esso valgano le (a).

Peeplo News

Attualità e Notizie su Peeplo News.

Cercale ora!