apostila
259 pág.

apostila

Disciplina:Algoritmos e Estrutura de Dados I542 materiais7.956 seguidores
Pré-visualização50 páginas
isto, vamos reescrever mais uma vez o
programa, desta vez usando procedimentos.

Antes disto, pore´m, e´ importante destacar uma limitac¸a˜o da linguagem Pascal : in-
felizmente, o compilador na˜o aceita um paraˆmetro do tipo array. Assim, a construc¸a˜o
seguinte gera um erro de compilac¸a˜o:

procedure ler (var v: array [1. .200] of real) ;

Para contornar este problema, a linguagem Pascal permite a definic¸a˜o de novos
tipos de dados baseados em outros tipos pre´-existentes. Isto se consegue com o uso
da declarac¸a˜o type.

type vetor= array [1. .200] of real ;

O que ocorre com o uso da declarac¸a˜o type e´ que o nome do tipo vetor passa a
ser conhecido pelo compilador, que por default so´ conhece os tipos pre´-definidos da
linguagem. O compilador Pascal foi um dos primeiros a permitir que o programador
pudesse definir seus pro´prios tipos.

132 CAPI´TULO 10. ESTRUTURAS DE DADOS

Assim, para reescrevermos o programa da figura 10.1 usando todo o nosso arse-
nal de conhecimentos adquiridos sobre procedimentos, func¸o˜es, uso de constantes no
co´digo, comenta´rios no co´digo, . . . , far´ıamos como apresentado na figura 10.7.

program ler e imprimir ao contrario ;
const min=1; max=200;
type vetor= array [min. .max] of real ;
var v: vetor ;

procedure ler (var w: vetor) ; (∗ leitura dos dados ∗)
var i : integer ;
begin

for i := 1 to 10 do
read (w[ i ] ) ;

end;

procedure imprimir (var w: vetor) ; (∗ impressao dos dados ∗)
var i : integer ;
begin

for i := 1 to 10 do
write (w[ i ] ) ;

end;

begin (∗ programa principal ∗)
ler (v) ;
imprimir (v) ;

end.

Figura 10.7: Lendo e imprimindo, agora com procedimentos.

Agora estamos prontos para resolver o problema proposto no in´ıcio deste cap´ıtulo,
aquele de ler uma sequeˆncia de nu´meros e imprimı´-los ao contra´rio. Uma vez que os
dados esta˜o carregados em memo´ria, apo´s a execuc¸a˜o do procedimento ler(v), podemos
manipular os dados da maneira que for necessa´rio. No nosso caso, para imprimir ao
contra´rio, basta modificar o procedimento de impressa˜o para percorrer o vetor do final
ao in´ıcio. A figura 10.8 conte´m esta modificac¸a˜o. Basta agora modificar o programa
principal trocando a chamada imprimir(v) por imprimir ao contrario(v).

procedure imprimir ao contrario (var w: vetor) ;
var i : integer ;
begin

for i := 10 donwto 1 do
write (w[ i ] ) ;

end;

Figura 10.8: Procedimento que imprime os elementos do vetor ao contra´rio.

10.1. VETORES 133

Algumas observac¸o˜es importantes:

1. A leitura e´ feita obrigatoriamente usando-se passagem de paraˆmetros por re-
fereˆncia. A impressa˜o pode usar passagem por valor. Contudo, conhecendo o
fato de que existe uma co´pia de elementos que e´ feita na pilha de memo´ria, isto
evidentemente provocara´ uma computac¸a˜o extra que pode custar caro, especial-
mente no caso em que os vetores sa˜o grandes. Imagine copiar, a toa, um milha˜o
de elementos. Assim, em geral, vetores sa˜o passados sempre por refereˆncia.

2. O co´digo seria generalizado facilmente se tive´ssemos passado como paraˆmetro
o tamanho usado (ou u´til) do vetor, e na˜o o nu´mero fixo 10, ale´m do enderec¸o
dele. Neste caso, o co´digo da figura 10.9 seria a soluc¸a˜o mais elegante para o
problema. Observar que o tamanho do vetor e´ lido dentro do procedimento, o
que exige um paraˆmetro por refereˆncia.

program ler e imprimir ao contrario ;
const min=0; max=50;
type vetor= array [min. .max] of real ;
var v: vetor ;

n: integer ;

procedure ler (var w: vetor ; var tam: integer) ; (∗ leitura ∗)
var i : integer ;
begin

read (tam) ; (∗ 1 <= tam<= 200, define o tamanho ut i l do vetor ∗)
for i := 1 to tam do

read (w[ i ] ) ;
end;

procedure imprimir ao contrario (var w: vetor ; tam: integer) ; (∗ impressao ∗)
var i : integer ;
begin

for i := tam donwto 1 do
write (w[ i ] ) ;

end;

begin (∗ programa principal ∗)
ler (v, n) ;
imprimir ao contrario (v, n) ;

end.

