ALGORITMOS E ESTRUTURAS DE DADOS I
259 pág.

ALGORITMOS E ESTRUTURAS DE DADOS I


DisciplinaAlgoritmos e Estrutura de Dados I708 materiais7.919 seguidores
Pré-visualização50 páginas
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\u2dco.
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
(\u2217 n e m sao o numero de linhas e colunas , respectivamente \u2217)
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\u2dco
os dois procedimentos fazem a mesma operac¸a\u2dco de somar dois vetores!
Multiplicac¸a\u2dco de matrizes
Agora vamos resolver o problema da multiplicac¸a\u2dco de matrizes. Inicialmente vamos
recordar como isto e´ feito.
Do ponto de vista matema´tico cada elemento da matriz resultado da multiplicac¸a\u2dco
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\u2dco 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\u2211
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\u2dco, neste caso, o produto escalar da linha
I da matriz A pela coluna J da matriz B e´ dado pela seguinte somato´ria:
m\u2211
k=1
A[I, k]×B[k, J ].
O programa que realiza esta operac¸a\u2dco e´ uma adaptac¸a\u2dco 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 (\u2217 considerando I e J fixos \u2217)
soma:= 0;
for i := 1 to m do
soma:= soma + A[ I ,k] \u2217 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\u2dco: 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] \u2217 B[k, j ] ;
end;
end.
Figura 10.49: Multiplicac¸a\u2dco de duas matrizes.
10.2.3 Procurando elementos em matrizes
Nesta sec¸a\u2dco 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\u2dco 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\u2dco anterior com duas modificac¸o\u2dces: a primeira e´ que deve-se usar
um procedimento que retorna as duas coordenadas usando para\u2c6metros por refere\u2c6ncia,
pois func¸o\u2dces 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
(\u2217 trecho inicial omitido \u2217)
i f w[ i , j ] = x then
begin
(\u2217 quando acha o elemento , armazena as coordenadas \u2217)
achou:= true ;
l := i ;
c:= j ;
end;
(\u2217 trecho final omitido \u2217)
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\u2dco
diferente. Isto exige um aninhamento de quatro lac¸os!
Um lac¸o duplo e´ necessa´rio 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