MC102
Algoritmos e Programação de Computadores
Parte XXII


Norton Trevisan Roman




VETORES (ARRAY)

Lembra de nosso programa que tirava a média de n números inteiros? Vamos repetí-lo para 10 números: 

    PROGRAM notas;
    VAR num   : integer; {número digitado}
        media : real;    {média dos dados}
        cont  : integer; {contador do for}
        soma  : integer; {soma dos dados}
    BEGIN
      soma := 0;

      FOR cont := 1 TO 10 DO
      BEGIN
        write('entre um dado: ');
        readln(num);
        soma := soma + num
      END;

      media := soma / n;
      writeln('a média é ',media:4:2)
    END.

Mas, e se quiséssemos guardar os vários valores de num? Como fazemos? Usamos um vetor (array): 

    PROGRAM notas;
1.  VAR num   : ARRAY[1..10] OF integer; {vetor dos números digitados}
        media : real;                    {média dos dados}
        cont  : integer;                 {contador do FOR}
        soma  : real;                    {soma dos dados}
    BEGIN
      soma := 0;

      FOR cont := 1 TO 10 DO
      BEGIN
        write('entre um dado: ');
2.      readln(num[cont]);
3.      soma := soma + num[cont]
      END;

      media := soma / n;
      writeln('a média é ',media:4:2)
    END.

Agora vamos por partes. antes de mais nada, o que é um vetor? Um vetor pode ser pensado como uma variável que consegue guardar vários valores de um determinado tipo. Assim, quando definimos: 

    VAR num : ARRAY[1..10] OF integer; {vetor dos números digitados}

estamos criando uma variável, chamada num, que é capaz de guardar até 10 inteiros. Ou seja, na prática, esta seria uma variável assim:

1 2 3 4 5 6 7 8 9 10

onde em cada quadrado cabe um inteiro.

Então, quando fazemos 

  n[5] := 20;

estamos colocando o inteiro 20 na 5ª posição do vetor:

1 2 3 4 5 6 7 8 9 10
20

Veja que, na linha 2 do nosso programa acima, abastecemos cada posição de "num" (usando, para isso, o contador "cont") com o inteiro dado pelo usuário.

Agora, como usamos esses valores armazenados? Da mesma forma que uma variável comum, só que com sintaxe um pouco diferente (veja a linha 3 do nosso programa): 

  VAR n : ARRAY[1..10] OF integer;
      x : integer;

  BEGIN
    x := n[8]; {x recebe o valor que está na 8ª posição do vetor}
    x := n[3] + 2*n[5]; {x recebe o dobro do valor que está na 5ª posição
                         somado ao que está na 3ª posição do vetor}

A forma geral da declaração de um vetor é: 

  ARRAY[limite_inferior..limite_superior] OF tipo;

Naturalmente, podemos definir um tipo com o vetor: 

  TYPE vetor = ARRAY[1..10] OF integer;

  VAR v : vetor;

A vantagem desse uso é que posso passar um vetor como parâmetro de uma função ou procedimento. Assim, posso fazer: 

  TYPE vetor = ARRAY[1..10] OF integer;

  VAR v : vetor;

  PROCEDURE P(x : vetor);
  BEGIN
    ...
  END;

Vale notar que, como na passagem por valor, o valor da variável é copiado para o parâmetro, x será um vetor que conterá uma cópia dos valores contidos no vetor a ele passado.

Como isso pode consumir muita memória, se o vetor for grande, é aconselhável efetuar a passagem por referência, desse modo: 

  TYPE vetor = ARRAY[1..10] OF integer;

  VAR v : vetor;

  PROCEDURE P(VAR x : vetor);
  BEGIN
    ...
  END;

Essa, na verdade, é a única maneira de se passar um vetor como parâmetro, já que o seguinte não é permitido: 

  PROCEDURE P(x : ARRAY[1..10] OF integer;);
  BEGIN
    ...
  END;