Figura 10.9: Lendo e imprimindo ao contra´rio, versa˜o final.

Neste ponto esgotamos o assunto de ler e imprimir vetores e estamos prontos para
novos problemas cujas soluc¸o˜es requerem o uso de vetores, ou tornam o co´digo mais
elegante.

134 CAPI´TULO 10. ESTRUTURAS DE DADOS

Nas sec¸o˜es que seguem, vamos considerar dois vetores de tamanhos diferentes, um
de inteiros o outro de reais. Nas apresentac¸o˜es dos algoritmos vamos omitir sempre
que poss´ıvel a redac¸a˜o dos cabec¸alhos dos programas e nos concentrar apenas na
soluc¸a˜o dos novos problemas, sempre usando func¸o˜es e procedimentos. As seguintes
definic¸o˜es sera˜o usadas ate´ o final deste cap´ıtulo:

const min r=0; max r=50;
min i=1; max i=10;

type vetor r= array [min r . .max r] of real ;
vetor i= array [ min i . . max i ] of integer ;

Uma u´ltima observac¸a˜o, antes de continuarmos. Quando usamos vetores, estamos
limitados ao tamanho dele, que deve ser conhecido em tempo de compilac¸a˜o! Isto pode
causar dificuldades na resoluc¸a˜o de problemas que envolvem um nu´mero desconhecido
de valores de entrada. Mas na˜o tem outro jeito a na˜o ser, em tempo de compilac¸a˜o, se
estimar um valor ma´ximo para o nu´mero de elementos no vetor e, durante a execuc¸a˜o,
testar se este valor nunca foi ultrapassado. Se o nu´mero for maior, enta˜o deve-se
modificar o tamanho do vetor e recompilar.

A questa˜o de qual o tamanho ideal para ser o escolhido na hora de compilar e´
questa˜o de bom-senso e envolve saber de qual aplicac¸a˜o se esta´ falando. Por exemplo,
se for um vetor para armazenar jogos da mega-sena, enta˜o o nu´mero 10 e´ suficiente.
Se for para guardar saldos de clientes do banco, melhor saber quantos clientes existem
hoje e estimar uma margem de erro que depende tambe´m do crescimento me´dio do
nu´mero de clientes nos u´ltimos anos. E assim por diante.

Imprimindo os que sa˜o pares

Vamos retornar ao velho e conhecido problema de se ler uma massa de dados de
quantidade indefinida e imprimir apenas aqueles que sa˜o pares.

O programa da figura 10.10 ilustra uma procedure com uma poss´ıvel soluc¸a˜o. A
leitura dos dados e´ muito similar ao que ja´ foi mostrado no exemplo anterior, basta
adaptar o tipo e dados vetor de reais para vetor de inteiros e por isto apresentamos
apenas o que e´ diferente. Observemos a similaridade deste programa com relac¸a˜o ao
co´digo apresentado na figura 9.3.

procedure imprimir pares (var v: vetor i ; tam: integer) ;
var i : integer ;
begin

for i := 1 to tam do
if eh par (v[ i ] ) then

write (v[ i ] ) ;
end;

Figura 10.10: Imprimindo os elementos do vetor que sa˜o pares.

10.1. VETORES 135

Aqui se faz uso da func¸a˜o booleana “eh par”, que foi estudada na sec¸a˜o 9.2.5. Com
isto conclu´ımos que os problemas sa˜o os mesmos, apenas o uso deles e´ ligeiramente
diferente por dois motivos: usa-se func¸o˜es ou procedimentos, e tambe´m se resolve
usando-se vetores. O resto na˜o muda.

Um problema que pode parecer o mesmo, mas na˜o e´, seria imprimir os elemen-
tos das posic¸o˜es pares do vetor, e na˜o mais os elementos cujos conteu´dos sa˜o pares.
Perceber esta diferenc¸a e´ fundamental no estudo de vetores. Consideremos o seguinte
vetor v com tamanho 10 como exemplo:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
15 12 27 23 7 2 0 18 19 21 ? ? ? ? ? . . . ? ? ? ?

O co´digo da figura 10.10 produziria como sa´ıda o seguinte: 12, 2, 0 e 18, que esta˜o
respectivamente nas posic¸o˜es 2, 6, 7 e 8 do vetor. Se, na linha 5 do programa, no´s
testarmos se o ı´ndice e´ par (e na˜o o conteu´do):

i f eh par ( i ) then // no lugar de: i f eh par (v[ i ] ) then

enta˜o a sa´ıda seria: 12, 23, 2, 18 e 21, respectivamente para os elementos das posic¸o˜es
2, 4, 6, 8 e 10 do vetor. Oberve com atenc¸a˜o esta diferenc¸a, e´ importante.

Como antes, a func¸a˜o “eh par” pode ser substitu´ıda por qualquer outra, como
por exemplo, ser primo, se divis´ıvel por n, pertencer a` sequeˆncia