Interpretador Hall - Calculando o MDC
Veja no exemplo abaixo um algoritmo para se calcular o MDC (Maior Divisor
Comum) entre dois números inteiros e positivos. O algoritmo implementa o
método de Euclides (+- 300 anos A.C.).
O MDC – Maior Divisor Comum
O maior divisor comum de dois números inteiros a e b é o maior número inteiro
que divide ambos simultâneamente. A notação disto geralmente é mdc(a,b) e,
algumas vezes, simplesmente (a,b).
Algoritmo de Euclides
O Algoritmo de Euclides para calcular o maior divisor comum de dois números
inteiros diferentes de zero baseia-se no seguinte fato:
“Se r é o resto, quando a é dividido por b então o máximo divisor comum de a
e b é igual ao máximo divisor comum de b e r”
isto é, se r = Resto(a,b) então MDC(a,b) = MDC(b,r). Essa regra define um
algoritmo para se calcular o MDC entre dois números (inteiros e positivos).
Calculando o MDC - versão 1
algoritmo()
{
inteiro a,b,c;
leia ("informe o valor de a: ",a);
leia ("informe o valor de b: ",b);
// os valores nao podem ser negativos
a := ValorABS(a);
b := ValorABS(b);
enquanto (b <> 0)
{
c = Resto(a,b);
a = b;
b = c;
}
escreva ("O MDC entre a e b e ", a);
}
Interpretador Hall
1
No exemplo abaixo um algoritmo para se calcular o MDC (Máximo Divisor
Comum) entre dois números inteiros e positivos é implementado através de
uma função de usuário. (uma função criada por você mesmo)
Calculando o MDC – versão 2
algoritmo()
{
inteiro a,b,c;
leia ("informe o valor de a: ",a);
leia ("informe o valor de b: ",b);
c := CalcMDC(a,b);
escreva ("O MDC entre a e b e ", c);
}
//-----------------------------------------------------------------------------------funcao CalcMDC (inteiro x, inteiro y)
{
inteiro r;
// os valores nao podem ser negativos
x := ValorABS(x);
y := ValorABS(y);
enquanto (y <> 0)
{
r = Resto(x,y);
x = y;
y = r;
}
retorne x;
}
Interpretador Hall
2
No exemplo abaixo um algoritmo para se calcular o MDC (Máximo Divisor
Comum) entre dois números inteiros e positivos é implementado através de
uma função de usuário recursiva.
Calculando o MDC – versão 3
algoritmo()
{
inteiro a,b,c;
leia ("informe o valor de a: ",a);
leia ("informe o valor de b: ",b);
x := ValorABS(x);
y := ValorABS(y);
c := CalcMDC(a,b);
escreva ("O MDC entre a e b e ", c);
}
//-----------------------------------------------------------------------------------funcao CalcMDC (inteiro x, inteiro y)
{
se ( Resto(x,y) == 0 )
{
retorne y;
}
senao
{
retorne CalcMDC(y,Resto(x,y));
}
}
Interpretador Hall
3
No exemplo abaixo o algoritmo para se calcular o MDC (Máximo Divisor
Comum) entre dois números inteiros e positivos é implementado através da
função interna do interpretador. O interpretador Hall disponibiliza uma
função de nome MDC que espera receber dois argumentos do tipo inteiro e
positivos.
Calculando o MDC – versão 4
algoritmo()
{
inteiro a,b,c;
leia ("informe o valor de a: ",a);
leia ("informe o valor de b: ",b);
x := ValorABS(x);
y := ValorABS(y);
c := MDC(a,b);
escreva ("O MDC entre a e b e ", c);
}
Interpretador Hall
4
No exemplo abaixo o algoritmo para se calcular o MDC (Máximo Divisor
Comum) entre vários números inteiros e positivos é implementado através da
função interna do interpretador. O interpretador Hall disponibiliza uma
função de nome MDC que espera receber dois argumentos do tipo inteiro e
positivos.
Calculando o MDC – versão 5
algoritmo()
{
inteiro a,b,c,d,e;
leia
leia
leia
leia
("informe
("informe
("informe
("informe
o
o
o
o
valor
valor
valor
valor
de
de
de
de
a: ",a);
b: ",b);
c: ",c);
d: ",d);
a := ValorABS(a);
b := ValorABS(b);
c := ValorABS(c);
d := ValorABS(d);
e := MDC(a,b);
e := MDC(e,c);
e := MDC(e,d);
escreva ("O MDC entre a,b,c e d: ", e);
}
Interpretador Hall
5
No exemplo abaixo o algoritmo para se calcular o MDC (Máximo Divisor
Comum) entre vários números inteiros e positivos é implementado através da
função interna do interpretador. O interpretador Hall disponibiliza uma
função de nome MDC que também pode receber uma lista de valores, inteiros
e positivos, separados por vírgulas.
Calculando o MDC – versão 6
algoritmo()
{
inteiro a,b,c,d,e;
leia
leia
leia
leia
("informe
("informe
("informe
("informe
o
o
o
o
valor
valor
valor
valor
de
de
de
de
a: ",a);
b: ",b);
c: ",c);
d: ",d);
a := ValorABS(a);
b := ValorABS(b);
c := ValorABS(c);
d := ValorABS(d);
e := MDC (a, MDC (b, MDC (c,d) ) );
escreva ("O MDC entre a,b,c e d: ", e);
}
Comentário:
Observe a instrução e := MDC (a, MDC (b, MDC (c,d) ) );
O interpretador Hall permite o empilhamento de chamadas de função. É
exatamente o que a instrução acima faz. A primeira parte a ser executada é a
instrução mais interna, no caso MDC(c,d).
Assim que o sistema retorna dessa chamada, a instrução seguinte é chamada,
a saber MDC (b, MDC(c,d) ) só que agora, a expressão MDC(c,d) já tem um
valor conhecido, digamos k1, de modo que a instrução a ser executada é:
MDC(b,k1).
Finalmente, a última instrução, MDC (a, MDC (b,k1)) é executada sendo que
a expressão MDC(b,k1) agora tem um valor conhecido, digamos k2. Assim a
expressão a ser avaliada é MDC(a,k2).
Por isso é denominada de pilha de execução. A sequência de execução
acontece no modo FILO (first-in, last-out), primeiro a entrar (empilhar) é o
último a sair (desempilhar). A sequência de execução é...
MDC(c,d)
MDC (b,MDC(c,d))
Interpretador Hall
MDC (a,MDC(b,MDC(c,d)))
6
No exemplo abaixo (último) demonstra-se uma outra forma de se chamar a
função interna MDC para se calcular o máximo divisor comum de uma série de
números (inteiros e positivos). (talvez a forma mais simples)
O interpretador Hall disponibiliza uma função de nome MDC que também pode
receber uma lista de valores, inteiros e positivos, separados por vírgulas.
Calculando o MDC – versão 7
algoritmo()
{
inteiro a,b,c,d,e;
leia
leia
leia
leia
("informe
("informe
("informe
("informe
o
o
o
o
valor
valor
valor
valor
de
de
de
de
a: ",a);
b: ",b);
c: ",c);
d: ",d);
a := ValorABS(a);
b := ValorABS(b);
c := ValorABS(c);
d := ValorABS(d);
e := MDC (a,b,c,d);
escreva ("O MDC entre a,b,c e d: ", e);
}
Nota: O pseudo-código do algoritmo de Euclides pode ser visto abaixo.
AlgoritmoDeEuclides(inteiro a, inteiro b)
dividendo ← a
divisor ← b
enquanto resto(dividendo/divisor) ≠ 0
c ← resto(dividendo/divisor)
dividendo ← divisor
divisor ← c
retornar divisor
That's All Folks!
Interpretador Hall
7