.4.1 Algoritmo euclidiano ampliado [Dados los enteros A y B con A B 0, este algoritmo calcula el MCD(A, B) y encuentra los enteros s y t tal que ...

.4.1 Algoritmo euclidiano ampliado
[Dados los enteros A y B con A B 0, este algoritmo calcula el MCD(A, B) y encuentra los enteros s y t tal que sA tB MCD(A, B).]
Entrada: A, B [enteros con A B 0]
Cuerpo del algoritmo: a : A, b : B, s : 1, t : 0, u : 0, : 1, [pre-condição: a sA tB y b u A B]
while (b = 0)
[invariante del bucle: a sA tB y b uA B, MCD(a, b) MCD(A,B)]
r : a mod b, q : a div b
a : 6, b : r
ne u : s ฀ uq, ne : t ฀ q
s : u, t :
u : ne u, : ne
end while
MCD : a
[post-condição: MCD(A, B) a sA tB]
Salida: MCD[a entero positivo], s, t [enteros]
En los ejercicios 28 y 29, para los valores dados de A y B, realice una tabla que muestre el valor de s, t y sA tB antes del inicio del bucle while y después de cada iteración del bucle.
28. A 330, B 156 29. A 284, B 168