apostila
259 pág.

apostila


DisciplinaAlgoritmos e Estrutura de Dados I707 materiais7.916 seguidores
Pré-visualização50 páginas
o co´digo global independente.
No caso, o programador usou diretivas do compilador para alterar o comportamento
padra\u2dco que aborta o programa se o usua´rio digitar um tipo na\u2dco esperado. Trata corre-
tamente o erro e quando tudo esta´ certo, termina o procedimento. Importante notar
que, para leitura de dados, o para\u2c6metro tem que ser passado por refere\u2c6ncia, e na\u2dco por
valor, sena\u2dco o valor seria lido em uma co´pia da varia´vel do programa principal.
Considerac¸o\u2dces similares sa\u2dco feitas para a outra func¸a\u2dco e o procedimento, ambos
possuem co´digo pro´prio e fazem com que a atenc¸a\u2dco do programador fique voltada
exclusivamente para o subproblema da vez. Desde que o proto´tipo da func¸a\u2dco ou pro-
cedimento esteja corretamente especificado, na\u2dco ha´ problema em se alterar o co´digo
interno. Notamos tambe´m que no caso da func¸a\u2dco, foram usadas varia´veis locais para
aux´\u131lio no ca´lculo do d´\u131gito verificador. Tudo para o bem da clareza do co´digo prin-
cipal. Se um dia mudarem a definic¸a\u2dco de como se calcula o d´\u131gito verificador, basta
alterar a func¸a\u2dco que o programa principal continuara´ a funcionar corretamente.
Na u´ltima func¸a\u2dco e´ importante notar a passagem de para\u2c6metros por valor. Isto
permitiu o lac¸o que controla o loop interno usar o pro´prio para\u2c6metro como condic¸a\u2dco
de parada, pois ele e´ dividido por 10 a cada iterac¸a\u2dco. Se o para\u2c6metro fosse passado
por refere\u2c6ncia isto na\u2dco poderia ser feito, pois estar´\u131amos estragando o valor da varia´vel
que sera´ ainda usada no programa principal.
Ainda uma u´ltima observac¸a\u2dco, no procedimento que separa o nu´mero de seu d´\u131gito
verificador, atentar para a sintaxe, em Pascal, que se usa quando se quer passar dois
para\u2c6metros do mesmo tipo, um por valor e outro por refere\u2c6ncia. No caso, eles devem
ser separados pelo s´\u131mbolo do ponto-e-v´\u131rgula, o segundo deles contendo a palavra var
para indicar refere\u2c6ncia.
9.4. CA´LCULO DO MDC PELA DEFINIC¸A\u2dcO 119
9.4 Ca´lculo do MDC pela definic¸a\u2dco
Nesta sec¸a\u2dco vamos revisitar o ca´lculo do MDC pela definic¸a\u2dco estudado na sec¸a\u2dco 8.5.
Deixamos propositalmente em aberto a questa\u2dco de que aquele co´digo continha trechos
de co´digo similares que tinham que ser repetidos por causa de um nu´mero de entrada
variante no programa.
De fato, naquele co´digo exibido na figura 8.15 o ca´lculo para saber se o nu´mero a
era par difere do ca´lculo para saber se o nu´mero b e´ par apenas por conta do valor de
a ou b. O mesmo ocorre para o co´digo da figura 8.16 no caso de nu´meros \u131´mpares.
Na verdade, os quatro trechos de co´digo esta\u2dco ali apenas para se saber quantas
vezes um dado nu´mero n pode ser dividido por um nu´mero primo p, seja ele o 2 ou
qualquer \u131´mpar primo.
Este ca´lculo pode ser feito em um subprograma que recebe os nu´meros de entrada
de alguma maneira e que devolva o valor correto tambe´m segundo uma convenc¸a\u2dco.
Esta convenc¸a\u2dco, em Pascal, e´ dada pelo proto´tipo de uma func¸a\u2dco que e´ constitu´\u131do
por tre\u2c6s para\u2c6metros: o nome da func¸a\u2dco, os nu´meros n e p envolvidos e, finalmente, o
tipo do valor devolvido pelo subprograma, isto e´, um tipo que contenha o nu´mero de
vezes em que n e´ dividido por p.
function num vezes que divide(p,n : integer) : integer ;
Outro trecho de co´digo repetido e´ a atualizac¸a\u2dco do MDC para receber a menor
pote\u2c6ncia do primo sendo calculado, na primeira vez e´ o 2, nas outras vezes e´ um primo
\u131´mpar.
Basta criarmos um segundo proto´tipo de func¸a\u2dco que calcule a pote\u2c6ncia do primo
elevado ao valor do menor contador. Este pode ser o seguinte:
function potencia(n, i : integer) : integer ;
Estas interfaces nos permitem modificar o programa do ca´lculo do MDC pela
definic¸a\u2dco conforme mostra a figura 9.8.
Observamos que o uso de func¸o\u2dces e procedimentos permite muita flexibilidade ao
programador, pois ele pode alterar o co´digo da func¸o\u2dces, se quiser, tornando-as mais
eficientes (caso na\u2dco fossem) sem que haja efeito colateral no programa principal. As
figuras 9.9 e 9.10 mostram sugesto\u2dces de co´digo para as func¸o\u2dces.
Na verdade, este co´digo na\u2dco e´ muito apropriado, pois exige um comportamento na\u2dco
muito elegante na func¸a\u2dco num vezes que divide, ela tem o efeito colateral de alterar
o valor da varia´vel n, o que na\u2dco e´ natural dado o nome da func¸a\u2dco. Deveria apenas
contar o nu´mero de vezes que divide e na\u2dco fazer mais nada. O problema na\u2dco pode ser
resolvido com este mesmo algoritmo sem este efeito colateral. Em todo caso, sabemos
que o algoritmo de Euclides e´ mais eficiente, mais simples de implementar e sobretudo
mais elegante!
120 CAPI´TULO 9. FUNC¸O\u2dcES E PROCEDIMENTOS
program mdcpeladefinicao ; (\u2217 pela definicao de mdc \u2217)
var
a, b, primo, mdc: longint ;
cont a , cont b , menor cont : integer ;
function num vezes que divide(p: integer ; var n: longint) : integer ;
(\u2217 codigo da funcao num vezes que divide \u2217)
function potencia(n,p : integer) : integer ;
(\u2217 codigo da funcao potencia \u2217)
begin (\u2217 programa principal \u2217)
read (a ,b) ;
mdc:= 1;
cont a:= num vezes que divide(2 ,a) ;
cont b:= num vezes que divide(2 ,b) ;
i f cont a <= cont b then
menor cont:= cont a
else
menor cont:= cont b ;
mdc:= mdc \u2217 potencia(2 ,menor cont) ;
writeln (\u2019mdc= \u2019 ,mdc) ;
primo:= 3;
while (a <> 1) and (b <> 1) do
begin
writeln (primo) ;
cont a:= num vezes que divide(primo,a) ;
cont b:= num vezes que divide(primo,b) ;
i f cont a <= cont b then
menor cont:= cont a
else
menor cont:= cont b ;
mdc:= mdc \u2217 potencia(primo,menor cont) ;
primo:= primo + 2;
end;
writeln (mdc) ;
end.
Figura 9.8: Calcula MDC entre a e b pela definic¸a\u2dco usando func¸o\u2dces.
9.4. CA´LCULO DO MDC PELA DEFINIC¸A\u2dcO 121
function num vezes que divide(p: integer ; var n: longint) : integer ;
var cont : integer ;
begin
(\u2217 descobre quantas vezes o 2 divide as duas entradas \u2217)
cont:= 0;
while n mod p = 0 do
begin
cont:= cont + 1;
n:= n div p;
end;
writeln (\u2019num_vezes_que_divide= \u2019 ,cont) ;
num vezes que divide:= cont ;
end;
Figura 9.9: Calcula quantas vezes um nu´mero divide outro.
function potencia(n,p : integer) : integer ;
var pot : longint ;
i : integer ;
begin
pot:= 1;
i:= 1;
while i <= p do
begin
pot:= pot \u2217 n;
i:= i + 1;
end;
writeln (\u2019potencia= \u2019 ,pot) ;
potencia:= pot ;
end;
Figura 9.10: Calcula a pote\u2c6ncia de um nu´mero elevado a outro.
9.4.1 Calculando ra´\u131zes de equac¸o\u2dces do segundo grau
Para reforc¸armos os conceitos em estudo, consideremos aqui o problema de se ler os
coeficientes a, b e c que definem uma equac¸a\u2dco do segundo grau ax2 + bx + c = 0 e
imprimir as ra´\u131zes calculadas pela fo´rmula de Ba´skara. O programa deve imprimir
mensagens corretas no caso de na\u2dco haverem ra´\u131zes reais bem como na\u2dco deve aceitar
entradas cujo valor para o coeficiente a sejam nulas. O programa da figura 9.11 conte´m
o co´digo que resolve este problema.
A figura 9.12 ilustra o programa principal modificado para se dar a ideia de que as
func¸o\u2dces se comportam como expresso\u2dces aritme´ticas, ao contra´rio dos procedimentos,
que se comportam como comandos.
Na verdade, o programa principal poderia ser apenas o co´digo da figura 9.13,
sem preju´\u131jo do funcinamento, mas com bem menos legilidade e ainda por cima sem
tratamento do delta negativo. Apresentamos esta versa\u2dco apenas para ilustrar o uso
das func¸o\u2dces dentro de func¸o\u2dces, mas observamos que o ca´lculo do delta e´ feito duas
vezes.
122 CAPI´TULO 9. FUNC¸O\u2dcES E PROCEDIMENTOS
program raizes eq 2o grau ;
var a, b, c , delta , x1, x2: real ;
procedure ler (var a, b, c : real) ;
begin
{$i\u2212}
repeat
read (a , b, c) ;
until ( ioresult = 0) and (a <> 0) ;
{$i+}
end;
function calcula delta (a , b, c : real) : real ;
begin
calcula delta:= b\u2217b \u2212 4\u2217a\u2217c ;
end;
function menor raiz (a , b, delta : real) : real ;
begin
menor raiz:= (\u2212b \u2212 sqrt(delta))/(2\u2217a) ;
end;
function maior raiz (a ,