apostila

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 deste segmento, e´ preciso informar, ale´m do nome da varia´vel, uma segunda
informac¸a\u2dco: a posic¸a\u2dco (ou o deslocamento) dentro do espac¸o reservado.
Ora, sabemos que foram reservadas 200 posic¸o\u2dces, cada uma delas com espac¸o para
conter um nu´mero inteiro. Se quisermos escrever na quinta posic¸a\u2dco, basta informar
ao computador que o in´\u131cio do segmento e´ dado pela varia´vel V e que, antes de se
escrever, e´ preciso realizar um deslocamento de 5 posic¸o\u2dces, cada uma delas para um
inteiro. Isto da´ um deslocamento de 10 bytes. Apo´s esta informac¸a\u2dco, o valor pode ser
escrito. Se o desejo e´ escrever na de´cima quarta posic¸a\u2dco, o deslocamento deve ser de
14× 2 bytes, isto e´, 28 bytes.
Para se recuperar a informac¸a\u2dco, por exemplo para se imprimir, ou para se fazer
algum ca´lculo com estes dados, basta usar o mesmo processo: os dados sa\u2dco acessados
pelo nome da varia´vel e pelo deslocamento.
Este processo foi apresentado em muito baixo n´\u131vel. Como de costume, precisamos
de uma outra forma de representac¸a\u2dco de mais alto n´\u131vel. Isto e´, cada linguagem de
10.1. VETORES 127
programac¸a\u2dco que implementa a noc¸a\u2dco de vetores tem que encontrar