Faça o teste de mesa do algoritmo para os seguintes pares de valores inteiros:
e
.
algoritmo calcular_mdc;
declare número inteiro i,mdc,x,y;
i \leftarrow 1;
enquanto (i\leq3) faça
escreva('Entre com dois inteiros: ');
leia(x,y);
enquanto (x f y ) faça
se (x > y) então
x \leftarrow x - y;
senão
Y \leftarrowY - x;
fim-se;
fim-enquanto;
mdc \leftarrow x;
escreva('O Máximo Divisor Comum : ', mdc);
i \leftarrowi + 1;
fim-enquanto;
fim-algoritmo.
algoritmo calcular_mdc;
declare número inteiro i,mdc,x,y;
i \leftarrow 1;
enquanto (i\leq3) faça
escreva('Entre com dois inteiros: ');
leia(x,y);
enquanto (x f y ) faça
se (x > y) então
x \leftarrow x - y;
senão
Y \leftarrowY - x;
fim-se;
fim-enquanto;
mdc \leftarrow x;
escreva('O Máximo Divisor Comum : ', mdc);
i \leftarrowi + 1;
fim-enquanto;
fim-algoritmo.
Passo 1
Vamos testar o algoritmo calcular_mdc, que lê três vezes um par de inteiros (x,y) e calcula o Máximo Divisor Comum por subtrações sucessivas (variante do algoritmo de Euclides). Para resolver, vamos simular o laço externo (i de 1 a 3) e, dentro dele, o laço interno que reduz x e y até ficarem iguais, ponto em que esse valor comum é o mdc.
Passo 2
Para o par (5,3):
• Estado inicial: x=5, y=3
• Iteração 1 do enquanto interno: x>y, então x ← 5−3 = 2
• Iteração 2: agora x=2, y=3; x<y, então y ← 3−2 = 1
• Iteração 3: agora x=2, y=1; x>y, então x ← 2−1 = 1
• A condição x=y=1 é satisfeita, saímos do laço interno. Logo, mdc=1.
O algoritmo imprime 1.
• Estado inicial: x=5, y=3
• Iteração 1 do enquanto interno: x>y, então x ← 5−3 = 2
• Iteração 2: agora x=2, y=3; x<y, então y ← 3−2 = 1
• Iteração 3: agora x=2, y=1; x>y, então x ← 2−1 = 1
• A condição x=y=1 é satisfeita, saímos do laço interno. Logo, mdc=1.
O algoritmo imprime 1.
Passo 3
Para o par (25,15):
• Estado inicial: x=25, y=15
• Iteração 1: x>y, x ← 25−15 = 10
• Iteração 2: x=10, y=15; x<y, y ← 15−10 = 5
• Iteração 3: x=10, y=5; x>y, x ← 10−5 = 5
• Agora x=y=5, saímos do laço interno. Logo, mdc=5.
O algoritmo imprime 5.
• Estado inicial: x=25, y=15
• Iteração 1: x>y, x ← 25−15 = 10
• Iteração 2: x=10, y=15; x<y, y ← 15−10 = 5
• Iteração 3: x=10, y=5; x>y, x ← 10−5 = 5
• Agora x=y=5, saímos do laço interno. Logo, mdc=5.
O algoritmo imprime 5.
Passo 4
Para o par (21,3):
• Estado inicial: x=21, y=3
• Subtrações sucessivas de y até x igualar y:
– x ← 21−3 = 18
– x ← 18−3 = 15
– x ← 15−3 = 12
– x ← 12−3 = 9
– x ← 9−3 = 6
– x ← 6−3 = 3
• Agora x=y=3, saímos do laço interno. Logo, mdc=3.
O algoritmo imprime 3.
• Estado inicial: x=21, y=3
• Subtrações sucessivas de y até x igualar y:
– x ← 21−3 = 18
– x ← 18−3 = 15
– x ← 15−3 = 12
– x ← 12−3 = 9
– x ← 9−3 = 6
– x ← 6−3 = 3
• Agora x=y=3, saímos do laço interno. Logo, mdc=3.
O algoritmo imprime 3.
Resposta
Os resultados do teste de mesa são: para (5,3) mdc=1; para (25,15) mdc=5; para (21,3) mdc=3.