apostila
259 pág.

apostila

Disciplina:Algoritmos e Estrutura de Dados I542 materiais7.956 seguidores
Pré-visualização50 páginas
de frequeˆncias
para palavras do texto (quantas palavras de uma letra, quantas de duas letras, etc.).

45. Escreva um programa em Pascal que leia do teclado o gabarito de uma prova de 20
questo˜es de mu´ltipla escolha, onde as respostas sa˜o inteiros de 1 a 5. Em seguida,
o programa deve ler o nu´mero de alunos que prestaram a prova e, para cada aluno,
a sua matr´ıcula (um inteiro) e as respectivas respostas. O programa deve calcular e
escrever:

• a relac¸a˜o de alunos ordenados pela nota, supondo que cada questa˜o vale 5 pontos;
• para cada questa˜o: quantos alunos acertaram a questa˜o

10.2. MATRIZES 179

10.2 Matrizes

Assim como os vetores, as matrizes sa˜o arrays. Os vetores sa˜o estruturas unidimen-
sionais enquanto que as matrizes sa˜o bidimensionais. Isto e´, o acesso a`s posic¸o˜es de
memo´ria de um vetor sa˜o feitas com base em duas informac¸o˜es: o nome da varia´vel e
o deslocamento. Para se acessar os elementos de uma matriz, precisa-se do nome da
varia´vel, do deslocamento lateral e do deslocamento vertical. Os elementos de uma
matriz tambe´m sa˜o do mesmo tipo.

10.2.1 Matrizes em Pascal

Para se declarar uma matriz de 200 posic¸o˜es inteiras, sendo 20 na vertical e 10 na hori-
zontal, a linguagem Pascal usa a seguinte sintaxe (lembre-se que em outras linguagens
a sintaxe pode ser diferente):

var m: array [1 . .20 ,1. .10] of integer ;

A construc¸a˜o “1..20,1..10” indica que existem 20 posic¸o˜es na horizontal (linhas) e
10 na vertical (colunas). O “of integer” indica que cada posic¸a˜o e´ para se guardar um
nu´mero inteiro, isto e´ 2 bytes (dependendo da implementac¸a˜o).

Todas as restric¸o˜es e variantes que usamos para os vetores valem tambe´m para as
matrizes. Isto e´, as declarac¸o˜es seguintes tambe´m sa˜o va´lidas:

var m: array [0 . .19 ,0 . .9 ] of integer ;

var m: array [21..40,−19..−10] of integer ;

var m: array [−19..0 ,51..60] of integer ;

const maxLin=20, maxCol=10;
var m: array [ 1 . .maxLin, 1 . .maxCol] of integer ;

Agora, para escrever um valor qualquer, digamos 12345, na linha 15 e coluna 7 da
matriz m, em Pascal, se usa um dos dois comandos seguintes:

m[15 ,7]:= 12345;

read(m[15 ,7]) ; (∗ e se digita 12345 no teclado ∗)

Por exemplo, a matriz abaixo tem 5 linhas e 4 colunas e pode ser visualizada do
modo padra˜o:

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

180 CAPI´TULO 10. ESTRUTURAS DE DADOS

A declarac¸a˜o do tipo matriz em Pascal e´ assim:

type matriz= array [1..5,1..4] of integer;

No exemplo acima, a primeira linha e´ constitu´ıda pelos elementos seguintes: 4, 6,
2 e 1. A terceira coluna pelos elementos 2, 0, 3, 3 e 0. Podemos destacar a t´ıtulo de
exemplo alguns elementos da matriz. Consideremos uma varia´vel m do tipo matriz.
Enta˜o: m[3, 2] = 7, m[2, 3] = 0, m[3, 4] = 9, e assim por diante.

Notem que, isoladamente, cada linha ou coluna completa pode ser imaginada como
sendo um vetor. De fato, uma outra maneira de se ver uma matriz e´ como sendo um
vetor de vetores! Confira a declarac¸a˜o seguinte:

type vetor= array [ 1 . . 4 ] of integer ;
matriz= array [ 1 . . 5 ] of vetor ;

var m: matriz ;

Em Pascal, e´ correto dizer que, para o exemplo acima: m[3][2] = 7, m[2][3] = 0,
m[3][4] = 9, e assim por diante. No´s usaremos a construc¸a˜o apresentada inicialmente.

10.2.2 Exemplos elementares

Do mesmo modo como fizemos para os vetores, vamos iniciar o estudo das matrizes
apresentando problemas simples.

Lendo e imprimindo matrizes

A leitura dos elementos de uma matriz e´ bastante parecida com a leitura de vetores.
Imaginando que cada linha da matriz e´ um vetor, basta fixar uma linha e ler todos os
elementos das colunas. Agora e´ so´ repetir o procedimento para todas as linhas. Isto
leva naturalmente a um co´digo com um lac¸o duplo: um para variar as linhas o outro
para as colunas. A figura 10.38 permite visualizar o co´digo para a leitura de uma
matriz.

program ler matriz ;
var w: array [0 . .50 ,1. .10] of real ;

i , j : integer ;

begin
for i := 0 to 50 do

for j:= 1 to 10 do
read (w[ i , j ] ) ;

end.

Figura 10.38: Lendo uma matrizes.

Da forma como foi constru´ıdo, este co´digo exige que se digite os elementos da
primeira linha, depois os da segunda e assim por diante. No lac¸o mais interno, con-
trolado pelo j, observem que o i e´ fixo, apenas o j varia, desta forma, a leitura das

10.2. MATRIZES 181

colunas de uma linha fixa e´ ideˆntico a ler um vetor. O lac¸o mais externo, controlado
pelo i, faz variar todas as linhas.

Da mesma forma como apresentamos os vetores, vamos mostrar os co´digos ape-
nas em termos de procedimentos e func¸o˜es. Para isto vamos precisar considerar as
seguintes definic¸o˜es:

const maxLin = 50; maxCol = 40;
type matriz= array [ 0 . .maxLin, 1 . .maxCol] of real ;

Tambe´m vamos considerar que apenas uma parte da matriz sera´ usada, logo pre-
cisaremos sempre fazer a leitura das dimenso˜es de uma matriz. Neste sentido, a
figura 10.39 apresenta um procedimento que leˆ uma matriz de dimenso˜es n×m.
procedure ler (var w: matriz ; var n, m: integer) ;
var i , j : integer ;
begin

read (n) ; (∗ n deve estar no intervalo 1..maxLin ∗)
read (m) ; (∗ m deve estar no intervalo 1..maxCol ∗)

for i := 1 to n do
for j:= 1 to m do

read (w[ i , j ] ) ;
end;

Figura 10.39: Procedimento para ler uma matriz.

As mesmas observac¸o˜es sobre passagem de paraˆmetros que foram feitas sobre os ve-
tores se aplicam aqui, isto e´, pelo overhead, sempre passamos matrizes por refereˆncia.
A figura 10.40 apresenta um procedimento para impressa˜o de uma matriz usando
passagem de paraˆmetros por refereˆncia, embora na˜o fosse estritamente necessa´rio. O
procedimento foi constru´ıdo para imprimir a matriz linha por linha.

procedure imprimir (var w: matriz ; n,m: integer) ;
var i , j : integer ;
begin

for i := 1 to n do
begin

for j:= 1 to m do
write (w[ i , j ] ,’ ’) ;

writeln ; (∗ muda de linha a cada fim de coluna ∗)
end;

end;

Figura 10.40: Procedimento para imprimir uma matriz.

Tomando como exemplo a matriz do in´ıcio desta sec¸a˜o, se forem digitados todos os
valores, linha por linha, para cada uma do in´ıcio ate´ o final de cada coluna, ter´ıamos
em memo´ria algo como ilustrado na figura seguinte:

182 CAPI´TULO 10. ESTRUTURAS DE DADOS

1 2 3 4 5 . . . 40
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 ? ?
...

50 ? ? ? ? ? ?

A t´ıtulo de exemplo, poder´ıamos construir um procedimento que imprime a matriz
em sua forma transposta, isto e´, com as linhas e colunas invertidas. Isto e´ apresentado
na figura 10.41. Basta inverter i e j no comando de impressa˜o! Observem que a matriz
na˜o mudou na memo´ria, apenas a impressa˜o e´ diferente.

procedure imprimir transposta (var w: matriz ; n,m: integer) ;
var i , j : integer ;
begin

for i := 1 to n do
begin

for j:= 1 to m do
write (w[ j , i ] ,’ ’) ; (∗ i e j invertidos imprime transposta ∗)

writeln ;
end;

end;

Figura 10.41: Procedimento para imprimir a transposta de uma matriz.

Outros procedimentos interessantes sa˜o os de impressa˜o de apenas uma certa linha
(figura 10.42) ou de apenas uma certa coluna (figura 10.43).

procedure imprimir uma linha (var w: matriz ; n,m: integer ; K: integer) ;
(∗ imprime a linha K da matriz ∗)
var j : integer ;
begin

for j:= 1 to m do
write (w[K, j ] ,’ ’) ; (∗ K fixo na primeira posicao ∗)

writeln ;
end;

Figura 10.42: Procedimento para imprimir uma unica linha da matriz.

Considerando o exemplo acima e fazendo K = 2 ter´ıamos a seguinte sa´ıda:

9 0 0 2

Considerando o exemplo acima e fazendo K = 2 ter´ıamos a seguinte sa´ıda:

10.2. MATRIZES 183

procedure imprimir uma coluna(var w: matriz ; n,m: integer ; K: integer) ;
(∗ imprime a coluna K da matriz ∗)
var i : integer ;
begin

for i := 1 to n do
writeln (w[ i ,K] ,’ ’) ; (∗ K fixo na segunda posicao