Algoritmos e Estruturas de Dados
I – Estruturas de Dados
Profa. Mercedes Gonzales
Márquez
Matrizes – Estrutura composta
homogênea bidimensional
Uma matriz representa um conjunto de vetores
de mesmo tamanho.
Uma matriz possui m linhas e n colunas:
– as linhas são numeradas de 1 a m
– as colunas são numeradas de 1 a n
Uma matriz pode armazenar (linhas * colunas)
elementos de um mesmo tipo
Uma matriz de m linhas e n colunas
1
1
2
3
4
m
2
3
4
n-1 n
Estrutura composta homogênea
multidimensional
- Há casos em que uma matriz é insuficiente para
armazenar um conjunto de dados para um determinado
programa. Nestes casos, é
necessário definir uma estrutura de d-dimensões
(Estrutura composta homogênea multidimensional).
- Declaração geral para d dimensões:
Tipo primitivo : variável[num_elem_
[num_elem_seg_dim]...[num_elem_d_dim]
prim.dim]
Estrutura composta homogênea
multidimensional
Exemplos
- tridimensional:
inteiro: matriz[4][4][4]
Estrutura composta homogênea
multidimensional
Estrutura composta homogênea
multidimensional
Estrutura composta homogênea
multidimensional
Estrutura Composta homogênea
multidimensional
-Para acessar um vetor, o inserimos em um único laço de
repetição, fazendo com que haja variação em seu índice.
-Como em uma estrutura multidimensional temos mais
de um índice, faz-se necessária a utilização de mais laços
de repetição, geralmente em mesmo número do que o
número de dimensões da estrutura.
-As estruturas multidimensionais mais utilizadas são as
bidimensionais (Matrizes).
Algumas Matrizes Especiais
-Matriz diagonal
Nesta matriz apenas os elementos da diagonal principal
ou secundária são significativos. Exemplos:
Algumas Matrizes Especiais
-Matriz triangular
Nesse tipo de matriz, apenas os elementos da diagonal
principal ou secundária e os abaixo (ou acima) possuem
valores significativos.
Algumas Matrizes Especiais
-Matriz transposta
É a matriz que resulta da troca de linhas por colunas em
uma determinada matriz.
1 3  5


A  0  2 4 
2 3
6 
Uma
0 2
1
AT   3  2 3
 5 4 6
matriz simétrica é toda a matriz que é igual à sua
transposta.
Matrizes Especiais
-Matriz simétrica e anti-simétrica
Uma matriz é dita simétrica quando para todo I e J temos:
M[I, J] = M[J, I]
Uma matriz é dita anti-simétrica quando para todo I e J temos:
M[I, J] = - M[J, I]
Matrizes - Exercícios
(1) Construa um algoritmo que efetue a leitura de duas
matrizes inteiras de dimensão 5x5, calcule e imprima a
soma delas.
Algoritmo <somamatrizes>
inteiro:A[5][5],B[5][5],S[5][5],i,j
inicio
para i de 1 até 5 repita
para j de 1 até 5 repita
leia (A[i][j],B[i][j])
S[i][j] ← A[i][j]+B[i][j]
fim para
fim para
fim
Matrizes
(2) Elabore um algoritmo que dada uma matriz 7 x 7
calcule a sua matriz transposta e ainda diga se ela é
simétrica ou não.
Algoritmo <matrizsimetrica>
inteiro:A[7][7],i,j,flag
inicio
para i de 1 até 7 repita
para j de 1 até 7 repita
leia A[i][j]
B[j][i] ← A[i][j]
fim para
fim para
flag ← 1
para i de 1 até 7 repita
para j de 1 até 7 repita
se (A[i][j]<>B[i][j])
flag ← 0
fim para
fim para
Se (flag=1) então
Escreva (“Simétrica”)
senão
Escreva (“Não Simétrica”)
fim se
fim
Matrizes
(3) Elabore um algoritmo que leia duas matrizes inteiras
A e B de dimensão 3x3 e calcule em uma matriz R, a
multiplicação delas.
Matrizes
Lembre-se que:
 A11 A12 A13   B11 B12 B13   R11 R12 R13 
 A A A  * B B B   R R R 
 21 22 23   21 22 23   21 22 23 
 A31 A32 A33   B31 B32 B33   R31 R32 R33 
