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