Da mesma forma, posso usar esse tipo como o retorno de uma função: 

  TYPE vetor = ARRAY[1..10] OF integer;

  VAR v : vetor;

  FUNCTION F(x : real) : vetor;
  BEGIN
    ...
  END;

  BEGIN
    v := F(2.3);
  END.

enquanto que o mostrado abaixo não é permitido: 

  TYPE vetor = ARRAY[1..10] OF integer;

  VAR v : vetor;

  FUNCTION F(x : real) : ARRAY[1..10] OF integer;
  BEGIN
    ...
  END;

  BEGIN
    v := F(2.3);
  END.

Atenção: alguns compiladores só aceitam tipos simples como retorno de função, ou seja, nem esse artifício acima funciona. Para esses, você não poderá usar funções, terá que escrever tudo na forma de precedimentos.

Vamos agora dar uma olhada no tipo dos dados que um vetor pode conter. Primeiro, que tipos são aceitos? Qualquer um! Então, posso ter: 

  TYPE cor      = (verde,vermelho,azul);
       complexo = RECORD
                    re :real;
		    im : real
                  END;
       vetor1   = ARRAY[1..10] OF cor;
       vetor2   = ARRAY[1..10] OF complexo;
       vetor3   = ARRAY[1..10] OF real;

  VAR v1 : vetor1;
      v2 : vetor2;
      v3 : vetor3;

  BEGIN
    {carrego a 2ª posição de v1 com "verde"}
    v1[2] := verde;

    {carrego a 5ª posição de v2 com "3 - 4i"}
    v2[5].re := 3;
    v2[5].im := -4;

    {carrego a 3ª posição de v2 com "2 + 3i"}
    v2[3].re := 2;
    v2[3].im := 3;

    {somo o imaginário da 3ª posição ao da 5ª e guardo na 10ª}
    v2[10].re := v2[5].re + v2[3].re;
    v2[10].im := v2[5].im + v2[3].im;

    {guardo na 1ª posição de v3 o módulo do complexo na posição 10 de v2}
    v3[1] := Sqr(v2[10].re) + Sqr(v2[10].im)
  END.

Reparou como faço para guardar e usar valores registro que estão dentro de vetores? É só fazer 

  variável_do_vetor[índice].nome_do_campo

E quanto aos limites do vetor? Bom, esses, na verdade, devem ser um conjunto de valores seqüenciais: 

  TYPE limites  = 15..20;
       cor      = (vermelho, verde, azul);
       inferior = 12;
       superior = 15;

  VAR v1 : ARRAY[inferior..superior] OF real;
      v2 : ARRAY[limites] OF integer;
      v3 : ARRAY[cor] OF char;
      v4 : ARRAY['a'..'z'] OF cor;
      v5 : ARRAY['1'..'5'] OF boolean;

e como acessamos ou guardamos valores nos vetores acima? 

  TYPE limites  = 15..20;
       cor      = (vermelho, verde, azul);
       inferior = 12;
       superior = 15;

  VAR v1 : ARRAY[inferior..superior] OF real;
      v2 : ARRAY[limites] OF integer;
      v3 : ARRAY[cor] OF char;
      v4 : ARRAY['a'..'z'] OF cor;
      v5 : ARRAY['1'..'5'] OF boolean;

  BEGIN
    v1[14] := 3.16;
    v2[16] := 12;
    v3[verde] := 'a';
    v4['d'] := azul;
    v5['3'] := true;

    v1[2] := v1[14] + v2[16] / 5;
    v3[azul] := Chr(Ord(v3[verde]) + 3); {terá 'd'}
    v4[v3[verde]] := vermelho; {v4['a'] := vermelho}
    v5['2'] := v5['3'] OR v5['5']
  END.

Note que os limites não precisam começar de 1. Esses valores são apenas índices, podem começar de qualquer valor, desde que o limite inferior seja maior que o superior e os valores escolhidos como índices sejam seqüenciais.

