para se percorrer a matriz por completo, e depois um outro lac¸o duplo para cada elemento para se saber se ele se repete. Isto resulta em um algoritmo de ordem de n4 para uma matriz quadrada de ordem n, para o pior caso. 188 CAPI´TULO 10. ESTRUTURAS DE DADOS Para completar o grau de dificuldade, queremos parar o processamento ta˜o logo um elemento repetido seja encontrado. O co´digo final esta´ ilustrado na figura 10.52. function tem repetidos (var w: matriz ; n,m: integer) : boolean; var i , j , cont , p, q: integer ; repetiu : boolean; begin repetiu:= false ; i := 1; while ( i <= n) and not repetiu do begin j:= 1; while ( j <= m) and not repetiu do begin p:= 1; while (p<= n) and not repetiu do begin q:= 1; while (q<= m) and not repetiu do begin if (w[p,q] = w[ i , j ] ) and ((p <> i ) or (q <> j ) ) then repetiu:= true ; q:= q + 1; end; p:= p + 1; end; j:= j + 1; end; i := i + 1; end; tem repetidos:= repetiu ; end; Figura 10.52: Verifica se uma matriz tem elementos repetidos. 10.2.4 Inserindo uma coluna em uma matriz Vamos considerar o problema de receber uma matriz de dimenso˜es n×m e um vetor de n elementos e inserir o vetor como uma coluna adicional na matriz, que ficara´ com dimenso˜es n×m+ 1. Por exemplo, consideremos a nossa matriz exemplo e o seguinte vetor: 1 2 3 4 1 4 6 2 1 2 9 0 0 2 3 8 7 3 9 4 1 2 3 4 5 0 1 0 1 1 2 3 4 5 7 6 5 4 3 10.2. MATRIZES 189 Inicialmente vamos apenas inserir o vetor apo´s a u´ltima coluna, isto e´, o vetor sera´ a u´ltima coluna da nova matriz, tal como na figura seguinte, de ordem 5 × 5 (vetor inserido esta´ em negrito na figura): 1 2 3 4 5 1 4 6 2 1 7 2 9 0 0 2 6 3 8 7 3 9 5 4 1 2 3 4 4 5 0 1 0 1 3 O procedimento mostrado na figura 10.53 faz esta operac¸a˜o. procedure insere coluna no fim (var w: matriz ; v: vetor ; var n,m: integer) ; (∗ recebe uma matriz e um vetor e insere o vetor como ultima coluna da matriz ∗) var i : integer ; begin for i := 1 to n do w[ i ,m+1] := v[ i ] ; (∗ m+1 eh fixo , queremos sempre a ultima coluna ∗) m:= m + 1; (∗ altera o numero de colunas ∗) end; Figura 10.53: Insere um vetor como u´ltima coluna de uma matriz. Um problema mais dif´ıcil seria se quise´ssemos inserir o vetor em alguma coluna que na˜o fosse a u´ltima da matriz. O exemplo seguinte mostra nossa matriz de exemplo com o vetor inserido na coluna 2. 1 2 3 4 5 1 4 7 6 2 1 2 9 6 0 0 2 3 8 5 7 3 9 4 1 4 2 3 4 5 0 3 1 0 1 Neste caso, tal como no caso dos vetores, ter´ıamos que abrir espac¸o na matriz antes de inserir o vetor. Esta e´ uma operac¸a˜o bastante custosa, pois temos que mover va´rias colunas para frente, cada uma delas move n elementos para frente. O algoritmo apresentado na figura 10.54 mostra estes dois passos, um que abre espac¸o o outro que insere o vetor no espac¸o aberto. Para inserir linhas em uma matriz o procedimento e´ ana´logo. 190 CAPI´TULO 10. ESTRUTURAS DE DADOS procedure insere coluna k (var w: matriz ; v: vetor ; var n,m: integer , K: integer) ; (∗ recebe uma matriz e um vetor e insere o vetor na coluna K da matriz ∗) var i : integer ; begin (∗ primeiro abre espaco ∗) for j:= m downto K do (∗ para cada coluna , iniciando na ultima ∗) for i := 1 to n do (∗ move elementos uma coluna para frente ∗) w[ i , j+1]:= w[ i , j ] ; (∗ depois insere na coluna K ∗) for i := 1 to n do w[ i ,K] := v[ i ] ; (∗ K eh fixo , queremos sempre a K−esima coluna ∗) m:= m + 1; (∗ altera o numero de colunas ∗) end; Figura 10.54: Insere um vetor como K-e´sima coluna de uma matriz. 10.2.5 Aplicac¸o˜es de matrizes em imagens Nosso objetivo nesta sec¸a˜o e´ mostrar como podemos fazer modificac¸o˜es em imagens digitais no formato PGM. Antes vamos resolver dois problemas que sera˜o u´teis no decorrer deste cap´ıtulo. Primeiro desafio O primeiro desafio e´, dada uma matriz de dimenso˜es n×n, vamos gerar uma segunda matriz a partir da primeira onde cada elemento e´ a me´dia da soma dele com treˆs de seus vizinhos na matriz original. Para exemplificar o que queremos, vejamos a seguinte ilustrac¸a˜o de uma matriz 4× 4: 4 6 2 1 9 0 0 2 8 7 3 9 1 2 3 4 Queremos que a matriz nova tenha como elemento da primeira linha, primeira coluna, a me´dia do quadrado constitu´ıdo pelos elementos das duas primeiras linhas considerando-se apenas as duas primeiras colunas, isto e´, a sub-matriz: 4 6 9 0 A me´dia destes elementos e´ (4+6+9+0) 4 = 4.75. O elemento gerado para a primeira linha, segunda coluna e´ a me´dia da seguinte sub-matriz: 2 1 0 2 10.2. MATRIZES 191 Isto e´, (2+1+0+2) 4 = 1.25. E assim por diante. No final, queremos produzir a seguinte matriz, de ordem 2× 2: 4.75 1.25 4.50 4.75 O procedimento que realiza este ca´lculo e´ ilustrado na figura 10.55. Como estamos no in´ıcio do estudo, vamos considerar sempre que a matriz as dimenso˜es n e m sa˜o sempre pares. procedure media dos 4 vizinhos (var v, lin v , col v : integer var w, var lin w , col w : integer) ; (∗ produz a matriz w a partir da media dos vizinhos de v ∗) (∗ lin v , col v definem linhas e colunas da matriz v ∗) (∗ lin w , col w definem linhas e colunas da matriz w ∗) var i , j : integer ; begin lin w:= lin m div 2; col w:= col m div 2; for i := 1 to lin w do for j:= 1 to col w do w[ i , j ]:= (m[2∗ i−1,2∗j−1] + m[2∗ i ,2∗ j−1] + m[2∗ i−1,2∗j ] + m[2∗ i ,2∗ j ] ) /4; end; Figura 10.55: Gerando matriz pela me´dia dos vizinhos. Segundo desafio Agora vamos trabalhar com gerac¸a˜o de “pedac¸os” de uma matriz, isto e´, dada uma matriz n × m, queremos gerar uma nova matriz que consiste de uma submatriz da primeira. Para isto, vamos considerar uma “janela” da matriz original definida pelo canto superior esquerdo e pelo canto inferior direito. Vejamos um exemplo do que queremos. Vamos considerar novamente a matriz exemplo seguinte, de ordem 5× 4: 4 6 2 1 9 0 0 2 8 7 3 9 1 2 3 4 0 1 0 1 A janela exemplo tem seu canto superior esquerdo nas coordenadas (2, 3) e seu canto inferior direito em (4, 4). Isto define a submatriz seguinte (elementos em negrito na figura anterior): 192 CAPI´TULO 10. ESTRUTURAS DE DADOS 0 2 3 9 3 4 O procedimento apresentado na figura 10.56 gera a submatriz desejada. procedure gerasubmatriz(var m: matriz ; lin m , col m: integer ; var w: matriz ; var lin w , col w : integer ; x1,y1,x2,y2: integer) ; (∗ (x1,y1) eh o canto superior esquerdo , (x2,y2) eh o canto inferior esquerdo ∗) var i , j : integer ; begin lin w:= x2 − x1 + 1; col w:= y2 − y1 + 1; for i := 1 to lin w do for j:= 1 to col w do w[ i , j ]:= m[ i+x1−1,j+y1−1]; end; Figura 10.56: Gerando submatriz. Matrizes que representam imagens Um dos formatos reconhecidos pelos computadores atuais para imagens e´ o padra˜o PGM. Este formato consiste de um arquivo ASCII que tem o seguinte formato: • a primeira linha conte´m um identificador “P2”; • a segunda linha conte´m a largura e a altura de uma matriz, isto e´, o nu´mero de colunas e de linhas; • a terceira linha conte´m o valor do maior valor da matriz que conte´m a imagem propriamente dita; • o restante do arquivo conte´m uma matriz de elementos (bytes) que representam um pixel da imagem em tons de cinza. A figura 10.57 mostra um exemplo de um arquivo que e´ uma imagem em PGM: a primeira linha tem “P2”; a segunda linha conte´m a dimensa˜o da matriz (10 × 11, observe que por definic¸a˜o o nu´mero de colunas vem antes); a terceira linha conte´m o maior elemento (40) da matriz que constitui o restante do arquivo. Vamos mostrar uma maneira de se fazer um zoom na imagem. Existem va´rias te´cnicas, a nossa sera´ da seguinte forma: o zoom sera´ obtido pela me´dia de cada quatro vizinhos, isto e´, o procedimento da figura 10.55. A matriz que conte´m o zoom sera´ enta˜o impressa na sa´ıda padra˜o, mas no formato correto para