ALGORITMOS COM PASCAL matriz

Prévia do material em texto

ALGORITMOS COM PASCAL
Prof. Miguel Jonathan – Dept. Ciência da Computação – IM/UFRJ
CAPíTULO 5
 
Variáveis Compostas Homogêneas - Vetores e Matrizes
 
Um vetor (array em inglês) é um agregado de variáveis do mesmo tipo (homogêneas). O exemplo abaixo mostra a representação gráfica de um vetor de 6 inteiros chamado v:
 
 1 2 3 4 5 6
 
 
 
Cada “casa” , ou “elemento”, do vetor é uma variável independente. No exemplo acima, cada elemento pode conter um valor inteiro, e as posições foram ordenadas de 1 até 6. Os elementos de um vetor são identificados pelo nome do vetor associado ao número de ordem da sua posição relativa no vetor: v[1], v[2], v[3], v[4], v[5] e v[6].
 
Assim, no caso acima, a variável v[2] tem o valor 67.
Podemos alterar esse valor exatamente como fazemos com qualquer variável:
v[2] := 100; 
readln(v[2]);
 
etc.
 
Para declarar esse vetor em um programa Pascal, é usada a forma abaixo:
var
 v: array[1..6] of integer;
 
A forma geral é: 
var <identificador do vetor>: array [<intervalo das posições>] of <tipo dos valores do vetor>
 
Cada variável do conjunto é representada por:
 <identificador do vetor>[<expressão cujo valor é a posição da variável> ]
onde a expressão deve ser do tipo declarado.
 
Por exemplo, a variável na posição 3 do vetor pode ser representada por:
 v[3] v[10-7] v[5*5-2*11] v[x-4], supondo que x tenha o valor 7, etc.
 
 
Uso do comando for com vetores
 
A manipulação de vetores é grandemente facilitada pelo uso dos comandos de repetição, especialmente o for. Por exemplo, para zerar (colocar o valor 0) todas as posições do vetor v definido acima, seria necessário escrever 6 comandos:
v[1]:= 0; 
v[2]:= 0; 
v[3]:= 0; 
v[4]:= 0; 
v[5]:= 0; 
v[6]:= 0;
 
A mesma operação pode ser feita com apenas um comando de repetição for, usando uma variável de controle para representar as posições do vetor:
 for i:= 1 to 6 do v[i]:=0;
É fácil imaginar o que isso representa de simplificação para a manipulação de vetores grandes.
 
Da mesma forma, para ler do teclado todos os valores do vetor v, seriam também necessários 6 comandos:
read (v[1]); 
read (v[2]); 
read (v[3]); 
read (v[4]); 
read (v[5]); 
read (v[6]); 
 
Todos esses comandos podem ser substituídos por um único comando for:
 for i:= 1 to 6 do read(v[i]);
 
O que se pode e o que não se pode fazer com vetores, na linguagem Pascal:
Nota: essas regras não se aplicam ao tipo string que é um caso especial de vetor de caracteres com regras própria, e que será visto mais adiante.
 
Não é possível:
a) Não se pode ler todo um vetor diretamente com um comando read. Não se pode escrever: read(v);
É necessário ler casa a casa, diretamente, ou com um laço de repetição como for no exemplo acima.
b) Não se pode escrever todos os elementos de um vetor com um único comando write. Não é permitido escrever: write(v). Também nesse caso cada elemento deve ser tratado como uma variável independente, por exemplo: 
 for i:= 1 to 6 do write(v[i]:3);
c) Não é possível copiar os valores dos elementos de um vetor para outro com um único comando de atribuição. Ou seja, dados dois vetores v e w, ambos do mesmo tamanho e do mesmo tipo, não é permitido fazer: w:= v; . Também aqui é necessário trabalhar elemento a elemento, e o comando for mais uma vez é indicado:
 for i:= 1 to 6 do w[i]:= v[i];
c) Não existe comandos ou funções que dão o tamanho (número de elementos) de um vetor.
d) Não é permitido tentar acessar uma posição fora do intervalo de posições definido para o vetor. A tentativa causará um erro em tempo de execução e o programa abortará. No caso do vetor v acima, por exemplo, não é permitido escrever: v[8]:= 20, read(v[8]) ou write (v[8]) porque a faixa de valores das posições vai de 1 a 6 apenas. 
 
