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\u2dco 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\u2dces n×m e um vetor
de n elementos e inserir o vetor como uma coluna adicional na matriz, que ficara´ com
dimenso\u2dces 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\u2dco.
procedure insere coluna no fim (var w: matriz ; v: vetor ; var n,m: integer) ;
(\u2217 recebe uma matriz e um vetor e insere o vetor como ultima coluna da matriz \u2217)
var i : integer ;
begin
for i := 1 to n do
w[ i ,m+1] := v[ i ] ; (\u2217 m+1 eh fixo , queremos sempre a ultima coluna \u2217)
m:= m + 1; (\u2217 altera o numero de colunas \u2217)
end;
Figura 10.53: Insere um vetor como u´ltima coluna de uma matriz.
Um problema mais dif´\u131cil seria se quise´ssemos inserir o vetor em alguma coluna
que na\u2dco 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´\u131amos que abrir espac¸o na matriz
antes de inserir o vetor. Esta e´ uma operac¸a\u2dco 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) ;
(\u2217 recebe uma matriz e um vetor e insere o vetor na coluna K da matriz \u2217)
var i : integer ;
begin
(\u2217 primeiro abre espaco \u2217)
for j:= m downto K do (\u2217 para cada coluna , iniciando na ultima \u2217)
for i := 1 to n do (\u2217 move elementos uma coluna para frente \u2217)
w[ i , j+1]:= w[ i , j ] ;
(\u2217 depois insere na coluna K \u2217)
for i := 1 to n do
w[ i ,K] := v[ i ] ; (\u2217 K eh fixo , queremos sempre a K\u2212esima coluna \u2217)
m:= m + 1; (\u2217 altera o numero de colunas \u2217)
end;
Figura 10.54: Insere um vetor como K-e´sima coluna de uma matriz.
10.2.5 Aplicac¸o\u2dces de matrizes em imagens
Nosso objetivo nesta sec¸a\u2dco e´ mostrar como podemos fazer modificac¸o\u2dces em imagens
digitais no formato PGM. Antes vamos resolver dois problemas que sera\u2dco u´teis no
decorrer deste cap´\u131tulo.
Primeiro desafio
O primeiro desafio e´, dada uma matriz de dimenso\u2dces n×n, vamos gerar uma segunda
matriz a partir da primeira onde cada elemento e´ a me´dia da soma dele com tre\u2c6s
de seus vizinhos na matriz original. Para exemplificar o que queremos, vejamos a
seguinte ilustrac¸a\u2dco 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´\u131do 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´\u131cio do estudo, vamos considerar sempre que a matriz as dimenso\u2dces n e m sa\u2dco
sempre pares.
procedure media dos 4 vizinhos (var v, lin v , col v : integer
var w, var lin w , col w : integer) ;
(\u2217 produz a matriz w a partir da media dos vizinhos de v \u2217)
(\u2217 lin v , col v definem linhas e colunas da matriz v \u2217)
(\u2217 lin w , col w definem linhas e colunas da matriz w \u2217)
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\u2217 i\u22121,2\u2217j\u22121] + m[2\u2217 i ,2\u2217 j\u22121] + m[2\u2217 i\u22121,2\u2217j ] + m[2\u2217 i ,2\u2217 j ] ) /4;
end;
Figura 10.55: Gerando matriz pela me´dia dos vizinhos.
Segundo desafio
Agora vamos trabalhar com gerac¸a\u2dco de \u201cpedac¸os\u201d 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 \u201cjanela\u201d 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) ;
(\u2217 (x1,y1) eh o canto superior esquerdo , (x2,y2) eh o canto inferior esquerdo \u2217)
var i , j : integer ;
begin
lin w:= x2 \u2212 x1 + 1;
col w:= y2 \u2212 y1 + 1;
for i := 1 to lin w do
for j:= 1 to col w do
w[ i , j ]:= m[ i+x1\u22121,j+y1\u22121];
end;
Figura 10.56: Gerando submatriz.
Matrizes que representam imagens
Um dos formatos reconhecidos pelos computadores atuais para imagens e´ o padra\u2dco
PGM. Este formato consiste de um arquivo ASCII que tem o seguinte formato:
\u2022 a primeira linha conte´m um identificador \u201cP2\u201d;
\u2022 a segunda linha conte´m a largura e a altura de uma matriz, isto e´, o nu´mero de
colunas e de linhas;
\u2022 a terceira linha conte´m o valor do maior valor da matriz que conte´m a imagem
propriamente dita;
\u2022 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 \u201cP2\u201d; a segunda linha conte´m a dimensa\u2dco da matriz (10 × 11,
observe que por definic¸a\u2dco 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\u2dco impressa na sa´\u131da padra\u2dco, mas no formato
correto para