apostila
259 pág.

apostila


DisciplinaAlgoritmos e Estrutura de Dados I702 materiais7.920 seguidores
Pré-visualização50 páginas
de freque\u2c6ncias
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\u2dces de mu´ltipla escolha, onde as respostas sa\u2dco 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´\u131cula (um inteiro) e as respectivas respostas. O programa deve calcular e
escrever:
\u2022 a relac¸a\u2dco de alunos ordenados pela nota, supondo que cada questa\u2dco vale 5 pontos;
\u2022 para cada questa\u2dco: quantos alunos acertaram a questa\u2dco
10.2. MATRIZES 179
10.2 Matrizes
Assim como os vetores, as matrizes sa\u2dco arrays. Os vetores sa\u2dco estruturas unidimen-
sionais enquanto que as matrizes sa\u2dco bidimensionais. Isto e´, o acesso a`s posic¸o\u2dces de
memo´ria de um vetor sa\u2dco feitas com base em duas informac¸o\u2dces: 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\u2dco do mesmo tipo.
10.2.1 Matrizes em Pascal
Para se declarar uma matriz de 200 posic¸o\u2dces 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\u2dco \u201c1..20,1..10\u201d indica que existem 20 posic¸o\u2dces na horizontal (linhas) e
10 na vertical (colunas). O \u201cof integer\u201d indica que cada posic¸a\u2dco e´ para se guardar um
nu´mero inteiro, isto e´ 2 bytes (dependendo da implementac¸a\u2dco).
Todas as restric¸o\u2dces e variantes que usamos para os vetores valem tambe´m para as
matrizes. Isto e´, as declarac¸o\u2dces seguintes tambe´m sa\u2dco va´lidas:
var m: array [0 . .19 ,0 . .9 ] of integer ;
var m: array [21..40,\u221219..\u221210] of integer ;
var m: array [\u221219..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]) ; (\u2217 e se digita 12345 no teclado \u2217)
Por exemplo, a matriz abaixo tem 5 linhas e 4 colunas e pode ser visualizada do
modo padra\u2dco:
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\u2dco do tipo matriz em Pascal e´ assim:
type matriz= array [1..5,1..4] of integer;
No exemplo acima, a primeira linha e´ constitu´\u131da pelos elementos seguintes: 4, 6,
2 e 1. A terceira coluna pelos elementos 2, 0, 3, 3 e 0. Podemos destacar a t´\u131tulo de
exemplo alguns elementos da matriz. Consideremos uma varia´vel m do tipo matriz.
Enta\u2dco: 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\u2dco 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\u2dco 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´\u131do, 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\u2c6ntico 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\u2dces. Para isto vamos precisar considerar as
seguintes definic¸o\u2dces:
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\u2dces de uma matriz. Neste sentido, a
figura 10.39 apresenta um procedimento que le\u2c6 uma matriz de dimenso\u2dces n×m.
procedure ler (var w: matriz ; var n, m: integer) ;
var i , j : integer ;
begin
read (n) ; (\u2217 n deve estar no intervalo 1..maxLin \u2217)
read (m) ; (\u2217 m deve estar no intervalo 1..maxCol \u2217)
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\u2dces sobre passagem de para\u2c6metros que foram feitas sobre os ve-
tores se aplicam aqui, isto e´, pelo overhead, sempre passamos matrizes por refere\u2c6ncia.
A figura 10.40 apresenta um procedimento para impressa\u2dco de uma matriz usando
passagem de para\u2c6metros por refere\u2c6ncia, embora na\u2dco fosse estritamente necessa´rio. O
procedimento foi constru´\u131do 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 ] ,\u2019 \u2019) ;
writeln ; (\u2217 muda de linha a cada fim de coluna \u2217)
end;
end;
Figura 10.40: Procedimento para imprimir uma matriz.
Tomando como exemplo a matriz do in´\u131cio desta sec¸a\u2dco, se forem digitados todos os
valores, linha por linha, para cada uma do in´\u131cio ate´ o final de cada coluna, ter´\u131amos
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´\u131tulo de exemplo, poder´\u131amos 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\u2dco! Observem que a matriz
na\u2dco mudou na memo´ria, apenas a impressa\u2dco 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 ] ,\u2019 \u2019) ; (\u2217 i e j invertidos imprime transposta \u2217)
writeln ;
end;
end;
Figura 10.41: Procedimento para imprimir a transposta de uma matriz.
Outros procedimentos interessantes sa\u2dco os de impressa\u2dco 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) ;
(\u2217 imprime a linha K da matriz \u2217)
var j : integer ;
begin
for j:= 1 to m do
write (w[K, j ] ,\u2019 \u2019) ; (\u2217 K fixo na primeira posicao \u2217)
writeln ;
end;
Figura 10.42: Procedimento para imprimir uma unica linha da matriz.
Considerando o exemplo acima e fazendo K = 2 ter´\u131amos a seguinte sa´\u131da:
9 0 0 2
Considerando o exemplo acima e fazendo K = 2 ter´\u131amos a seguinte sa´\u131da:
10.2. MATRIZES 183
procedure imprimir uma coluna(var w: matriz ; n,m: integer ; K: integer) ;
(\u2217 imprime a coluna K da matriz \u2217)
var i : integer ;
begin
for i := 1 to n do
writeln (w[ i ,K] ,\u2019 \u2019) ; (\u2217 K fixo na segunda posicao