Matrizes (Aula 7)

Matrizes
(Aula 7)
Uma matriz � um array de duas dimens�es. Uma matriz � �til por exemplo para armazenar tabelas, fazer calculos matem�ticos, fazer desenhos, resolver problemas, etc. Imagina que desejamos guardar no computador a lista dos alunos com suas respetivas notas em todas as disciplinas cursadas durante o ano. Por exemplo a seguinte tabela mostra a lista de 10 alunos e as notas em 8 disciplinas.

Alunos notas Media
1 2 3 4 5 6 7 8
Jo�ozinho 7 7 8 9 5 6 6 9
Pedrinho 4 5 5 7 8 9 6 6
Gabriela 8 8 7 5 7 8 9 7
Roberto 4 5 6 7 5 6 7 3
Paulo 5 4 5 4 6 5 5 3
Gisele 6 7 7 8 5 9 8 9
Vera 7 7 8 8 6 6 8 9
Jorginho 6 4 5 4 6 5 5 6
Paulinho 6 4 5 4 6 5 5 6
Flavio 7 7 8 6 8 9 8 9
Gostariamos fazer um programa para armazenar essa tabela no computador e depois poder calcular por exemplo a media de todas as notas de todos os alunos. Inclusive para saber o desempenho da turma inteira poderiamos calcular a media das medias.

Bom, para come�ar vamos pensar apenas em como armazenar as notas na memoria do computador. Para isso vamos utilizar uma matriz. Em Pascal, uma matriz � definida em forma muito similar a um vetor, da seguinte forma:
Var notas : array [1..10,1..8] of real;
Onde o n�mero 10 indica o n�mero maximo de linhas da matriz e o n�mero 8 indica o n�mero maximo de colunas. Se n�o sabemos com antecedencia qual ser� o tamanho de nossa matriz podemos reservar um n�mero grande como foi feito com vetores.

Para manter a informa��o completa da tabela no computador, poderiamos armazenar tamb�m os nomes dos alunos num vetor de string e as medias dos alunos num vetor de n�meros reias.
Vejamos como trabalhar com matrizes, analisando o seguinte programa que le as notas dos alunos, calcula as medias, guarda num vetor e imprime os resultados na tela do computador.
Programa
Program Turma;
Var notas: array [1..10,1..8] of real;
Media: array [1..8] of real;
Soma: real;
i,j,N,M: integer;
Begin
{Entrada de Dados}
Readln(N); {ler o n�mero de alunos}
Readln(M); {ler o n�mero de disciplina}
For i:=1 to N do Begin
For j:=1 to M do Begin
{ler as notas dos alunos em cada disciplina}
Read (notas[i][j]);
End;
End;
{Processamento de Dados}
For i:=1 to N do Begin
Soma:=0; {zerar a soma das notas do aluno i}
For j:=1 to M do Begin
{acrecentar a soma as notas da disciplina j}
Soma:=Soma + notas[i][j]
End;
Media[i]:=Soma/M;
End;
{Sa�da de Resultados}
For i:=1 to N do Begin
Writeln('a nota media aluno ',i,' : ',Media[i]);
End;
End.
Para acessar aos elementos de uma matriz utilizamos dois �ndices: o primeiro para definir a linha e o segundo para definir a coluna. No programa observamos que precisamos sempre de dois la�os para percorrer todos os elementos de uma matriz. Quando um la�o est� dentro de outro la�o, estes s�o chamados de la�os aninhados. � muito comum encontrar em programas la�os anhinhados, especialmente quando se trabalha com vetores e matrizes. Os vetores e matrizes s�o bastante usados em c�lculos matem�ticos. Vejamos agora um outro exemplo de opera��es com matrizes.
Problema
Fazer um programa que dada duas matrizes A e B, determinar a soma de A e B.

A soma de duas matrizes � bastante simples, apenas precisamos somar os elementos correspondentes de cada matriz e o resultado colocar em uma outra matriz. Veja o seguinte exemplo de soma de dois matrizes A e B de tamanho 3x3:
A B C
| 1 4 2 | | 1 2 3 | | 2 6 5 |
| 0 5 1 | + | 1 0 1 | = | 1 5 2 |
| 2 2 8 | | 2 3 2 | | 4 5 10|

