apostila
259 pág.

apostila

Disciplina:Algoritmos e Estrutura de Dados I542 materiais7.956 seguidores
Pré-visualização50 páginas
o co´digo global independente.
No caso, o programador usou diretivas do compilador para alterar o comportamento
padra˜o que aborta o programa se o usua´rio digitar um tipo na˜o esperado. Trata corre-
tamente o erro e quando tudo esta´ certo, termina o procedimento. Importante notar
que, para leitura de dados, o paraˆmetro tem que ser passado por refereˆncia, e na˜o por
valor, sena˜o o valor seria lido em uma co´pia da varia´vel do programa principal.

Considerac¸o˜es similares sa˜o feitas para a outra func¸a˜o e o procedimento, ambos
possuem co´digo pro´prio e fazem com que a atenc¸a˜o do programador fique voltada
exclusivamente para o subproblema da vez. Desde que o proto´tipo da func¸a˜o ou pro-
cedimento esteja corretamente especificado, na˜o ha´ problema em se alterar o co´digo
interno. Notamos tambe´m que no caso da func¸a˜o, foram usadas varia´veis locais para
aux´ılio no ca´lculo do d´ıgito verificador. Tudo para o bem da clareza do co´digo prin-
cipal. Se um dia mudarem a definic¸a˜o de como se calcula o d´ıgito verificador, basta
alterar a func¸a˜o que o programa principal continuara´ a funcionar corretamente.

Na u´ltima func¸a˜o e´ importante notar a passagem de paraˆmetros por valor. Isto
permitiu o lac¸o que controla o loop interno usar o pro´prio paraˆmetro como condic¸a˜o
de parada, pois ele e´ dividido por 10 a cada iterac¸a˜o. Se o paraˆmetro fosse passado
por refereˆncia isto na˜o poderia ser feito, pois estar´ıamos estragando o valor da varia´vel
que sera´ ainda usada no programa principal.

Ainda uma u´ltima observac¸a˜o, no procedimento que separa o nu´mero de seu d´ıgito
verificador, atentar para a sintaxe, em Pascal, que se usa quando se quer passar dois
paraˆmetros do mesmo tipo, um por valor e outro por refereˆncia. No caso, eles devem
ser separados pelo s´ımbolo do ponto-e-v´ırgula, o segundo deles contendo a palavra var
para indicar refereˆncia.

9.4. CA´LCULO DO MDC PELA DEFINIC¸A˜O 119

9.4 Ca´lculo do MDC pela definic¸a˜o

Nesta sec¸a˜o vamos revisitar o ca´lculo do MDC pela definic¸a˜o estudado na sec¸a˜o 8.5.
Deixamos propositalmente em aberto a questa˜o 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 ı´mpares.

Na verdade, os quatro trechos de co´digo esta˜o 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 ı´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˜o.

Esta convenc¸a˜o, em Pascal, e´ dada pelo proto´tipo de uma func¸a˜o que e´ constitu´ıdo
por treˆs paraˆmetros: o nome da func¸a˜o, 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˜o do MDC para receber a menor
poteˆncia do primo sendo calculado, na primeira vez e´ o 2, nas outras vezes e´ um primo
ı´mpar.

Basta criarmos um segundo proto´tipo de func¸a˜o que calcule a poteˆncia 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˜o conforme mostra a figura 9.8.

Observamos que o uso de func¸o˜es e procedimentos permite muita flexibilidade ao
programador, pois ele pode alterar o co´digo da func¸o˜es, se quiser, tornando-as mais
eficientes (caso na˜o fossem) sem que haja efeito colateral no programa principal. As
figuras 9.9 e 9.10 mostram sugesto˜es de co´digo para as func¸o˜es.

Na verdade, este co´digo na˜o e´ muito apropriado, pois exige um comportamento na˜o
muito elegante na func¸a˜o num vezes que divide, ela tem o efeito colateral de alterar
o valor da varia´vel n, o que na˜o e´ natural dado o nome da func¸a˜o. Deveria apenas
contar o nu´mero de vezes que divide e na˜o fazer mais nada. O problema na˜o 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˜ES E PROCEDIMENTOS

program mdcpeladefinicao ; (∗ pela definicao de mdc ∗)
var

a, b, primo, mdc: longint ;
cont a , cont b , menor cont : integer ;

function num vezes que divide(p: integer ; var n: longint) : integer ;
(∗ codigo da funcao num vezes que divide ∗)

function potencia(n,p : integer) : integer ;
(∗ codigo da funcao potencia ∗)

begin (∗ programa principal ∗)
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 ∗ potencia(2 ,menor cont) ;
writeln (’mdc= ’ ,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 ∗ potencia(primo,menor cont) ;

primo:= primo + 2;
end;
writeln (mdc) ;

end.

Figura 9.8: Calcula MDC entre a e b pela definic¸a˜o usando func¸o˜es.

9.4. CA´LCULO DO MDC PELA DEFINIC¸A˜O 121

function num vezes que divide(p: integer ; var n: longint) : integer ;
var cont : integer ;
begin

(∗ descobre quantas vezes o 2 divide as duas entradas ∗)
cont:= 0;
while n mod p = 0 do
begin

cont:= cont + 1;
n:= n div p;

end;
writeln (’num_vezes_que_divide= ’ ,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 ∗ n;
i:= i + 1;

end;
writeln (’potencia= ’ ,pot) ;
potencia:= pot ;

end;

Figura 9.10: Calcula a poteˆncia de um nu´mero elevado a outro.

9.4.1 Calculando ra´ızes de equac¸o˜es 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˜o do segundo grau ax2 + bx + c = 0 e
imprimir as ra´ızes calculadas pela fo´rmula de Ba´skara. O programa deve imprimir
mensagens corretas no caso de na˜o haverem ra´ızes reais bem como na˜o 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˜es se comportam como expresso˜es 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´ıjo do funcinamento, mas com bem menos legilidade e ainda por cima sem
tratamento do delta negativo. Apresentamos esta versa˜o apenas para ilustrar o uso
das func¸o˜es dentro de func¸o˜es, mas observamos que o ca´lculo do delta e´ feito duas
vezes.

122 CAPI´TULO 9. FUNC¸O˜ES E PROCEDIMENTOS

program raizes eq 2o grau ;
var a, b, c , delta , x1, x2: real ;

procedure ler (var a, b, c : real) ;
begin

{$i−}
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∗b − 4∗a∗c ;
end;

function menor raiz (a , b, delta : real) : real ;
begin

menor raiz:= (−b − sqrt(delta))/(2∗a) ;
end;

function maior raiz (a ,