Matrizes_01

Prévia do material em texto

A
r
r
a
y
s
 
e
m
C
Idéias Gerais
Variáveis 
Estruturadas:
vetores/arranjos/agregados (arrays 1D), 
struct (agregado heterogêneo)
Estruturas homogêneas (arrays multidimensionais)
Estruturas heterogêneas
matrizes (arrays 2D), ..., nD
strings (cadeias de caracteres)
Arquivos (FILES).
A
r
r
a
y
s
 
e
m
C
Matrizes – Revisão Matemática
11 12
21 22 2 2X
a a
A
a a
⎛ ⎞= ⎜ ⎟⎝ ⎠
11 12 13
21 22 23
31 32 33 3 3x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
Cada um dos elementos aij de uma matriz (tabela) pode ser determinado 
de forma única através de seus índices de linha e de coluna.
Por convenção, o primeiro índice (i) está associado a linha, enquanto o 
segundo índice (j) está associado a coluna.
( )ij mxnA a=
A
r
r
a
y
s
 
e
m
C
11 12 13
21 22 23
31 32 33 3 3x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
linha 1
linha 2
linha 3
coluna 
1
coluna 
2
coluna 
3
Matrizes – Revisão Matemática
A
r
r
a
y
s
 
e
m
C
linha i
coluna 
j
ija
11 1
1
n
m mn mxn
a a
A
a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
…
# #
"
Matrizes – Revisão Matemática
M
a
t
r
i
z
e
s
Operações Sobre Matrizes (Arrays 2D
Matrizes Å Matrizes operação Escalar
Vetores Å Matrizes operação Vetores
Matrizes Å Matrizes operação Matrizes
Operações Típicas
multiplicação de matrizes por um escalar real;
multiplicação de matrizes por um vetor;
Adição, subtração, multiplicação, ..., entre matrizes;
M
a
t
r
i
z
e
s
Operações Sobre Matrizes (Arrays 2D
Matrizes Å Matrizes
Permutação de linhas ou colunas, inversão, transposta de uma matriz;
Verificar uma dada propriedade (simetria, triangular inferior ou superior, ...);
Boleano Å Matrizes
Real Å Matrizes
Determinante, traço (soma dos elementos da diagonal principal ou 
secundária), maior elemento de uma linha ou coluna, maior elemento, ..., de 
uma matriz real;
Operações Típicas
M
a
t
r
i
z
e
s
Revisão de Matrizes
Multiplicação por um escalar 
Operações entre uma matriz A e um escalar .λ ∈\
** 1 ,ijA a i j nλ λ= ≤ ≤
A operação é realizada aplicando-se a multiplicação do escalar por 
todos os elementos da matriz.
M
a
t
r
i
z
e
s
Revisão de Matrizes
Operações entre matrizes
As matrizes A e B devem satisfazer os requisitos de dimensionalidade.
Subtração
Adição
, , .ij ijA B a b i j− = − ∀
, , .ij ijA B a b i j+ = + ∀
M
a
t
r
i
z
e
s
Revisão de Matrizes
Operações entre matrizes
As matrizes A e B devem satisfazer os requisitos de dimensionalidade.
Multiplicação matricial:
( )ij nxmA a=
( )jk mxpB b= 1
( ) *
m
ik nxp ij jk
j
C C a b
=
= = ∑
.C AB=
Como obter essa relação? Vamos 
desenvolver na lousa depois. Me lembrem.
A
r
r
a
y
s
 
e
m
C
Arrays 1D
Arrays multidimensionais (1D, 2D, 3D, ..., 12D)
i
A
0 n-1
Arrays unidimensionais (1D): Coleção de componentes de um 
mesmo tipo de dados.
Acesso a componentes:
indexada Notação(ponteiros)
A[i] *(A+i)
A
r
r
a
y
s
 
e
m
C
Arrays 2D
(índice de linha)
Arrays bidimensionais (2D): Representação diagramática
i
(índice de coluna)
j
linha i
coluna j
A
r
r
a
y
s
 
e
m
C
Representação de Arrays 2D
Arrays bidimensionais (2D): Representação diagramática
(5,5)(5,4)(5,3)(5,2)(5,1)(5,0)
(4,5)(4,4)(4,3)(4,2)(4,1)(4,0)
(3,5)(3,4)(3,3)(3,2)(3,1)(3,0)
(2,5)(2,4)(2,3)(2,2)(2,1)(2,0)
(1,5)(1,4)(1,3)(1,2)(1,1)(1,0)
(0,5)(0,4)(0,3)(0,2)(0,1)(0,0)
Em C, o primeiro elemento de um 
array, independente de sua 
dimensão, está sempre na posição 
0 (zero). Logo, o primeiro elemento 
de um array 2D está na posição 
(0,0).
A representação interna de um 
array 2D é feita em posições 
adjacentes de memória. Isso é
fundamental para permitir 
aritmética de ponteiros.
0
0
i m
j n
≤ <⎧⎨ ≤ <⎩
A
r
r
a
y
s
 
e
m
C
Representação Diagramática de Arrays 2D
A[5][5]A[5][4]A[5][3]A[5][2]A[5][1]A[5][0]
A[4][5]A[4][4]A[4][3]A[4][2]A[4][1]A[4][0]
A[3][5]A[3][4]A[3][3]A[3][2]A[3][1]A[3][0]
A[2][5]A[2][4]A[2][3]A[2][2]A[2][1]A[2][0]
A[1][5]A[1][4]A[1][3]A[1][2]A[1][1]A[1][0]
A[0][5]A[0][4]A[0][3]A[0][2]A[0][1]A[0][0]
Cada componente de um array 2D está associada a uma única posição 
na estrutura e pode ser referenciada de forma única através de seus 
índices de posição na linha e na coluna.
M
a
t
r
i
z
e
s
Declaração de Arrays 2D
Forma Geral: Æ
Tipo_de_Dado Nome_Variavel[NumeroLinhas][NumeroColunas];
Podem ser constantes ou 
expressões constantes.
int, char, float, double, ponteiro, ..., ou 
ainda do tipo struct (ainda vamos ver).
M
a
t
r
i
z
e
s
Declaração de Arrays 2D
Exemplos: Æ ...
...
#define MAX1 100
#define MAX2 500
int A[MAX1][MAX1];
int A1[MAX1][MAX2];
double bb[2*MAX1][MAX2];
// Matriz com 100 linhas e 100 colunas
// Matriz com 100 linhas e 500 colunas
// Matriz com 200 linhas e 500 colunas
Reserva espaço de memória para as variáveis em 
tempo de compilação.
M
a
t
r
i
z
e
s
Acesso a Arrays 2D – Notação Indexada
Forma Geral: Æ
nome_da_matriz[i][j]
Nome da variável 
estruturada matriz 
(array 2D) definida 
pelo usuário.
Índice que indica 
a linha onde o 
elemento se 
localiza
Índice que indica 
a coluna onde o 
elemento se 
localiza
M
a
t
r
i
z
e
s
Usando Notação Indexada
Exemplos: Æ Supondo as declarações de variáveis abaixo:
...
#define MAX1 100
#define MAX2 500
int A[MAX1][MAX1], b;
int A1[MAX1][MAX2];
Int B[MAX1];
...
// Matriz com 100 linhas e 100 colunas
// Matriz com 100 linhas e 500 colunas
Acesso a Componentes de Arrays 2D
// Arranjo com 100 elementos
M
a
t
r
i
z
e
s
As seguintes instruções são válidas:
...
printf(“ %d ”, A[2][3]);
A[2][8] = A1[12][25];
b = B[6] + (int)sqrt(A1[85][321])
...
Acesso a Arrays 2D – Notação Indexada
// imprimi o conteúdo do elemento da 
matriz A que está na posição (2,3);
// Altera o conteúdo do elemento da 
matriz A que está na posição (2,8), que 
passa a ter o mesmo valor do elemento 
que está na posição (12,25);
// a variável b recebe o conteúdo da 
expressão aritmética a direita do 
operador de atribuição;
M
a
t
r
i
z
e
s
Acesso a Arrays 2D – Notação Indexada
Em síntese, os elementos de uma matriz podem ser usados em 
todos os contextos em que usamos um escalar qualquer (variável 
simples), como por exemplo, em expressões aritméticas, argumentos 
de funções primitivas, ou ainda, como passagem de parâmetros. 
Lembre-se de estar atento a compatibilidade entre os tipos de dados. 
Quando for necessário, faça o molde (cast).
M
a
t
r
i
z
e
s
Acesso a Componentes de Arrays 2D
Usando Aritmética de Ponteiros
A memória de um computador é linear e não bidimensional. Assim, quando 
declaramos uma variável A do tipo array 2D ( matriz ), o compilador se 
encarrega de reservar o espaço de memória necessário, baseado em 
informações do tipo base do array (int, double, pointer, char, ...). Todas as 
referências a posição (i,j) ( [ i ][ j ]) (bidimensional) são mapeadas para o 
endereço unidimensional:
( * )k A i NC j= + +
onde:
:
:
A
NC
⎧⎨⎩
Endereço base do array 2D (1ª posição).
Número de colunas do array 2D.
M
a
t
r
i
z
e
s
Acesso a Componentes de Arrays 2D
Equivalência entre Notações Indexada e de 
Ponteiros
A[i][j] *(A + i*NC + j)
Acesso ao elemento da matriz A que está na posição (i,j).
Notação Indexada Aritmética de Ponteiros
endereçoOperador que indica o conteúdo 
de um endereço 
M
a
t
r
i
z
e
s
Acesso a Componentes de Arrays 2D
*(A + i*NC + j)
Aritmética de Ponteiros
(Fatores de deslocamento)
endereço base do array
deslocamento pelas linhas
deslocamento pelas colunas
M
a
t
r
i
z
e
s
Inicializando Variáveis Estruturadas 2D
Inicializando uma variável do tipo array 2d no 
momento de sua declaração
Várias Alternativas:Æ
...
#define MAX1 3
int A[MAX1][MAX1] = { {1, 2, 3}, {3,3,3}, {-4,2,0} };
int B[MAX1][MAX1] = {1,2,3,4,5,6,7,8,9};
int C[MAX1][MAX1] = {1,2,3,4,5};
...
M
a
t
r
i
z
e
s
Manipulação de MatrizesEmbora toda matriz seja uma variável estruturada, toda e qualquer 
operação sobre ela, deve ser feita sobre seus elementos 
individualmente. Isto significa, que devemos saber como “percorrer” , 
“caminhar” sobre cada um dos elementos da matriz, de forma 
sistemática e organizada (transverse sobre a estrutura ).
É claro que poderíamos acessar os elementos de uma matriz de 
variadas formas. Por convenção e simplicidade, manipulamos os 
elementos: da esquerda para a direita, e, de cima para baixo.
O trecho de código no próximo slide é capaz de passear por todos os 
elementos de uma matriz na ordem sugerida.
Todos os códigos a seguir foram elaborados para trabalhar com 
matrizes quadradas.
M
a
t
r
i
z
e
s
Manipulação de Matrizes
00 01 02 03
10 11 12 13
20 21 22 23
30 31 32 33 NlxNc
a a a a
a a a a
A
a a a a
a a a a
⎛ ⎞⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠
...
for (i=0; i<Nl; i++)
for (j=0; j<Nc; j++)
operações a serem realizadas sobre o elemento A[i][j];
...
% controla o índice de linhas;
% controla o índice de colunas;
Observem que o comando de repetição associado a variável de 
controle i é mais externo, logo, para cada valor de i, a variável de 
controle j, varia de 0 até Nc -1 (inclusive).
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
void Leitura_Valores_Matriz(int *A, int Dim) {
int i, j;
for (i=0; i<Dim; i++)
for (j=0; j<Dim; j++) {
printf(“A[%d ,%d] = ”,i,j);
scanf(“%d”, (A + i*Dim + j) );
} // for j
return;
} // Leitura_Valores_Matriz
Leitura de uma matriz quadrada com valores arbitrários:
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
void Impressao_Valores_Matriz(int *A, int Dim) {
int i,j;
for (i=0; i<Dim; i++) {
printf(“\n”); // mudança de linha
for (j=0; j<Dim; j++)
printf(“%d ”, *(A + i*Dim + j) );
} // for i
return;
} // Impressao_Valores_Matriz
Impressão de uma matriz quadrada:
Observação: Dependendo da dimensão da matriz podemos ter problemas em 
visualizar todos os elementos. Devemos pensar numa forma alternativa.
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Soma dos elementos da diagonal principal de uma matriz quadrada:
00 01 02
10 11 12
20 21 22 3 3x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
...
soma = 0;
for (i=0; i<Dim; i++) // percorrendo todas as linhas
for (j=0; j<Dim; j++) // percorrendo todas as colunas
if ( i == j ) soma = soma + A[i][j];
...
Qual o problema com o trecho de código acima? É possível ser mais 
eficiente?
Primeira abordagem.
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Soma dos elementos da diagonal principal de uma matriz quadrada:
00 01 02
10 11 12
20 21 22 3 3x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
Observação: Os índices de linha e de coluna são iguais. Precisamos explorar essa
informação.
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
int Soma_Diagonal_Principal(int *A, int Dim) {
int i, soma = 0;
for (i=0; i<Dim; i++)
soma += *(A + i*Dim + i );
return(soma);
} // Soma_Diagonal_Principal
Soma dos elementos da diagonal principal de uma matriz :
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Obter a transposta de uma matriz.
11 12 13
21 22 23
31 32 33 3 3
Se,
x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
11 21 31
12 22 32
13 23 33 3 3
t
x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
void Transposta_Matriz(int *A, int *AT, int Dim) {
int i,j;
for (i=0; i<Dim; i++)
for (j=0; j<Dim; j++)
*(AT + i*Dim + j) = *(A + j*Dim + i );
return;
} // Soma_Diagonal_Principal
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Verificar se uma matriz é simétrica. Uma matriz é simétrica se o elemento que 
está na posição (i,j) é igual ao elemento que está na posição (j,i), ou seja, se A = 
At.
00 01 02
10 11 12
20 21 22 3 3x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
...
for (i=0; i<Dim; i++)
for (j=0; j<Dim; j++)
if ( A[i][j] != A[j][i] ) return(0);
return(1); 
...
Qual o problema com o trecho de código acima? É possível ser mais 
eficiente?
Primeira abordagem.
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Verificar se uma matriz é simétrica. Uma matriz é simétrica se o elemento que 
está na posição (i,j) é igual ao elemento que está na posição (j,i), ou seja, se A = 
At.
00 01 02
10 11 12
20 21 22 3 3x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
Observe que é suficiente trabalhar somente com os elementos acima, 
ou abaixo da diagonal.
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Verificar se uma matriz é simétrica.
int Verificar_Simetria_Matriz (int *A, int Dim) {
int i, j;
for (i=1; i<Dim; i++)
for (j=0; j<i; j++)
if ( *(A + i*Dim + j) != *(A + j*Dim + i) ) 
return(0);
return(1);
} // Verificar_Simetria_Matriz
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Permutar os elementos de duas linhas de uma matriz arbitrária. 
l1
l2
x x x x x x x x x x x
x x x x x x x x x x x
0 1 2l l Dim≤ ≠ <
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Permutar os elementos de duas linhas de uma matriz arbitrária. 
Devemos observar que além dos parâmetros normais, há a necessidade de 
mais dois parâmetros que irão indicar respectivos índices das linhas a serem 
permutadas. A responsabilidade da correção desses índices deve ser de quem 
chamou a função. Por outro lado, a função garante a correção das linhas 
permutadas. (pré-condição e pós-condição).
Considerando a matriz a esquerda e os índices 0 e 2, após a 
permutação, teríamos a matriz do lado direito:
00 01 02
10 11 12
20 21 22
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
20 21 22
10 11 12
00 01 02
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Permutar os elementos de duas linhas de uma matriz arbitrária. 
void Permutar_Linhas_Matriz (int *A, int L1, int L2, int Dim) {
int i, j, aux;
// observe que os índices de ambas as linhas são fixos
for (i=0; i<Dim; i++) { // caminhando pelas colunas
aux = *(A + L1*Dim + i); 
*(A + L1*Dim + i) ) = *(A + L2*Dim + i);
*(A + L2*Dim + i) = aux;
}
return;
} // Permutar_Linhas_Matriz
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Somar duas matrizes arbitrárias (quadradas). 
Só podemos somar matrizes com mesma dimensão.
00 01 02 00 01 02 00 01 02
10 11 12 10 11 12 10 11 12
20 21 22 20 21 22 20 21 22
a a a b b b c c c
a a a b b b c c c
a a a b b b c c c
⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟+ =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠
A B C+ =
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Somar duas matrizes arbitrárias (quadradas). 
int Somar_Matrizes (int *A, int *B, int *C, int Dima, int Dimb) {
int i, j;
if ( Dima != Dimb) return(0);
for (i=0; i<Dima; i++)
for (j=0; j<Dima; j++)
*(C + i*Dima + j) = *(A + i*Dima + j) ) + *(B + i*Dima + j);
}
return(1);
} // Somar_Matrizes
% soma realizada com sucesso
% impossível realizar soma
M
a
t
r
i
z
e
s
Exercícios
Elabore funções para manipular matrizes quadradas arbitrárias para 
resolver os seguintes problemas:
01) Encontre a soma dos elementos da diagonal secundária;
02) Encontre a soma dos elementos acima da diagonal principal;
03) Encontre a soma dos elementos abaixo da diagonal principal;
05) Encontrar o maior elemento em valor absoluto; 
06) Realizar a permutação dos os elementos de duas colunas 
quaisquer; 
04) Encontre a soma de todos os elementos da matriz;
M
a
t
r
i
z
e
s
Exercícios
07) Encontrar a matriz mágica de dimensão n;
Uma matriz quadrada (números inteiros) é denominada mágica, se possui a 
seguinte propriedade: 
“a soma dos elementos de cada uma das linhas, das colunas e das 
diagonais, são iguais. Além disso, somente os elementos inteiros de 1 a 
n2 são permitidos. Abaixo há exemplos de matrizes mágicas de 
dimensão 3, 4 e 5.
8 1 6
3 5 7
4 9 2
⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠
16 2 3 13
5 11 10 8
9 7 6 12
4 14 15 1
⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠
S = 15 S = 34 S = 65
M
a
t
r
i
z
e
s
Exercícios
08) Obter a soma de cada uma das linhase de cada uma das colunas 
de uma matriz quadrada de dimensão n;
sl1
sl2
sl3
00 01 02
10 11 12
20 21 22
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
sc1 sc2 sc3
M
a
t
r
i
z
e
s
Exercícios
09) Gerar uma matriz quadrada de dimensão n, satisfazendo a relação 
abaixo:
2 * se ( )%2 0
. .ij j
i j i j
A a
i c c
⎧ + == = ⎨⎩
10) Gerar uma matriz quadrada de dimensão n, satisfazendo a relação 
abaixo:
( , * )
( )
( ) . .
j
ij
Mdc i i j se i j
A a Fatorial j i se i j
Fibonacci i j c c
⎧ >⎪= = − <⎨⎪ +⎩
M
a
t
r
i
z
e
s
Exercícios
11) Obter o produto de uma matriz quadrada de dimensão n arbitrária 
pela sua transposta. 
12) Dado uma matriz quadrada de coeficientes inteiros de ordem Dim, 
dizemos que A é uma matriz de permutação, se em cada linha e em 
cada coluna houver (n-1) elementos nulos e um único elemento igual 
a 1. Elabore uma função para verificar se uma matriz nas condições 
enunciadas é de permutação. Por exemplo, as matrizes de ordem 3 
dadas abaixo são todas de permutação.
1 0 0
0 0 1
0 1 0
A
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
1 0 0
0 1 0
0 0 1
A
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
0 0 1
1 0 0
0 1 0
A
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