Solu��o
Vamos escrever um programa que le os elementos da matriz, depois faz a soma de seus elementos e finalmente imprime a matriz resultante. A primeira entrada s�o as dimens�es da matriz. Para poder somar duas matrizes, elas devem ter as mesmas dimens�es. Os elementos de cada linha devem ser digitados deixando um espaco, como mostra o seguinte exemplo:
Exemplo de entrada:
digite as dimens�es das matrizes:
3
3
digite os elementos da matriz A:
1 4 2
0 5 1
2 2 8
digite os elementos da matriz B:
1 2 3
1 0 1
2 3 2
Programa
Program soma_matrizes;
Var A,B,C: array[1..100,1..100] of integer;
i,j: integer;
M,N: integer;
Begin
Writeln('digite as dimens�es das matrizes:');
Readln(N,M);
Writeln('digite os elementos da matriz A:');
For i:=1 to N do Begin
For j:=1 to M do Begin
Read(A[i,j]);
End;
Readln;
end;
Writeln('digite os elementos da matriz B:');
For i:=1 to N do Begin
For j:=1 to M do Begin
Read(B[i,j]);
End;
Readln;
end;
{calcular a soma de A + B}
For i:=1 to N do Begin
For j:=1 to M do Begin
C[i,j]:=A[i,j]+B[i,j];
End;
End;
{imprimir o resultado}
Writeln('O resultado da soma de A+B:');
For i:=1 to N do Begin
For j:=1 to M do Begin
Write(C[i,j],' '); {deixar espa�o entre n�meros}
End;
Writeln; { quebra linha }
End;
End.
Problema: Aeroporto
A crescente utiliza��o do transporte a�reo preocupa os especialistas, que prev�em que o congestionamento em aeroportos poder� se tornar um grande problema no futuro. Os n�meros atuais j� s�o alarmantes: relat�rios oficiais demonstram que na Europa, em junho de 2001, houve uma m�dia de 7.000 atrasos de v�os por dia. Preocupada com a previs�o dos seus especialistas em tr�fego a�reo, a Associa��o de Transporte A�reo Internacional (ATAI) est� come�ando um estudo para descobrir quais s�o os aeroportos onde o tr�fego a�reo pode vir a ser mais problem�tico no futuro.
Tarefa
Como programador rec�m contratado pela ATAI voc� foi encarregado de escrever um programa para determinar, a partir de uma listagem de aeroportos e v�os, qual aeroporto possui maior probabilidade de congestionamento no futuro. Como medida da probabilidade de congestionamento ser� utilizado neste estudo o n�mero total de v�os que chegam ou que partem de cada aeroporto.
Entrada
A primeira linha de entrada cont�m dois n�meros inteiros A e V, que indicam respectivamente o n�mero de aeroportos e o n�mero de v�os. Os aeroportos s�o identificados por inteiros de 1 a A. As V linhas seguintes cont�m cada uma a informa��o de um v�o, representada por um par de n�meros inteiros positivos X e Y, indicando que h� um v�o do aeroporto X para o aeroporto Y.
Exemplo de Entrada
5 7
1 3
2 1
3 2
3 4
4 5
3 5
2 5
Restri��es
0 ≤ A ≤ 100
0 ≤ V ≤ 10000
1 ≤ X ≤ A
1 ≤ Y ≤ A
X ≠ Y
Solu��o
Para resolver este problema vamos usar matrizes. Os indices de cada elemento da matriz vai indicar o origem e o destino do v�o, por exemplo 1,3 indica que tem v�o do aeroporto 1 ao aeroporto 3. Em cada elemento da matriz vamos armazenar o n�mero de v�os, por exemplo mat[1][3] vamos colocar um 1 indicando que existe um v�o entre estes dois aeroportos. A tabela ou matriz para armazenar os dados de acima seria uma matriz quadrada de tamanho igual ao n�mero de aeroportos.
1 2 3 4 5
1 0 0 1 0 0
2 1 0 0 0 1
3 0 1 0 1 1
4 0 0 0 0 1
5 0 0 0 0 0
A partir desta tabela podemos determinar os aeroportos mas congestionados, contando os v�os que chegam e os v�os que saem. Para isso vamos somar as linhas e as colunas de forma similar como foi feito com a tabela das notas. Estes ser�o armazenados em vetores para depois fazer a soma e finalmente procurar os aeroportos mais congestionados. Vejamos o programa:
Programa
PROGRAM aeroporto;
VAR mat: array [1..100,1..100] of integer;
total,sai,cheg: array[1..100] of integer;
A,V:integer;
i,j:integer;
x,y:integer;
max: integer;
BEGIN
WRITELN('digite o n�mero de aeroportos e o n�mero de v�os');
READ(A); {ler numero de aeroportos}
READLN(V); {ler n�mero de v�os}
{zerar a matriz mat}
FOR i:=1 TO A DO BEGIN
FOR j:=1 TO A DO BEGIN
mat[i][j]:=0;
END;
END;
{ler x, y e acrecentar 1 na matriz se existir v�o de x para y}
Writeln('para cada v�o digite o origem e o destino na mesma linha');
FOR i:=1 to V DO BEGIN
READLN(x,y);
mat[x][y]:=mat[x][y]+1;
END;

{somar as saidas do aeroporto i}
FOR i:=1 TO A DO BEGIN
sai[i]:=0;
FOR j:=1 TO A DO BEGIN
sai[i]:=sai[i]+mat[i][j];
END;
END;