Agora, como exemplo do uso de vetores, vamos fazer um programa que conte o número de vezes que cada letra foi digitada pelo usuário. O usuário termina o texto com '#'. Repare como fazemos para contar cada letra: 

  PROGRAM contador;

  TYPE vetor = ARRAY['A'..'Z'] OF integer;

  VAR ch   : char;    {o caracter digitado}
      v    : vetor;   {guarda o número de vezes que cada letra foi digitada}
      cont : integer; {contador do FOR}

  {retorna true se c for letra, false se não}
  FUNCTION letra(c : char) : boolean;
  BEGIN
    letra := ((c>='a') AND (c<='z')) OR ((c>='A') AND (c<='Z'))
  END;

  BEGIN
    ch := readkey;

    WHILE ch<>'#' DO
    BEGIN
      {escrevo o ch na tela}
      write(ch);

      {se for letra...}
      IF letra(ch) THEN
      BEGIN
        {transformo em maiúscula}
	ch := Upcase(ch);

	{conto a letra correta - veja como faço}
        v[ch] := v[ch] + 1
      END;

      {leio o próximo}
      ch := readkey
    END;

    {imprimo o vetor}
    writeln('Resultado:');
    FOR cont:='A' TO 'Z' DO
    BEGIN
      writeln('v[',cont,'] = ',v[cont])
    END
  END.

Ao final desse programa, o vetor v será algo como:

'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K' 'L' 'M' 'N' 'O' 'P' 'Q' 'R' 'S' 'T' 'U' 'V' 'W' 'X' 'Y' 'Z'
100 20 10 5 7 6 12 3 43 23 6 7 54 3 6 0 23 65 23 1 9 57 0 12 5 0

Ou seja, cada índice contém, em seu elemento correspondente no vetor, o número de vezes que a letra do índice foi digitada no texto.

Vejamos outro exemplo, a coidificação de um texto. Nesse exemplo, o usuário digita um caracter e, se este for letra, nós o codificamos conforme a seguinte chave:

Caracter Código Caracter Código
'A' 'C' 'N' 'K'
'B' 'Z' 'O' 'L'
'C' 'O' 'P' 'S'
'D' 'R' 'Q' 'E'
'E' 'A' 'R' 'H'
'F' 'G' 'S' 'M'
'G' 'B' 'T' 'P'
'H' 'N' 'U' 'I'
'I' 'U' 'V' 'X'
'J' 'T' 'W' 'Q'
'K' 'D' 'X' 'V'
'L' 'Y' 'Y' 'J'
'M' 'F' 'Z' 'W'

Queremos, então, um programa que leia o caracter digitado pelo usuário, o substitua pelo caracter do código e escreva este último, mostrando ao usuário. Novamente, façamos o texto ser terminado por '#'. 

  PROGRAM codigo;

  TYPE vetor = ARRAY['A'..'Z'] OF integer;

  VAR ch    : char;    {o caracter digitado}
      chave : vetor;   {guarda a chave do código}

  {retorna true se c for letra, false se não}
  FUNCTION letra(c : char) : boolean;
  BEGIN
    letra := ((c>='a') AND (c<='z')) OR ((c>='A') AND (c<='Z'))
  END;

  {retorna true se c for letra maiuscula}
  FUNCTION maiuscula(c : char) : boolean;
  BEGIN
    maiuscula := letra(c) AND (c >= 'A') AND (c <= 'Z')
  END;

  {retorna a correspondente minúscula de c}
  FUNCTION mai_para_min(c : char) : char;
  BEGIN
    IF maiuscula(c) THEN mai_para_min := Chr(Ord(c) - Ord('A') + Ord('a'))
    ELSE mai_para_min := c
  END;

  {inicializa a chave}
  PROCEDURE inicializa(c : vetor);
  BEGIN
    v['A'] := 'C';
    v['B'] := 'Z';
    v['C'] := 'O';
    v['D'] := 'R';
    v['E'] := 'A';
    v['F'] := 'G';
    v['G'] := 'B';
    v['H'] := 'V';
    v['I'] := 'U';
    v['J'] := 'T';
    v['K'] := 'D';
    v['L'] := 'Y';
    v['M'] := 'F';
    v['N'] := 'K';
    v['O'] := 'L';
    v['P'] := 'S';
    v['Q'] := 'E';
    v['R'] := 'H';
    v['S'] := 'M';
    v['T'] := 'P';
    v['U'] := 'I';
    v['V'] := 'X';
    v['W'] := 'Q';
    v['X'] := 'V';
    v['Y'] := 'J';
    v['Z'] := 'W'
  END;

  BEGIN
    ch := readkey;

    WHILE ch<>'#' DO
    BEGIN
      IF letra(ch) THEN
      BEGIN
        IF maiuscula(ch) THEN write(v[ch])
	ELSE {é minúscula}
	  write(mai_para_min(v[Upercase(ch)]))
      END
      ELSE {não é letra}
        write(ch);

      {leio a próxima}
      ch := readkey
    END
  END.