R11  A11*B11 A12*B21 A13*B31
R12  A11*B12  A12*B22  A13*B32
R13  A11*B13  A12*B23  A13*B33
R21  A21*B11 A22*B21 A23*B31
...
R32  A31*B12  A32*B22  A33*B32
R33  A31*B13  A32*B23  A33*B33
Matrizes
Algoritmo <produtomatrizes>
inteiro:A[3][3],B[3][3],R[3][3],i,j,k
início
para i de 1 até 3 repita
para j de 1 até 3 repita
leia (A[i][j],B[i][j])
fim para
fim para
para i de 1 até 3 repita
para j de 1 até 3 repita
R[i][j] ← 0
para k de 1 até 3 repita
R[i][j] ← A[i][k]*B[k][j]+R[i][j]
fim para
fim para
fim para
Matrizes
(4) Faça um algoritmo que leia uma matriz M de 10x10
Troque a seguir
(a)A linha 2 com a linha 8
(b)A coluna 4 com a coluna 10
(c)A diagonal principal com a diagonal secundária
(d)A linha 5 com a coluna 10
Matrizes
Algoritmo <trocas>
inteiro:M[10][10],i,j,t
inicio
para i de 1 até 10 repita
para j de 1 até 10 repita
leia (M[i][j])
fim para
fim para
para i de 1 até 10 repita
t ← M[2][i]
M[2][i] ← M[8][i]
M[8][i] ← t
t ← M[i][4]
M[i][4] ← M[i][10]
M[i][10] ← t
t ← M[5][i]
M[5][i] ← M[i][10]
M[i][10] ← t
t ← M[i][i]
M[i][i] ← M[i][11-i]
M[i][11-i] ← t
fim para
fim
Matrizes
(5) Faça um algoritmo que leia uma matriz M de
dimensão 6x6 e um valor A, multiplique a matriz pelo
valor A, coloque os valores da matriz multiplicados por A
em um vetor de 36 elementos e imprima o vetor.
Algoritmo <matriz_vetor>
inteiro:M[6][6],V[36],A,i,j
inicio
leia (A)
para i de 1 até 6 repita
para j de 1 até 6 repita
leia (M[i][j])
V[(i-1)*6+j] ← A*M[i][j]
fim para
fim para
Matrizes
(6) Escreva um algoritmo que leia um número inteiro A e
uma matriz de 30x30 de inteiros. Também deve contar
quantos valores iguais a A estão na matriz e criar uma
matriz X contendo todos os elementos diferentes de A.
Nas outras posições deve se colocar o valor 0.
Matrizes
Algoritmo <matriz_vetor>
inteiro:M[30][30],A,X[30][30],i,j,cont
inicio
leia (A)
cont ← 0
para i de 1 até 30 repita
para j de 1 até 30 repita
leia (M[i][j])
se (M[i][j]=A) então
X[i][j] ← 0
cont ← cont+1
senão
X[i][j] ← M[i][j]
fim se
fim para
fim para
Matrizes
(7) Escreva um algoritmo que leia uma matriz M de 12 x
13 e divide todos os 13 elementos de cada uma das
linhas de M pelo maior elemento em módulo daquela
Algoritmo <divide_maior>
linha.
inteiro:M[12][13],maior,i,j
inicio
para i de 1 até 12 repita
maior ← 0
para j de 1 até 13 repita
leia (M[i][j])
se (abs(M[i][j])>maior) então
maior ← abs(M[i][j])
fim se
fim para
para j de 1 até 13 repita
M[i][j] ← M[i][j]/maior
fim para
Matrizes
(8) Escreva um algoritmo que leia uma matriz M de 5 x 5
e crie dois vetores SL[5] e SC[5] que contenham,
respectivamente, as somas das linhas e das colunas de M.
Escreva a matriz e os vetores criados.
Algoritmo <soma_linhas_colunas>
inteiro:M[5][5],SL[5],SC[5],i,j
inicio
/*Leitura de M[i][j]*/
para i de 1 até 5 repita
SL[i] ← 0
SC[i] ← 0
para j de 1 até 5 repita
SL[i] ← SL[i]+M[i][j]
SC[i] ← SC[i]+M[j][i]
fim para
fim para
Matrizes
(9) Faça um algoritmo que leia uma matriz 20x15 de
inteiros e calcule a soma das linhas pares da matriz.
Algoritmo <soma_linhas_pares>
inteiro:M[20][15],S,i,j
inicio
S←0
para i de 2 até 20 passo 2 repita
para j de 1 até 15 repita
leia (M[i][j])
S ← S+M[i][j]
fim para
fim para
fim
Matrizes
(10) Na teoria de sistemas, define-se como elemento
minimax de uma matriz o menor elemento da linha onde
se encontra o maior elemento da matriz. Escreva um
algoritmo que leia uma matriz 10x10 de inteiros e
encontre seu elemento minimax, mostrando também sua
posição.
Matrizes
Algoritmo <minimax>
inteiro:M[10][10],minimax,maior,indi,indj,i,j
inicio
maior ← -inf
para i de 1 até 10 repita
para j de 1 até 10 repita
leia (M[i][j])
se (M[i][j]>maior) então
maior ← M[i][j]
indi ← i
fim se
fim para
fim para
menor ← inf
para j de 1 até 10 repita
se (M[indi][j]<menor) então
menor ← M[i][j]
indj ← j
fim se
fim para
Matrizes
(11) Faça um algoritmo que leia uma matriz 12x12 de inteiros,
calcule e escreva a soma da área hachurada na letra a e o maior
elemento da área hachurada na letra b abaixo:
Matrizes
Algoritmo <areahachurada-a>
inteiro:M[12][12], i,j, soma
início
soma ←0
para i de 1 até 12 repita
para j de 1 até 12 repita
leia (M[i][j])
fim para
fim para
para i de 1 até 11 repita
para j de 1 até 12-i repita
soma← soma+M[i][j]
fim para
fim para
fim
Algoritmo <areahachurada-b>
inteiro:M[12][12], i,j, maior
início
para i de 1 até 12 repita
para j de 1 até 12 repita
leia (M[i][j])
fim para
fim para
maior ← -inf
para i de 1 até 6 repita
para j de i até 13-i repita
se (M[j][i]>maior) então
maior← M[j][i]
fim se
se (M[j][13-i]>maior) então
maior← M[j][13-i]
fim se
fim para
fim para
fim
Matrizes
(12) Faça um algoritmo que leia uma matriz 12 x 12 e calcule e
escreva: a. o menor elemento e a sua posição (índices) da área
hachurada; b. a média dos elementos da área hachurada.
Matrizes
Algoritmo <areahachurada-a>
inteiro:M[12][12], i,j, menor
início
menor ←inf
para i de 1 até 12 repita
para j de 1 até 12 repita
leia (M[i][j])
fim para
fim para
para i de 1 até 12 repita
para j de 13-i até 12 repita
se (M[i][j]<menor) então
menor← M[i][j]
fim se
fim para
fim para
fim
Algoritmo <areahachurada-b>
inteiro:M[12][12], i,j, soma,media,cont
início
para i de 1 até 12 repita
para j de 1 até 12 repita
leia (M[i][j])
fim para
fim para
soma ← 0
para i de 1 até 5 repita
para j de i+1 até 12-i repita
soma ← soma+M[i][j]
soma ← soma+M[13-i][j]
cont ←cont+1
fim para
fim para
media ←soma/cont
fim
Matrizes
(13) Uma certa fábrica produziu dois tipos de motores M1 e M2
nos meses de janeiro, ...,dezembro e o número de motores
produzidos foi registrado na tabela a seguir:
O setor de controle de vendas tem uma tabela do custo e do lucro
(em unidades monétarias) obtidos com cada motor.
Matrizes
(13) Faça um algoritmo que, a partir da produção mensal de
motores M1 e M2 e seus respectivos custos e lucros, calcule o
custo e lucro em cada um dos meses e o custo e lucro anuais.
Matrizes
Algoritmo <motores>
inteiro:P[12][2], C[12][2],
val[2][2],cla[2][2],i,j,k
início
para i de 1 até 2 repita
leia (val[i][1], val[i][2])
para j de 1 até 12 repita
leia (P[j][i])
fim para
fim para
para i de 1 até 12 repita
para j de 1 até 2 repita
C[i][j] ← 0
para k de 1 até 2 repita
C[i][j] ← P[i][k]*val[k][j]+C[i][j]
fim para
fim para
fim para
para j de 1 até 2 repita
cla[j] ← 0
para i de 1 até 12 repita
cla[j]← cla[j]+C[i][j]
fim para
fim para
para i de 1 até 2 repita
para j de 1 até 12 repita
leia (C[i][j])
fim para
fim para
para i de 1 até 2 repita
leia (cla[i])
fim para
Matrizes
Resolver os exercícios propostos sobre vetores e
matrizes do livro de Harry Farrer.
Download

AEDI-estruturasdedados2