apostila

∗)
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