Estude bem esse programa.



MATRIZES

Vetores também podem ser usados para representar matrizes. Considere a matriz:

[
1 2
3 4
]

Seria interessante podermos representar isso, não? Como faríamos? Podemos criar um vetor de vetores: 

  TYPE coluna = ARRAY[1..2] OF integer;
       matriz = ARRAY[1..2] OF coluna;

e como abasteceríamos a matriz nessa estrutura de dados? 

  TYPE coluna = ARRAY[1..2] OF integer;
       matriz = ARRAY[1..2] OF coluna;

  VAR m : matriz;

  BEGIN
    m[1][1] := 1;
    m[1][2] := 2;
    m[2][1] := 3;
    m[2][2] := 4
  END.

Bastante truculento, não é? Bem, felizmente o Pascal tem um modo mais fácil de representar uma matriz: 

  TYPE matriz = ARRAY[1..2,1..2] OF integer;

  VAR m : matriz;

  BEGIN
    m[1,1] := 1;
    m[1,2] := 2;
    m[2,1] := 3;
    m[2,2] := 4
  END.

Simples, não? Nós agora representamos uma matriz 2 × 2. Considere agora a matriz 3 × 3:

A = [
1 2 3
4 5 6
7 8 9
]

Como podemos representá-la em Pascal? 

  TYPE matriz = ARRAY[1..3,1..3] OF integer;

  VAR A : matriz;

  BEGIN
    A[1,1] := 1;
    A[1,2] := 2;
    A[1,3] := 3;
    A[2,1] := 4;
    A[2,2] := 5;
    A[2,3] := 6;
    A[3,1] := 7;
    A[3,2] := 8;
    A[3,3] := 9
  END.

Note que a prepresentação do elemento Ai,j é A[i,j]. Realmente mnemônico.

Como representamos agora uma matriz 3 × 2, como a abaixo?

A = [
1 2
3 4
5 6
]

Assim: 

  TYPE matriz = ARRAY[1..3,1..2] OF integer;

  VAR A : matriz;

  BEGIN
    A[1,1] := 1;
    A[1,2] := 2;
    A[2,1] := 3;
    A[2,2] := 4;
    A[3,1] := 5;
    A[3,2] := 6
  END.

E a 2 × 3 abaixo?

A = [
1 2 3
4 5 6
]

Assim: 

  TYPE matriz = ARRAY[1..2,1..3] OF integer;

  VAR A : matriz;

  BEGIN
    A[1,1] := 1;
    A[1,2] := 2;
    A[1,3] := 3;
    A[2,1] := 4;
    A[2,2] := 5;
    A[2,3] := 6
  END.

Agora podemos criar funções para soma e multiplicação de matrizes: 

  PROGRAM matrizes;

  TYPE matriz = ARRAY[1..2,1..2] OF integer;

  VAR m1,m2,m3 :matriz;

  FUNCTION soma(m1,m2:matriz) : matriz;
  BEGIN
    soma[1,1] := m1[1,1] + m2[1,1];
    soma[1,2] := m1[1,2] + m2[1,2];
    soma[2,1] := m1[2,1] + m2[2,1];
    soma[2,2] := m1[2,2] + m2[2,2]
  END;

  BEGIN
    m1[1,1] := 1;
    m1[1,2] := 2;
    m1[2,1] := 3;
    m1[2,2] := 4;
    m2[1,1] := 5;
    m2[1,2] := 6;
    m2[2,1] := 7;
    m2[2,2] := 8;

    m3 := soma(m1,m2);

    writeln(m3[1,1],' ',m3[1,2],' ',m3[2,1],' ',m3[2,2])
  END.

