apostila

de Fibonacci, ou
qualquer outra propriedade mais complexa que se queira.
Encontrando o menor de uma sequeˆncia de nu´meros
Vamos considerar o problema de se ler uma sequeˆncia de N > 1 nu´meros do teclado
e imprimir o menor deles. Ja´ sabemos resolveˆ-lo sem o uso de vetores, conforme
ilustrado na figura 10.11.
program menor dos lidos ;
var N, i : integer ; x, menor: real ;
begin
read (N) ;
read (x) ;
menor:= x;
for i := 2 to N do
begin
read (x) ;
i f x < menor then
menor:= x;
end;
writeln (menor) ;
end;
Figura 10.11: Encontrando o menor de N nu´meros lidos, sem vetor.
136 CAPI´TULO 10. ESTRUTURAS DE DADOS
Vamos reimplementa´-lo em termos de uma func¸a˜o que considera que os elementos
digitados no teclado ja´ foram lidos em um vetor. A figura 10.12 permite percebermos
que a te´cnica usada foi rigorosamente a mesma: o primeiro nu´mero lido e´ considerado
o menor de todos. Na leitura dos dados subsequentes, quando um nu´mero ainda
menor e´ encontrado, atualiza-se a informac¸a˜o de quem e´ o menor de todos.
function menor dos lidos (var v: vetor r ; N: integer) : real ;
var i : integer ; x, menor: real ;
begin
menor:= v[1 ] ;
for i := 2 to N do
if v[ i ] < menor then
menor:= v[ i ] ;
menor dos lidos:= menor;
end;
Figura 10.12: Encontrando o menor de N nu´meros lidos, com vetor.
10.1.2 Soma e produto escalar de vetores
Nesta sec¸a˜o vamos explorar algoritmos ligeiramente mais sofisticados, envolvendo
noc¸o˜es novas sobre vetores1.
Somando vetores
Nesta sec¸a˜o vamos implementar o algoritmo que soma dois vetores. Para isto preci-
samos antes entender como funciona o processo.
Sejam v e w dois vetores. Para soma´-los, e´ preciso que eles tenham o mesmo
tamanho. Isto posto, o algoritmo cria um novo vetor v + w no qual cada elemento
(v + w)[i] do novo vetor e´ a soma dos respectivos elementos v[i] e w[i]. O esquema e´
conforme a figura seguinte, que apresenta dois vetores de 6 elementos cada:
1 2 3 4 5 6
v: 2 6 1 5 3 3
+ + + + + +
w: 1 3 2 4 3 5
= = = = = =
v+w: 3 9 3 9 6 8
Assim, o algoritmo que soma os dois vetores devera´, para cada i fixo, somar os
respectivos elementos em v e w e guardar em v + w. Variar i de 1 ate´ o tamanho do
vetor resolve o problema. O programa da figura 10.13 implementa esta ideia.
1Na˜o ta˜o novas, ja´ que sa˜o conceitos estudados no ensino me´dio.
10.1. VETORES 137
procedure soma vetores (var v, w, soma v w: vetor i ; tam: integer) ;
(∗ este procedimento considera que os dois vetores tem o mesmo tamanho ∗)
var i : integer ;
begin
for i := 1 to tam do
soma v w[ i ]:= v[ i ] + w[ i ] ;
end;
Figura 10.13: Somando dois vetores.
Importante notar que i e´ varia´vel local, isto e´, serve apenas para controlar o
comando for interno do procedimento. Tambe´m digno de nota e´ a passagem de
paraˆmetros: no caso de v e w, poder´ıamos perfeitamente ter passado por valor, pois
na˜o sa˜o alterados no procedimento. Isto vale tambe´m para o tamanho do vetor. Mas
soma v w deve ser obrigatoriamente passado por refereˆncia.
Se, por acaso, os dois vetores tivessem eventualmente tamanhos diferentes o proto´tipo
mudaria um pouco e poderia ser assim (desde que na implementac¸a˜o se teste se
tam v = tam w):
procedure soma vetores (var v: vetor i ; tam v: integer ;
var w: vetor i ; tam w: integer ;
var soma v w: vetor i ; tam soma: integer) ;
Produto escalar
Nesta sec¸a˜o vamos implementar o algoritmo que calcula o produto escalar de dois
vetores. Para isto precisamos antes entender como funciona o processo.
Sejam v e w dois vetores. Para se obter o produto escalar e´ preciso que eles tenham
o mesmo tamanho. Isto posto, o algoritmo gera um nu´mero real (ou inteiro, depende
do tipo de dados do vetor) obtido pela soma das multiplicac¸o˜es de cada elemento i
dos vetores dados, respectivamente. O esquema e´ conforme a figura seguinte, que
apresenta dois vetores de 6 elementos cada:
1 2 3 4 5 6
v: 2 6 1 0 3 3
× × × × × ×
w: 1 0 2 4 3 5
= = = = = =
2 0 2 0 9 15
Os nu´meros obtidos a partir das multiplicac¸o˜es para todos os i fixos devem ser
somados: 2 + 0 + 2 + 0 + 9 + 15 = 28. Logo, 28 e´ o produto escalar de v e w.
138 CAPI´TULO 10. ESTRUTURAS DE DADOS
Assim, o algoritmo que calcula o produto escalar de dois vetores devera´, para cada
i fixo, multiplicar os respectivos elementos em v e w e usar a te´cnica do acumulador
para armazenar as somas parciais. Variar i de 1 ate´ o tamanho do vetor resolve o
problema. O programa que implementa esta ideia e´ apresentado na figura 10.14.
function prod escalar (var v, w: vetor r ; tam: integer) : real ;
var i : integer ;
soma: real ;
begin
soma:= 0;
for i := 1 to tam do
soma:= soma + v[ i ] ∗ w[ i ] ;
prod escalar:= soma;
end;
Figura 10.14: Produto escalar de dois vetores.
Como procuramos mostrar, programar usando vetores, func¸o˜es e procedimentos
na˜o e´ muito diferente de se programar os algoritmos elementares tais como os que
foram estudados ate´ enta˜o. Pelo menos ate´ agora. A pro´xima sec¸a˜o vai apresentar
novas te´cnicas usando-se estes novos conceitos.
10.1.3 Busca em vetores
Nesta sec¸a˜o vamos estudar alguns algoritmos para o importante problema de busca
em vetores. Em outras palavras, estamos interessados em saber se um dado elemento
x e´ um dos elementos de um vetor v e, caso seja, tambe´m podemos querer saber a
posic¸a˜o onde este elemento se encontra.
Este problema e´ extremamente importante em computac¸a˜o e na˜o e´ dif´ıcil imaginar
aplicac¸o˜es no nosso dia a dia. Por exemplo, localizar um livro na biblioteca, localizar
um filme na videolocadora, saber se um dado CPF esta´ cadastrado em alguma lista
de cheques, e por ai vai.
O tema de busca em vetores e´ ta˜o importante que e´ estudado de diversas maneiras
ao longo de um curso de cieˆncia da computac¸a˜o. Em um curso introduto´rio iremos
estudar os mais elementares para o caso de vetores de reais ou inteiros.
Ao longo desta sec¸a˜o, vamos considerar sempre que um dado vetor v ja´ foi lido em
memo´ria de alguma maneira. Assim, vamos elaborar algoritmos na forma de func¸o˜es
ou procedimentos. A ideia e´, como tem sido ate´ aqui, inicar por algo trivial e evoluir
a qualidade da soluc¸a˜o.
No´s iremos convencionar que as func¸o˜es tera˜o sempre o mesmo proto´tipo, que e´
assim definido:
(∗ Recebe um valor x que deve ser procurado no vetor v que tem tamanho n. ∗)
(∗ Se for encontrado , retorna a posicao do elemento , senao retorna zero . ∗)
function busca (x: real ; var v: vetor r ; n: integer) : integer ;
10.1. VETORES 139
O algoritmo mais ingeˆnuo poss´ıvel e´ mostrado na figura 10.15.
function busca (x: real ; var v: vetor r ; n: integer) : integer ;
var i : integer ;
begin
busca:= 0;
for i := 1 to n do
if v[ i ] = x then
busca:= i ;
end;
Figura 10.15: Busca em vetores, primeira versa˜o.
Este algoritmo sempre acha o elemento x em v se ele estiver presente, pois ele
varre todo o vetor comparando cada elemento com x. Caso x esteja presente duas
vezes ou mais, ele retorna a posic¸a˜o da u´ltima ocorreˆncia. O algoritmo sempre faz n
comparac¸o˜es, por causa do comando for. Por isto diz-se que o nu´mero de comparac¸o˜es
que o algoritmo realiza e´ proporcional ao tamanho do vetor.
De fato, em qualquer programa sempre e´ interessante analisar o que custa mais
caro no co´digo. Entendemos por “custar caro” como sendo o comando que e´ executado
o maior nu´mero de vezes durante uma rodada do programa.
Neste caso, temos um comando if, que faz um teste de igualdade (uma com-
parac¸a˜o), dentro do escopo de um comando for, o qual e´ controlado pela varia´vel n.
Logo, esta comparac¸a˜o sera´ executada sempre n vezes.
Apesar do algoritmo funcionar, ele faz comparac¸o˜es demais: mesmo quando o
elemento ja´ foi encontrado o vetor e´ percorrido ate´ o final. Obviamente ele poderia
parar na primeira ocorreˆncia, pois na˜o