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