ALGORITMOS E ESTRUTURAS DE DADOS I
259 pág.

ALGORITMOS E ESTRUTURAS DE DADOS I


DisciplinaAlgoritmos e Estrutura de Dados I708 materiais7.919 seguidores
Pré-visualização50 páginas
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 , b, delta : real) : real ;
begin
maior raiz:= (\u2212b + sqrt(delta))/(2\u2217a) ;
end;
begin (\u2217 programa principal \u2217)
ler (a , b, c) ; (\u2217 garante\u2212se que a nao eh nulo \u2217)
delta:= calcula delta (a , b, c) ;
i f delta >= 0 then
begin
x1:= menor raiz (a , b, delta) ;
writeln (x1) ;
x2:= maior raiz (a , b, delta) ;
writeln (x2) ;
end
else
writeln (\u2019raizes complexas\u2019) ;
end.
Figura 9.11: Calculando ra´\u131zes de equac¸a\u2dco do segundo grau.
9.4. CA´LCULO DO MDC PELA DEFINIC¸A\u2dcO 123
begin (\u2217 programa principal \u2217)
ler (a , b, c) ; (\u2217 garante\u2212se que a nao eh nulo \u2217)
delta:= calcula delta (a , b, c) ;
i f delta >= 0 then
begin
writeln (menor raiz (a , b, delta) , maior raiz (a , b, delta)) ;
end
else
writeln (\u2019raizes complexas\u2019) ;
end.
Figura 9.12: Calculando ra´\u131zes de equac¸a\u2dco do segundo grau.
begin (\u2217 programa principal \u2217)
ler (a , b, c) ; (\u2217 garante\u2212se que a nao eh nulo \u2217)
writeln (menor raiz (a , b, calcula delta (a ,b, c)) ,
maior raiz (a , b, calcula delta (a ,b, c))) ;
end.
Figura 9.13: Calculando ra´\u131zes de equac¸a\u2dco do segundo grau.
Terminamos aqui a primeira parte do curso, no qual as noc¸o\u2dces fundamentais sobre
algoritmos esta\u2dco estabelecidas. Nos pro´ximos estudaremos as principais estruturas de
dados ba´sicas para um curso introduto´rio de algoritmos.
124 CAPI´TULO 9. FUNC¸O\u2dcES E PROCEDIMENTOS
9.5 Exerc´\u131cios
1. Fazer uma func¸a\u2dco em Pascal que receba como para\u2c6metro dois nu´meros intei-
ros na\u2dco nulos e retorne TRUE se um for o contra´rio do outro e FALSE em
caso contra´rio. Isto e´, se os para\u2c6metros forem 123 (cento e vinte e tre\u2c6s) e 321
(trezentos e vinte e um), deve-se retornar TRUE. Usar apenas operac¸o\u2dces sobre
inteiros.
2. Fazer uma func¸a\u2dco em Pascal que receba como para\u2c6metro um nu´mero inteiro
representando um nu´mero bina´rio e retorne seu valor equivalente em decimal.
Por exemplo, se a entrada for 10001, a sa´\u131da deve ser 17.
3. Fazer uma func¸a\u2dco em Pascal que receba como para\u2c6metro um nu´mero inteiro e
retorne TRUE se ele for primo e FALSE em caso contra´rio. Use esta func¸a\u2dco
para imprimir todos os nu´meros primos entre 0 e 1000.
4. Implemente func¸o\u2dces para seno e cosseno conforme definidos em cap´\u131tulos an-
teriores e use-as em uma terceira func¸a\u2dco que calcule a tangente. O programa
principal deve imprimir os valores de tg(x) para um certo valor fornecido pelo
usua´rio.
5. Implemente um procedimento para gerar mais de um milha\u2dco de nu´meros inteiros.
Os nu´meros gerados devera\u2dco ser impressos em um arquivo texto.
6. Fac¸a uma func¸a\u2dco em Pascal que some dois nu´meros representando horas. A
entrada deve ser feita da seguinte maneira:
12 52
7 13
A sa´\u131da deve ser assim:
12:52 + 7:13 = 20:05
7. Fac¸a uma func¸a\u2dco que receba como para\u2c6metros seis varia´veis DIA1, MES1 e
ANO1, DIA2, MES2 e ANO2, todas do tipo integer. Considerando que cada
trinca de dia, me\u2c6s e ano representa uma data, a func¸a\u2dco deve retornar true se a
primeira data for anterior a` segunda e false caso contra´rio.
Cap´\u131tulo 10
Estruturas de dados
Ate´ aqui apresentamos as te´cnicas ba´sicas para construc¸a\u2dco de algoritmos, incluindo as
noc¸o\u2dces de func¸o\u2dces e procedimentos. Podemos dizer que e´ poss´\u131vel, com este conteu´do,
programar uma vasta colec¸a\u2dco de algoritmos, inclusive alguns com alta complexidade.
Contudo, o estudo geral da disciplina de \u201cAlgoritmos e Estrurutas de Dados\u201d
envolve algoritmos que trabalham dados organizados em memo´ria de maneira mais
sofisticada do que as simples varia´veis ba´sicas que foram estudadas ate´ o momento.
E´ algo mais ou menos parecido como manter um guarda-roupas organizado no lugar
de um monte de coisas atiradas no meio do quarto de qualquer jeito.
A organizac¸a\u2dco de dados em memo´ria permite a construc¸a\u2dco de algoritmos sofistica-
dos e eficientes. Neste textp estudaremos tre\u2c6s estruturas de dados elementares. Sa\u2dco
elas:
\u2022 vetores (ou array unidimencional);
\u2022 matrizes (ou array multidimencional);
\u2022 registros.
Nas sec¸o\u2dces seguintes explicaremos cada uma delas, sempre motivados por proble-
mas que exigem seu uso ou que facilitam a implementac¸a\u2dco. Tambe´m veremos nos
pro´ximos cap´\u131tulos algumas estruturas que misturam estas tre\u2c6s.
10.1 Vetores
Para motivar, vamos considerar o problema seguinte: ler uma certa quantidade de
valores inteiros e os imprimir na ordem inversa da leitura. Isto e´, se os dados de
entrada forem: 2, 5, 3, 4, 9, queremos imprimir na sa´\u131da: 9, 4, 3, 5, 2.
Este tipo de problema e´ imposs´\u131vel de ser resolvido com o uso de apenas uma
varia´vel pois, quando se le\u2c6 o segundo nu´mero, ja´ se perdeu o primeiro da memo´ria.
Exigiria o uso de tantas varia´veis quantos fossem os dados de entrada, mas notem que
isto deve ser conhecido em tempo de compilac¸a\u2dco! O que faz com que simplesmente
na\u2dco seja poss´\u131vel resolver este problema para uma quantidade indefinida de valores.
125
126 CAPI´TULO 10. ESTRUTURAS DE DADOS
De fato, quando se aloca, por exemplo, um nu´mero inteiro em uma varia´vel de
nome a, o que ocorre e´ que o computador reserva uma posic¸a\u2dco de memo´ria em algum
enderec¸o da RAM (conforme sabemos pelo modelo Von Neumann). Um inteiro exige
(dependendo da implementac¸a\u2dco) 2 bytes.
Mas, digamos que e´ preciso alocar espac¸o para 100 nu´meros inteiros. Sabendo
que cada um deles ocupa 2 bytes, precisar´\u131amos encontrar uma maneira de reservar
100 × 2 = 200 bytes e fazer com que este espac¸o de memo´ria pudesse ser acessado
tambe´m por um u´nico enderec¸o, ou em outras palavras, por uma u´nica varia´vel.
Os vetores sa\u2dco estruturas de dados que permitem o acesso a uma grande quantidade
de dados em memo´ria usando-se apenas um nome de varia´vel. Esta varia´vel especial
e´ declarada de tal maneira que o programador passa a ter acesso a` muitas posic¸o\u2dces
de memo´ria, de maneira controlada.
Sem ainda entrar em detalhes da linguagem Pascal, vamos tentar entender o pro-
cesso.
Como funciona isto em memo´ria?
Seguindo no exemplo de se alocar 200 espac¸os em memo´ria para nu´meros inteiros,
suponhamos que o seguinte comando faz esta alocac¸a\u2dco:
var V: array[1. .200] of integer ;
Em Pascal isto resulta na alocac¸a\u2dco de 200 vezes 2 bytes. Pela varia´vel V temos o
controle deste espac¸o.
O problema e´ como se faz para se escrever um valor qualquer neste espac¸o. Outro
problema e´ onde se escreve, ja´ que temos 200 possibilidades de escolha. O simples uso
da varia´vel, como esta´vamos acostumados, na\u2dco serve. E´ preciso uma outra informac¸a\u2dco
adicional para se dizer em qual das 200 posic¸o\u2dces se quer escrever.
Na verdade, a varia´vel V aponta para o in´\u131cio do segmento reservado, da mesma
maneira que se fazia para varia´veis ba´sicas ja´ estudadas. Para se escrever em algum
lugar