apostila

b, delta : real) : real ;
begin
maior raiz:= (−b + sqrt(delta))/(2∗a) ;
end;
begin (∗ programa principal ∗)
ler (a , b, c) ; (∗ garante−se que a nao eh nulo ∗)
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 (’raizes complexas’) ;
end.
Figura 9.11: Calculando ra´ızes de equac¸a˜o do segundo grau.
9.4. CA´LCULO DO MDC PELA DEFINIC¸A˜O 123
begin (∗ programa principal ∗)
ler (a , b, c) ; (∗ garante−se que a nao eh nulo ∗)
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 (’raizes complexas’) ;
end.
Figura 9.12: Calculando ra´ızes de equac¸a˜o do segundo grau.
begin (∗ programa principal ∗)
ler (a , b, c) ; (∗ garante−se que a nao eh nulo ∗)
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´ızes de equac¸a˜o do segundo grau.
Terminamos aqui a primeira parte do curso, no qual as noc¸o˜es fundamentais sobre
algoritmos esta˜o 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˜ES E PROCEDIMENTOS
9.5 Exerc´ıcios
1. Fazer uma func¸a˜o em Pascal que receba como paraˆmetro dois nu´meros intei-
ros na˜o nulos e retorne TRUE se um for o contra´rio do outro e FALSE em
caso contra´rio. Isto e´, se os paraˆmetros forem 123 (cento e vinte e treˆs) e 321
(trezentos e vinte e um), deve-se retornar TRUE. Usar apenas operac¸o˜es sobre
inteiros.
2. Fazer uma func¸a˜o em Pascal que receba como paraˆmetro 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´ıda deve ser 17.
3. Fazer uma func¸a˜o em Pascal que receba como paraˆmetro um nu´mero inteiro e
retorne TRUE se ele for primo e FALSE em caso contra´rio. Use esta func¸a˜o
para imprimir todos os nu´meros primos entre 0 e 1000.
4. Implemente func¸o˜es para seno e cosseno conforme definidos em cap´ıtulos an-
teriores e use-as em uma terceira func¸a˜o 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˜o de nu´meros inteiros.
Os nu´meros gerados devera˜o ser impressos em um arquivo texto.
6. Fac¸a uma func¸a˜o em Pascal que some dois nu´meros representando horas. A
entrada deve ser feita da seguinte maneira:
12 52
7 13
A sa´ıda deve ser assim:
12:52 + 7:13 = 20:05
7. Fac¸a uma func¸a˜o que receba como paraˆmetros seis varia´veis DIA1, MES1 e
ANO1, DIA2, MES2 e ANO2, todas do tipo integer. Considerando que cada
trinca de dia, meˆs e ano representa uma data, a func¸a˜o deve retornar true se a
primeira data for anterior a` segunda e false caso contra´rio.
Cap´ıtulo 10
Estruturas de dados
Ate´ aqui apresentamos as te´cnicas ba´sicas para construc¸a˜o de algoritmos, incluindo as
noc¸o˜es de func¸o˜es e procedimentos. Podemos dizer que e´ poss´ıvel, com este conteu´do,
programar uma vasta colec¸a˜o de algoritmos, inclusive alguns com alta complexidade.
Contudo, o estudo geral da disciplina de “Algoritmos e Estrurutas de Dados”
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˜o de dados em memo´ria permite a construc¸a˜o de algoritmos sofistica-
dos e eficientes. Neste textp estudaremos treˆs estruturas de dados elementares. Sa˜o
elas:
• vetores (ou array unidimencional);
• matrizes (ou array multidimencional);
• registros.
Nas sec¸o˜es seguintes explicaremos cada uma delas, sempre motivados por proble-
mas que exigem seu uso ou que facilitam a implementac¸a˜o. Tambe´m veremos nos
pro´ximos cap´ıtulos algumas estruturas que misturam estas treˆs.
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´ıda: 9, 4, 3, 5, 2.
Este tipo de problema e´ imposs´ıvel de ser resolvido com o uso de apenas uma
varia´vel pois, quando se leˆ 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˜o! O que faz com que simplesmente
na˜o seja poss´ıvel 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˜o de memo´ria em algum
enderec¸o da RAM (conforme sabemos pelo modelo Von Neumann). Um inteiro exige
(dependendo da implementac¸a˜o) 2 bytes.
Mas, digamos que e´ preciso alocar espac¸o para 100 nu´meros inteiros. Sabendo
que cada um deles ocupa 2 bytes, precisar´ıamos 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˜o 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˜es
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˜o:
var V: array[1. .200] of integer ;
Em Pascal isto resulta na alocac¸a˜o 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˜o serve. E´ preciso uma outra informac¸a˜o
adicional para se dizer em qual das 200 posic¸o˜es se quer escrever.
Na verdade, a varia´vel V aponta para o in´ıcio 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˜o: a posic¸a˜o (ou o deslocamento) dentro do espac¸o reservado.
Ora, sabemos que foram reservadas 200 posic¸o˜es, cada uma delas com espac¸o para
conter um nu´mero inteiro. Se quisermos escrever na quinta posic¸a˜o, basta informar
ao computador que o in´ıcio do segmento e´ dado pela varia´vel V e que, antes de se
escrever, e´ preciso realizar um deslocamento de 5 posic¸o˜es, cada uma delas para um
inteiro. Isto da´ um deslocamento de 10 bytes. Apo´s esta informac¸a˜o, o valor pode ser
escrito. Se o desejo e´ escrever na de´cima quarta posic¸a˜o, o deslocamento deve ser de
14× 2 bytes, isto e´, 28 bytes.
Para se recuperar a informac¸a˜o, por exemplo para se imprimir, ou para se fazer
algum ca´lculo com estes dados, basta usar o mesmo processo: os dados sa˜o acessados
pelo nome da varia´vel e pelo deslocamento.
Este processo foi apresentado em muito baixo n´ıvel. Como de costume, precisamos
de uma outra forma de representac¸a˜o de mais alto n´ıvel. Isto e´, cada linguagem de
10.1. VETORES 127
programac¸a˜o que implementa a noc¸a˜o de vetores tem que encontrar