Novamente, alguns compiladores podem não aceitar isso, então, uma versão alternativa com procedimentos é: 

  PROGRAM matrizes;

  TYPE matriz = ARRAY[1..2,1..2] OF integer;

  VAR m1,m2,m3 :matriz;

  PROCEDURE soma(m1,m2:matriz; VAR m3:matriz);
  BEGIN
    m3[1,1] := m1[1,1] + m2[1,1];
    m3[1,2] := m1[1,2] + m2[1,2];
    m3[2,1] := m1[2,1] + m2[2,1];
    m3[2,2] := m1[2,2] + m2[2,2]
  END;

  BEGIN
    m1[1,1] := 1;
    m1[1,2] := 2;
    m1[2,1] := 3;
    m1[2,2] := 4;
    m2[1,1] := 5;
    m2[1,2] := 6;
    m2[2,1] := 7;
    m2[2,2] := 8;

    soma(m1,m2,m3);

    writeln(m3[1,1],' ',m3[1,2],' ',m3[2,1],' ',m3[2,2])
  END.

as funções para subtração, multiplicação e divisão ficam como exercício.

Então, como vimos, matrizes nada mais são que vetores em 2 dimensões. Mas, será que posso fazer em 3 dimensões? Posso fazer em quantas eu quiser... 

  PROGRAM matrizes;

  TYPE matriz3D = ARRAY[1..2,1..2,1..2] OF integer;
       matriz5D = ARRAY[1..3,1..5,1..2,1..2,1..1] of integer;

       etc

E como acesso valores nessas matrizes? 

  PROGRAM matrizes;

  TYPE matriz3D = ARRAY[1..2,1..2,1..2] OF integer;
       matriz5D = ARRAY[1..3,1..5,1..2,1..2,1..1] of integer;

  VAR m1 : matriz3D;
      m2 : matriz5D;

  BEGIN
    m1[1,2,1] := 3;
    m2[1,1,3,2,1] := 5;

    etc...
  END.

Quando você usará isso? Não sei, mas se precisar...

Por fim, como fazemos para ler todos os valores de uma matriz n × m, dados n e m, e imprimí-los na tela? (Suponha que ela já está carregada) 

  PROGRAM matrizes;

  CONST n = 20;
        m = 30;

  TYPE matriz = ARRAY[1..n,1..m] OF integer;

  VAR mat   : matriz;  {a matriz}
      cont1 : integer; {contador do primeiro FOR}
      cont2 : integer; {contador do segundo FOR}

  BEGIN
    FOR cont1:=1 TO n DO
      FOR cont2:=1 TO m DO writeln('mat[',cont1,',',cont2,'] = ',mat[cont1,cont2])
  END.

E para "zerarmos" uma matriz n × m? 

  PROGRAM matrizes;

  CONST n = 20;
        m = 30;

  TYPE matriz = ARRAY[1..n,1..m] OF integer;

  VAR mat   : matriz;  {a matriz}
      cont1 : integer; {contador do primeiro FOR}
      cont2 : integer; {contador do segundo FOR}

  BEGIN
    FOR cont1:=1 TO n DO
      FOR cont2:=1 TO m DO mat[cont1,cont2] := 0
  END.

Simples, não? Apenas 2 FORs. Na verdade, você deve usar um FOR para cada dimensão do vetor. Como uma matriz é um vetor em 2 dimensões, usamos 2 FORs, se tivesse k dimensões, teríamos que usar k FORs.



BUSCA BINÁRIA

