Questo sito contribuisce alla audience di

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!