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