Suponha que temos um vetor ordenado, com n elementos, e queremos verificar se um dado elemento, x, está nesse vetor. Como faríamos?

A primeira idéia é comparar x a todo elemento do vetor. Mas isso é lento, pois temos que fazer n comparações, onde n é o número de elementos do vetor.

Podemos usar do fato do vetor estar ordenado para reduzir o tempo de busca. Considere o algoritmo: 

  1. Seja y0 o 1º elemento do vetor e y1 o último.
  2. Seja y o elemento do meio do vetor, ou seja, y = (y0 + y1) DIV 2.
  3. Comparo x com y e, se x > y, então x está na metade superior do vetor.
     Nesse caso faço y0 = y + 1 e volto a 2.
     Se y0 = y1, x não está no vetor.
  4. Se x < y, x está na metade inferior. Então faço y1 = y - 1 e volto a 2.
     Se y0 = y1, x não está no vetor.
  5. Se x = y, achei. y0 = y1, x não está no vetor.

Notou como é mais rápido? Não comparo com todos, apenas com alguns. Vejamos um exemplo: suponha que queremos saber seo 27 está no vetor abaixo:

1 2 3 4 5 6 7 8
1 5 8 9 12 15 27 30

vamos rodar o algoritmo:

1: y0 = 1 e y1 = 8

2: y = 4

3: como 27 > 4, ignoro a 1ª metade do vetor, fazendo y0 = 5. Ou seja, nosso vetor ficou:

5 6 7 8
12 15 27 30

2: y = 6

3: como 27 > 15, ignoro a 1ª metade do novo vetor, fazendo y0 = 7. Nosso vetor ficou:

7 8
27 30

2: y = 7

3: falhou, pois 27 não é > 27

4: falhou, pois 27 não é < 27

5: como 27 = 27, achei.

Agora vamos procurar o número 7:

1 2 3 4 5 6 7 8
1 5 8 9 12 15 27 30

1: y0 = 1 e y1 = 8

2: y = 4

3: falha, pois 7 não é > 9

4: Como 7 < 9, ignoro a 2ª metade do vetor, fazendo y1 = 3. Nosso vetor fica:

1 2 3
1 5 8

2: y = 2

3: como 7 > 5, ignoro a 1ª metade do vetor, fazendo y0 = 3. Nosso vetor fica:

3
8

2: y = 3

3: falha, pois 7 não é > 8.

4: 7 < 8, mas como y0 = y1, então 7 não está no vetor.

Agora, vamos estruturar mais nosso algoritmo: 

  Seja y0 o 1º elemento do vetor, V, e y1 o último.
  Seja y o elemento do meio do vetor, ou seja, y = (y0 + y1) DIV 2.

  enquanto x ≠ V[y] e y0 < y1
    se x > V[y] faço y0 = y + 1
    senão
      se x < V[y] faço y1 = y - 1
    faço y = (y0 + y1) DIV 2

  se x = V[y] achei
  senão não achei

Em Pascal isso fica: (Suponha que o vetor já foi carregado com os valores) 

  CONST MAX = 8;

  VAR v  : ARRAY[1..MAX] OF integer;
      y0 : integer;
      y1 : integer;
      y  : integer;
      x  : integer;

  BEGIN
    {carreguei o vetor...}

    {começo o algoritmo}
    y0 := 1;
    y1 := MAX;
    y := (y0 + y1) DIV 2;

    write('Entre o inteiro a ser buscado: ');
    readln(x);

    WHILE (x <> v[y]) AND (y0 < y1) DO
    BEGIN
      IF x > v[y] THEN {parte superior}
        y0 := y + 1
      ELSE
        IF x < v[y] THEN y1 := y - 1;
      y := (y1 + y0) DIV 2
    END;

    IF x = v[y] THEN writeln('encontrado na posição: ',y)
    ELSE writeln('elemento não encontrado no vetor)
  END.

O nome dessa busca é busca binária, pois, a cada passo, jogo fora metade do vetor em que estou trabalhando.




‹— Parte XXI — Página da disciplina — Parte XXIII —›