O que é permitido:
a) A faixa de valores das posições não precisa começar em 1. Qualquer intervalo de valores pode ser usado na definição de um vetor. Por exemplo, podemos definir um vetor assim:
var v:array[15..20] of real;
Nesse caso o vetor v terá apenas os elementos: v[15], v[16], v[17], v[18], v[19] e v[20]
b) As posições não precisam ser necessariamente números inteiros. Podem ser qualquer tipo ordinal, ou seja, que possa ser definido por uma seqüência ordenada de valores. Por exemplo, os caracteres em Pascal formam uma seqüência ordenada na tabela de caracteres, e podem portanto serem marcadores de posição em um vetor.
Podemos definir um vetor assim: 
 var letras: array['a'..'z'] of integer;
Nesse caso os elementos do vetor são: letras['a'], letras['b'], ….., letras['z']
Um uso possível para esse vetor poderia ser que cada posição poderia guardar a quantidade de vezes que a letra dessa posição aparece em uma determinada frase.
 
 
Exemplos de uso:
 
Ordenação de números:
Fazer um programa para ler n valores inteiros quaisquer, n <50, onde o valor de n deve ser previamente fornecido pelo usuário. 
Em seguida, o programa deve escrever na tela os valores em ordem numérica crescente. 
A solução utiliza um algoritmo de ordenação . 
O algoritmo abaixo é conhecido como ordenação por seleção. Os números são colocados em um vetor definido com 50 posições. Inicialmente, procura-se a posição no vetor (posMenor) onde está o menor número. Se essa posição for diferente da posição 1, então troca-se os valores das casas 1 e posMenor. Isso garante que o menor elemento agora está na posição 1. A seguir, repete-se o processo a partir da posição 2. Ou seja, procura-se a posição do menor elemento da posição 2 em diante, que será posMenor. Se o valor de posMenor for diferente de 2, troca-se os valores das casas 2 e posMenor. O processo é repetido a partir da posição 3, depois 4, etc, até n-1. Nesse ponto o vetor estará com os valores ordenados. Basta então escrever na tela os valores das posições 1 a n e teremos os números em ordem crescente.
 
program ordenasel;
const nmax=50;
var
 v: array[1..nmax] of integer;
 i,j,n,posMenor,temp: integer;
begin
 writeln('Digite um inteiro menor ou igual a ' ,nmax, ' : '); readln(n);
 writeln('Digite ',n,' inteiros separados por espacos');
 for i:=1 to n do read(v[i]);
 for i:=1 to n-1 do begin
 posMenor:=i;
 for j:=i+1 to n do 
 if v[j] < v[posMenor] then posMenor := j;
 if i <> posMenor then begin
 temp := v[i];
 v[i] := v[posMenor];
 v[posMenor] := temp;
 end;
 end;
 writeln;
 for i:=1 to n do write(v[i]:4);
end.
 
 
O tipo STRING
 
A linguagem Pascal original não possuía o tipo string. Hoje em dia, todas as versões modernas de Pascal estendido possuem esse tipo (Turbo Pascal, Free Pascal, etc).
 
O tipo string é um caso especial de vetor de caracteres criado especialmente para tratar com texto: palavras, frases, etc, onde a seqüência de caracteres deve ser tratada como uma única entidade. A palavra string significa uma cadeia de caracteres. Cada posição de uma string contém apenas um caractere.
 
A definição de uma variável é: var frase: string;
 
Não há necessidade de se definir um tamanho máximo, embora seja possível: 
 var nome: string[15];
 
Se não for definido um tamanho máximo, a string poderá expandir-se ou encolher-se automaticamente para acomodar a quantidade de caracteres necessária. 
 
As regras para vetores em geral não se aplicam às strings. Em particular, é permitido paara strings: 
a)      ler uma string inteira com um único comando read ou readln: readln(frase);
b)      escrever uma string inteira com um único comando write ou writeln: writeln(frase);
c)      atribuir uma string diretamente: frase2:= frase;
d)      escrever o valor literal deuma string entre aspas simples e usar em comandos de atribuição ou de escrita: frase:= ‘rio de janeiro’; write(‘rio de janeiro’); 
e)      Caracteres individuais e strings podem ser usados de forma idêntica:
	frase:= ‘a’; faz a string frase ser uma string com apenas o caractere ‘a’.
f)        O uso da função length() que dá o tamanho (número de caracteres) de uma string.
g)      O uso do operador de concatenação +, que permite unir duas strings produzindo uma string que é a concatenação das duas: ‘ab’ + ‘cd’ produz a string ‘abcd’. O mesmo pode ser obtido com a função concat(). Também aqui pode-se misturar strings com caracteres de qualquer maneira: ‘a’ + ‘b’ dá a string ‘ab’, etc. O operador e a função podem ser usados para concatenar varias strings e/ou caracteres:
Ex: frase := frase1 + frase2 + ‘!’;
 frase := concat(frase1, frase2, ‘!’);
