apostila

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