Grátis
259 pág.

Denunciar
Pré-visualização | Página 42 de 50
∗) writeln ; end; Figura 10.43: Procedimento para imprimir uma unica coluna da matriz. 6 0 7 2 1 Outro exemplo interessante seria imprimir apenas os elementos da matriz que sa˜o pares, conforme mostrado na figura 10.44. procedure imprimir os pares(var w: matriz ; n,m: integer) ; var i , j : integer ; begin for i := 1 to n do begin for j:= 1 to m do if eh par (w[ i , j ] ) then write (w[ i , j ] ,’ ’) ; end; end; Figura 10.44: Procedimento para imprimir os elementos pares matriz. Considerando novamente a nossa matriz exemplo, ter´ıamos a seguinte sa´ıda: 4 6 2 0 0 2 8 2 4 0 0 Para finalizarmos esta sec¸a˜o inicial, apresentamos na figura 10.45 um co´digo que imprime os elementos cujos ı´ndices das linhas e das colunas sa˜o pares. Considerando novamente a nossa matriz exemplo, ter´ıamos a seguinte sa´ıda: 0 2 2 4 184 CAPI´TULO 10. ESTRUTURAS DE DADOS procedure imprimir as linhas e colunas pares(var w: matriz ; n,m: integer) ; var i , j : integer ; begin for i := 1 to n do begin for j:= 1 to m do if eh par ( i ) and eh par( j ) then write (w[ i , j ] ,’ ’) ; writeln ; end; end; Figura 10.45: Procedimento para imprimir os elementos cujos indices sa˜o pares. Encontrando o menor elemento de uma matriz Vamos retornar ao velho e conhecido problema de se determinar qual e´ o menor elemento de um conjunto de nu´meros em memo´ria, considerando que, desta vez, eles estara˜o armazenados em uma matriz. A figura 10.46 conte´m o co´digo que faz isto. Note a semelhanc¸a com os programas das sec¸o˜es anteriores. A te´cnica e´ a mesma: o primeiro elemento e´ considerado o menor de todos e depois a matriz tem que ser toda percorrida (todas as linhas e todas as colunas) para ver se tem outro elemento ainda menor. function achamenor (var w: matriz ; n,m: integer) : real ; var i , j : integer ; maior : real ; begin menor:= w[1 ,1 ] ; for i := 1 to n do for j:= 1 to m do if w[ i , j ] < menor then menor:= w[ i , j ] ; achamenor:= menor; end; Figura 10.46: Encontrando o menor elemento de uma matriz. Soma de matrizes Nesta sec¸a˜o vamos implementar o algoritmo que soma duas matrizes. Para isto pre- cisamos antes entender como funciona o processo. Sejam v e w duas matrizes. Para soma´-las, e´ preciso que elas tenham o mesmo tamanho. Isto posto, o algoritmo cria uma nova matriz v+w onde cada elemento i, j da nova matriz e´ a soma dos respectivos elementos v[i, j] e w[i, j]. O esquema e´ muito parecido com a soma de vetores, ja´ estudada, apenas, novamente, trata-se tambe´m da segunda dimensa˜o. 10.2. MATRIZES 185 Desta forma, o algoritmo que soma os dois vetores devera´, para cada par i, j fixo, somar os respectivos elementos em v e w e guardar em v + w. Variando i de 1 ate´ o nu´mero de linhas e j de 1 ate´ o nu´mero de colunas resolve o problema. O programa que implementa esta ideia e´ apresentado na figura 10.47. procedure soma matrizes (var v, w, soma v w: matriz ; n,m: integer) ; var i , j : integer ; begin (∗ n e m sao o numero de linhas e colunas , respectivamente ∗) for i := 1 to n do for j:= 1 to m do soma v w[ i , j ]:= v[ i , j ] + w[ i , j ] ; end; Figura 10.47: Somando duas matrizes. E´ interessante comparar com o procedimento que soma vetores, apresentado na figura 10.13. Se considerarmos que, no lac¸o interno controlado pelo j o i e´ fixo, enta˜o os dois procedimentos fazem a mesma operac¸a˜o de somar dois vetores! Multiplicac¸a˜o de matrizes Agora vamos resolver o problema da multiplicac¸a˜o de matrizes. Inicialmente vamos recordar como isto e´ feito. Do ponto de vista matema´tico cada elemento da matriz resultado da multiplicac¸a˜o de duas matrizes pode ser encarado como sendo o produto escalar de dois vetores formados por uma linha da primeira matriz e por uma coluna da segunda. Vamos considerar duas matrizes An×m e Bm×p. A multiplicac¸a˜o so´ pode ocorrer se o nu´mero de colunas da matriz A for igual ao nu´mero de linhas da matriz B. Isto por causa do produto escalar de vetores, que exige que os vetores tenham o mesmo tamanho. O resultado e´ uma matriz n × p. O produto escalar de vetores, conforme ja´ estudado, e´ o resultado da seguinte somato´ria: m∑ k=1 V [k]×W [k]. Vamos considerar duas matrizes A e B, fixando uma linha I na matriz A e uma coluna J na matriz B. Conforme ja´ mencionado, fixar linhas ou colunas em matrizes e´ o mesmo que trabalhar com vetores. Enta˜o, neste caso, o produto escalar da linha I da matriz A pela coluna J da matriz B e´ dado pela seguinte somato´ria: m∑ k=1 A[I, k]×B[k, J ]. O programa que realiza esta operac¸a˜o e´ uma adaptac¸a˜o simples do co´digo exibido na figura 10.14, que para fins dida´ticos e´ mostrado na figura 10.48. 186 CAPI´TULO 10. ESTRUTURAS DE DADOS begin (∗ considerando I e J fixos ∗) soma:= 0; for i := 1 to m do soma:= soma + A[ I ,k] ∗ B[k,J ] ; prod escalar:= soma; end; Figura 10.48: Produto escalar de uma linha da matriz por uma coluna da outra. Vejamos isto de forma ilustrada considerando as duas matrizes seguintes: A: 4 6 2 1 9 0 0 2 8 7 3 9 1 2 3 4 0 1 0 1 B: 2 3 4 5 0 0 0 7 7 1 0 9 O produto escalar da linha (terceira) pela coluna (segunda) em destaque e´ o re- sultado da seguinte operac¸a˜o: 8× 3 + 7× 0 + 3× 7 + 9× 0 = 45. Este resultado e´ o valor da linha 3 coluna 2 da matriz produto, isto e´, e´ o elemento AB[3,2]. Para se obter a resultado completo do produto de A por B, basta variar I nas linhas de A e J nas colunas de B. Isto e´ apresentado na figura 10.49. procedure multiplicacao matrizes (var A: matriz ; lin A , col A : integer ; var B: matriz ; lin B , col B : integer ; var AB: matriz ; var lin AB, col AB: integer ; var i , j , k: integer ; begin lin AB:= lin A ; col AB:= col B ; for i := 1 to lin A do for j:= 1 to col B do begin AB[ i , j ]:= 0; for i := 1 to m do AB[ i , j ]:= AB[ i , j ] + A[ i ,k] ∗ B[k, j ] ; end; end. Figura 10.49: Multiplicac¸a˜o de duas matrizes. 10.2.3 Procurando elementos em matrizes Nesta sec¸a˜o vamos apresentar alguns problemas de busca de elementos em matrizes. Busca em uma matriz O problema de busca em matrizes e´ similar ao caso dos vetores. O procedimento agora e´ quadra´tico, pois no pior caso a matriz inteira deve ser percorrida (caso em que o elemento na˜o esta´ na matriz). A figura 10.50 conte´m o co´digo para este problema. 10.2. MATRIZES 187 function busca (var w: matriz ; n,m: integer ; x: integer) : boolean; var i , j : integer ; achou: boolean; begin achou:= false ; i := 1; while ( i <= n) and not achou do begin j:= 1; while ( j <= m) and not achou do begin if w[ i , j ] = x then achou:= true ; j:= j + 1; end; i := i + 1; end; busca:= achou; end; Figura 10.50: Busca em uma matriz. As vezes e´ preciso saber as coordenadas i e j do elemento. A figura 10.51 mostra como adaptar a func¸a˜o anterior com duas modificac¸o˜es: a primeira e´ que deve-se usar um procedimento que retorna as duas coordenadas usando paraˆmetros por refereˆncia, pois func¸o˜es retornam apenas um u´nico valor. A outra diferenc¸a e´ que, quando o elemento e´ encontrado deve-se lembrar da linha e coluna correspondente. procedure acha pos elemento (var w: matriz ; n,m,x: integer ; var l , c : integer) ; var i , j : integer ; achou: boolean; begin (∗ trecho inicial omitido ∗) i f w[ i , j ] = x then begin (∗ quando acha o elemento , armazena as coordenadas ∗) achou:= true ; l := i ; c:= j ; end; (∗ trecho final omitido ∗) end; Figura 10.51: Busca em uma matriz, retornando as coordenadas (l,c). Um problema interessante e´ saber se uma matriz conte´m elementos repetidos. Basta varrer a matriz e, para cada elemento, saber se ele existe na matriz em posic¸a˜o diferente. Isto exige um aninhamento de quatro lac¸os! Um lac¸o duplo e´ necessa´rio