h) É possível comparar duas strings diretamente, usando os operadores relacionais =, <>, >, <, >=, e <=, onde a comparação é feita pela ordem dos elementos na tabela de caracteres, o que garante a ordem alfabética para strings contendo apenas letras maiúsculas ou apenas minúsculas: 
 	‘cde’ < ‘fgh’ dará true e ‘AB’ = ‘CD’ dará false
i) A posição zero de uma string contém sempre um número inteiro que é o tamanho da string. Esse valor pode ser obtido usando a função ord(). Por exemplo, para imprimir o tamanho da string frase, pode-se escrever: write ( ord(frase[0]); Na realidade a função length() obtém o seu valor consultando a posição 0 da string.
 
Com esses conhecimentos, podemos adaptar muito facilmente o algoritmo de ordenação por seleção, descrito acima para vetores de números, para ordenar um vetor de nomes em ordem alfabética, assumindo que estão todos escritos em letras da mesma caixa (maiúsculas ou minúsculas). Note que isso só foi possível por causa das regras especiais para strings, e que é possível também se criar um vetor de strings:
 
 
program ordenanomes;
(**********************************************************************
 algoritmo de selacao para ordenar nomes em ordem alfabética.
**********************************************************************)
const nmax=50;
var
 v: array[1..nmax] of string;
 i,j,n,posMenor: integer;
 temp:string;
begin
 writeln('Digite um inteiro menor ou igual a ' ,nmax, ' : '); readln(n);
 writeln('Digite ',n,' strings, uma em cada linha);
 for i:=1 to n do readln(v[i]);
 for i:=1 to n-1 do begin
 posMenor:=i;
 for j:=i+1 to n do 
 if v[j] < v[posMenor] then posMenor := j;
 if i <> posMenor then begin
 temp := v[i];
 v[i] := v[posMenor];
 v[posMenor] := temp;
 end;
 end;
 writeln;
 for i:=1 to n do writeln(v[i]);
end.
 
 
 
MATRIZES – vetores com mais de 1 dimensão:
 
Os elementos de um vetor guardam uma relação de posicionamento entre si apenas em uma dimensão. Essas variáveis estão dispostas como que em uma linha, e cada elemento é identificado pela sua posição relativa na linha:
 
	20
	30
	17
	35
	7
 1 2 3 4 5 (posições na linha)
 
Quando há mais de uma dimensão, damos o nome de matriz a esse arranjo de variáveis. O caso mais comum é a matriz de 2 dimensões. Os elementos ficam dispostos em um plano, composto por várias linhas do mesmo tamanho, como abaixo:
 
colunas (
	1
	40
	34
	50
	27
	2
	25
	4
	18
	80
	3
	0
	3
	65
	11
	 
	1
	2
	3
	4
linhas
↓
 
 
 
 
Na matriz de inteiros acima, existem 3 linhas, cada linha com 4 colunas, ou 3x4 (três por quatro). Essa matriz pode ser declarada assim:
var mat: array[1..3, 1..4] of integer;
Após o nome da matriz, são colocados entre colchetes os intervalos em que ficam os números das linhas, e os números das colunas, nessa ordem. Note que também aqui os elementos da matriz devem ser todos do mesmo tipo.
Cada elemento da matriz é identificado pela notação: mat[i,j], onde i é o número da linha, e j o número da coluna, onde se encontra o elemento. Na figura acima, temos então que mat[1,1] tem o valor 40.
O comando for... do é muito usado para processar os valores de matrizes. 
Exemplos:
 
a) Para zerar todos os elementos de uma matriz m, com 3 linhas e 4 colunas, declarada como:
var
 m: array[1..3, 1..4] of integer;
 
basta fazer:
for i:= 1 to 3 do
 for j:= 1 to 4 do m[i,j] := 0;
 
Nota: é usual usar-se a variável i para representar as linhas de uma matriz, a variável j para representar as colunas.
 
b) Para ler do teclado valores para preencher a matriz acima (12 valores):
for i:= 1 to 3 do
 for j:= 1 to 4 do read(m[i,j] );
 
Nota: O usuário poderá digitar todos os 12 números em uma só linha (separados por espaços), ou um número por linha, ou, melhor, 4 números por linha, de forma a visualizar melhor a matriz. 
 
24�
�
67�
�
5�
�
94�
�
12	q2��
�
10	q2��
