apostila

de Fibonacci, ou
qualquer outra propriedade mais complexa que se queira.
Encontrando o menor de uma seque\u2c6ncia de nu´meros
Vamos considerar o problema de se ler uma seque\u2c6ncia de N > 1 nu´meros do teclado
e imprimir o menor deles. Ja´ sabemos resolve\u2c6-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\u2dco 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\u2dco 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\u2dco vamos explorar algoritmos ligeiramente mais sofisticados, envolvendo
noc¸o\u2dces novas sobre vetores1.
Somando vetores
Nesta sec¸a\u2dco 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\u2dco ta\u2dco novas, ja´ que sa\u2dco conceitos estudados no ensino me´dio.
10.1. VETORES 137
procedure soma vetores (var v, w, soma v w: vetor i ; tam: integer) ;
(\u2217 este procedimento considera que os dois vetores tem o mesmo tamanho \u2217)
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\u2c6metros: no caso de v e w, poder´\u131amos perfeitamente ter passado por valor, pois
na\u2dco sa\u2dco alterados no procedimento. Isto vale tambe´m para o tamanho do vetor. Mas
soma v w deve ser obrigatoriamente passado por refere\u2c6ncia.
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\u2dco 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\u2dco 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\u2dces 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\u2dces 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 ] \u2217 w[ i ] ;
prod escalar:= soma;
end;
Figura 10.14: Produto escalar de dois vetores.
Como procuramos mostrar, programar usando vetores, func¸o\u2dces e procedimentos
na\u2dco e´ muito diferente de se programar os algoritmos elementares tais como os que
foram estudados ate´ enta\u2dco. Pelo menos ate´ agora. A pro´xima sec¸a\u2dco vai apresentar
novas te´cnicas usando-se estes novos conceitos.
10.1.3 Busca em vetores
Nesta sec¸a\u2dco 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\u2dco onde este elemento se encontra.
Este problema e´ extremamente importante em computac¸a\u2dco e na\u2dco e´ dif´\u131cil imaginar
aplicac¸o\u2dces 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\u2dco importante que e´ estudado de diversas maneiras
ao longo de um curso de cie\u2c6ncia da computac¸a\u2dco. Em um curso introduto´rio iremos
estudar os mais elementares para o caso de vetores de reais ou inteiros.
Ao longo desta sec¸a\u2dco, 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\u2dces
ou procedimentos. A ideia e´, como tem sido ate´ aqui, inicar por algo trivial e evoluir
a qualidade da soluc¸a\u2dco.
No´s iremos convencionar que as func¸o\u2dces tera\u2dco sempre o mesmo proto´tipo, que e´
assim definido:
(\u2217 Recebe um valor x que deve ser procurado no vetor v que tem tamanho n. \u2217)
(\u2217 Se for encontrado , retorna a posicao do elemento , senao retorna zero . \u2217)
function busca (x: real ; var v: vetor r ; n: integer) : integer ;
10.1. VETORES 139
O algoritmo mais inge\u2c6nuo poss´\u131vel 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\u2dco.
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\u2dco da u´ltima ocorre\u2c6ncia. O algoritmo sempre faz n
comparac¸o\u2dces, por causa do comando for. Por isto diz-se que o nu´mero de comparac¸o\u2dces
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 \u201ccustar caro\u201d 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\u2dco), dentro do escopo de um comando for, o qual e´ controlado pela varia´vel n.
Logo, esta comparac¸a\u2dco sera´ executada sempre n vezes.
Apesar do algoritmo funcionar, ele faz comparac¸o\u2dces demais: mesmo quando o
elemento ja´ foi encontrado o vetor e´ percorrido ate´ o final. Obviamente ele poderia
parar na primeira ocorre\u2c6ncia, pois na\u2dco