apostila
259 pág.

apostila


DisciplinaAlgoritmos e Estrutura de Dados I706 materiais7.917 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\u2dco da linguagem Pascal : in-
felizmente, o compilador na\u2dco aceita um para\u2c6metro do tipo array. Assim, a construc¸a\u2dco
seguinte gera um erro de compilac¸a\u2dco:
procedure ler (var v: array [1. .200] of real) ;
Para contornar este problema, a linguagem Pascal permite a definic¸a\u2dco de novos
tipos de dados baseados em outros tipos pre´-existentes. Isto se consegue com o uso
da declarac¸a\u2dco type.
type vetor= array [1. .200] of real ;
O que ocorre com o uso da declarac¸a\u2dco 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\u2dces, uso de constantes no
co´digo, comenta´rios no co´digo, . . . , far´\u131amos 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) ; (\u2217 leitura dos dados \u2217)
var i : integer ;
begin
for i := 1 to 10 do
read (w[ i ] ) ;
end;
procedure imprimir (var w: vetor) ; (\u2217 impressao dos dados \u2217)
var i : integer ;
begin
for i := 1 to 10 do
write (w[ i ] ) ;
end;
begin (\u2217 programa principal \u2217)
ler (v) ;
imprimir (v) ;
end.
Figura 10.7: Lendo e imprimindo, agora com procedimentos.
Agora estamos prontos para resolver o problema proposto no in´\u131cio deste cap´\u131tulo,
aquele de ler uma seque\u2c6ncia de nu´meros e imprim\u131´-los ao contra´rio. Uma vez que os
dados esta\u2dco carregados em memo´ria, apo´s a execuc¸a\u2dco 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\u2dco para percorrer o vetor do final
ao in´\u131cio. A figura 10.8 conte´m esta modificac¸a\u2dco. 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\u2dces importantes:
1. A leitura e´ feita obrigatoriamente usando-se passagem de para\u2c6metros por re-
fere\u2c6ncia. A impressa\u2dco 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\u2dco extra que pode custar caro, especial-
mente no caso em que os vetores sa\u2dco grandes. Imagine copiar, a toa, um milha\u2dco
de elementos. Assim, em geral, vetores sa\u2dco passados sempre por refere\u2c6ncia.
2. O co´digo seria generalizado facilmente se tive´ssemos passado como para\u2c6metro
o tamanho usado (ou u´til) do vetor, e na\u2dco o nu´mero fixo 10, ale´m do enderec¸o
dele. Neste caso, o co´digo da figura 10.9 seria a soluc¸a\u2dco mais elegante para o
problema. Observar que o tamanho do vetor e´ lido dentro do procedimento, o
que exige um para\u2c6metro por refere\u2c6ncia.
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) ; (\u2217 leitura \u2217)
var i : integer ;
begin
read (tam) ; (\u2217 1 <= tam<= 200, define o tamanho ut i l do vetor \u2217)
for i := 1 to tam do
read (w[ i ] ) ;
end;
procedure imprimir ao contrario (var w: vetor ; tam: integer) ; (\u2217 impressao \u2217)
var i : integer ;
begin
for i := tam donwto 1 do
write (w[ i ] ) ;
end;
begin (\u2217 programa principal \u2217)
ler (v, n) ;
imprimir ao contrario (v, n) ;
end.
Figura 10.9: Lendo e imprimindo ao contra´rio, versa\u2dco final.
Neste ponto esgotamos o assunto de ler e imprimir vetores e estamos prontos para
novos problemas cujas soluc¸o\u2dces requerem o uso de vetores, ou tornam o co´digo mais
elegante.
134 CAPI´TULO 10. ESTRUTURAS DE DADOS
Nas sec¸o\u2dces que seguem, vamos considerar dois vetores de tamanhos diferentes, um
de inteiros o outro de reais. Nas apresentac¸o\u2dces dos algoritmos vamos omitir sempre
que poss´\u131vel a redac¸a\u2dco dos cabec¸alhos dos programas e nos concentrar apenas na
soluc¸a\u2dco dos novos problemas, sempre usando func¸o\u2dces e procedimentos. As seguintes
definic¸o\u2dces sera\u2dco usadas ate´ o final deste cap´\u131tulo:
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\u2dco, antes de continuarmos. Quando usamos vetores, estamos
limitados ao tamanho dele, que deve ser conhecido em tempo de compilac¸a\u2dco! Isto pode
causar dificuldades na resoluc¸a\u2dco de problemas que envolvem um nu´mero desconhecido
de valores de entrada. Mas na\u2dco tem outro jeito a na\u2dco ser, em tempo de compilac¸a\u2dco, se
estimar um valor ma´ximo para o nu´mero de elementos no vetor e, durante a execuc¸a\u2dco,
testar se este valor nunca foi ultrapassado. Se o nu´mero for maior, enta\u2dco deve-se
modificar o tamanho do vetor e recompilar.
A questa\u2dco de qual o tamanho ideal para ser o escolhido na hora de compilar e´
questa\u2dco de bom-senso e envolve saber de qual aplicac¸a\u2dco se esta´ falando. Por exemplo,
se for um vetor para armazenar jogos da mega-sena, enta\u2dco 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\u2dco pares
Vamos retornar ao velho e conhecido problema de se ler uma massa de dados de
quantidade indefinida e imprimir apenas aqueles que sa\u2dco pares.
O programa da figura 10.10 ilustra uma procedure com uma poss´\u131vel soluc¸a\u2dco. 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\u2dco 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\u2dco pares.
10.1. VETORES 135
Aqui se faz uso da func¸a\u2dco booleana \u201ceh par\u201d, que foi estudada na sec¸a\u2dco 9.2.5. Com
isto conclu´\u131mos que os problemas sa\u2dco os mesmos, apenas o uso deles e´ ligeiramente
diferente por dois motivos: usa-se func¸o\u2dces ou procedimentos, e tambe´m se resolve
usando-se vetores. O resto na\u2dco muda.
Um problema que pode parecer o mesmo, mas na\u2dco e´, seria imprimir os elemen-
tos das posic¸o\u2dces pares do vetor, e na\u2dco mais os elementos cujos conteu´dos sa\u2dco 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´\u131da o seguinte: 12, 2, 0 e 18, que esta\u2dco
respectivamente nas posic¸o\u2dces 2, 6, 7 e 8 do vetor. Se, na linha 5 do programa, no´s
testarmos se o \u131´ndice e´ par (e na\u2dco o conteu´do):
i f eh par ( i ) then // no lugar de: i f eh par (v[ i ] ) then
enta\u2dco a sa´\u131da seria: 12, 23, 2, 18 e 21, respectivamente para os elementos das posic¸o\u2dces
2, 4, 6, 8 e 10 do vetor. Oberve com atenc¸a\u2dco esta diferenc¸a, e´ importante.
Como antes, a func¸a\u2dco \u201ceh par\u201d pode ser substitu´\u131da por qualquer outra, como
por exemplo, ser primo, se divis´\u131vel por n, pertencer a` seque\u2c6ncia