{somar as chegadas ao aeroporto j}
FOR j:=1 TO A DO BEGIN
cheg[j]:=0;
FOR i:=1 TO A DO BEGIN
cheg[j]:=cheg[j]+mat[i][j];
END;
END;
{procurar o valor maximo da soma de chegadas e saidas}
max:=0;
FOR i:=1 TO A DO BEGIN
total[i]:=cheg[i]+sai[i];
IF(total[i]>max) THEN max:=total[i];
END;
{imprimir os aeroportos congestionados}
WRITELN(' Os aeroportos congestionados:');
FOR i:=1 TO A DO BEGIN
IF(max=total[i]) THEN WRITE(i, ' ');
END;
WRITELN; {quebra linha}
END.
Exerc�cios
O jogo de xadrez, al�m de ser um jogo que exige bastante racioc�nio, � uma �tima fonte de quebra-cabe�as. Este problema trata de um destes quebra-cabe�as, envolvendo os movimentos de uma de suas pe�as, o cavalo. Os movimentos do cavalo s�o ditos em 'L', pois ele sempre deve andar duas casas em uma dire��o e uma casa na dire��o perpendicular.



A figura acima ilustra os poss�veis movimentos do cavalo, onde o caractere 'C' indica a posi��o inicial e o caractere '•' representa as poss�veis finais. � importante notar que o cavalo � a unica pe�a que pode saltar sobre outras pe�as do xadrez. Note ainda que na representa��o que usamos n�o desting�imos casas brancas de casas pretas no tabuleiro.
Tarefa
Usando os movimentos do cavalo, voce deve fazer um programa para determinar qual o n�mero m�nimo de movimentos do cavalo para ir de uma casa Inicio at� uma casa Final, sendo proibido que o cavalo para sobre algumas casas especificadas com X durante a seq��ncia de movimentos.



Entrada
Como entrada ser�o fornecidas LI e CI indicando a posi��o (coluna e linea) inicial do cavalos no tabuleiro, a posi��o final LF e CF, o n�mero de casas proibidas e a sequencia de LX e CX indicando a posi��o das casas proibidas.
Exemplo de entrada:
4 3
7 8
13
3 5
4 4
4 5
5 3
5 4
5 5
5 6
5 7
6 2
6 3
6 4
8 5
8 6
Sa�da
O programa deve mostrar o minimo n�mero de movimentos que o cavalo deve fazer para ir da posi��o inicial ate a posi��o final. Por exemplo, a sa�da para os dados de acima �: 6.
Quebracabe�a
Este � um jogo antigo bem popular entre crian�as que consiste de uma matriz de 5x5 contendo 25 quadradinho todos de igual tamanho. Em cada quadradinho esta escrito uma unica letra do alfabeto, por�m um quadradinho esta vazio, como mostra a figura abaixo.



Um quadradinho pode ser movido para o espa�o vazio se este estiver a direita, esquerda, acima ou abaixo imediato. O objetivo da quebracabe�a � mover os quadradinho no espa�o vazio de forma que todas as letras aparecem em ordem alfabetico.
Tarefa
Escreva um programa que mostre o quebracabe�a resultante depois de uma seq��ncia de movimentos dada a posi��o inicial.
Entrada
A entrada consiste da configura��o inicial da quebracabe�a, e a sequencia de movimentos. As primeiras 5 linhas descreve a configura��o inicial, a linha seguinte contem a seq��ncia de movimentos, definidos pelas letras A,B,E,D. Onde cada letra tem o seguinte significado
A --- O movimento � para abaixo, a letra que esta acima do espa�o vazio ser� movido
B --- O movimento � para acima, a letra que esta abaixo do espa�o vazio ser� moviemdo
E -- O movimento � para esquerda, a letra que esta � direita do espa�o vazio ser� movida
D -- O movimento � para a direita, a letra que esta � esqueda do espa�o vazio ser� movida
Caso exista algum movimento n�o permitido, imprimir que a quebracabe�a n�o tem configura��o final.
Exemplo de entrada
TRGSJ
XDOKI
M VLN
WPABE
UQHCF
AEEBBR
S�ida
A s�ida � a configura��o final da quebracabe�a depois da seq��ncia de movimentos, as letras devem ser imprimidas deixando um espa�o, como mostra o exemplo:
Exemplo de sa�da
T R G S J
X O K L I
M D V B N
W P A E
U Q H C F
Sensor do escaner
Uma imagem em branco e preto pode ser considerado como uma matriz de pontos brancos e pretos. Onde os pontos pretos representam o objeto e o branco o fundo. Quando desejamos guardar no computador uma imagem, utilizamos um escaner. O escaner � um aparelho que tem v�rios sensores que detecta os pontos brancos e pretos quando passa pela imagem e depois reconstrui a imagem colocando numa matriz de zeros e unos. Um dos sensores do escaner barre a imagem em forma diagonal, como mostra a figura abaixo. Em cada diagonal conta o n�mero de pontos pretos.


Tarefa
Fa�a um programa que conte o n�mero de pontos pretos em cada diagonal da imagem.
Dados de entrada
A entrada � composta de M e N que indica o tamanho da imagem e de uma matriz de 1s e 0s que representa a imagem.

Ejemplo de entrada
5 7
0 0 0 0 0 1 0
1 1 0 1 0 0 0
0 0 1 0 0 1 0
0 1 0 1 0 0 0
0 0 0 1 0 1 0
Sa�da
Na sa�da o programa deve imprimir o n�mero de pontos pretos em cada diagonal.
Exemplo de sa�da
0 1 1 0 3 1 1 2 0 1 0
As solu��es voce encontra aqui.

Posted in: Aulas Tutorias