06 - Algoritmos com dados compostos

Até o momento todos nosso algoritmos usavam dados "simples": cada variável guarda somente um valor. Agora vamos desenvolver algoritmos com dados compostos: cada variável guarda uma coleção de valores. Os tipos compostos mais básicos são o Array e Strings.

04 - Arrays

Quando representamos algoritmos o tipo mais básico de dados compostos que temos é o Array, que representa uma coleção de objetos do mesmo tipo contínua indexada por um número inteiro começando em 0. Tem tamanho fixo. As seguintes operações estão disponíveis em um Array.

• NOVO_ARRAY(N) - cria array com capacidade N>0
• TAMANHO(A)- devolve o número de elementos do array
• A[i] - devolve o elemento de índice i. Se i<0 ou i>TAMANHO(A) dá erro

Vejamos então como escrever essas operações com Pseudo-código e com Java:

# Cria array com 10 int
ARR := NOVO_ARRAY(10)

# Acessa elementos do array
ARR[0] := 5
ARR[1] := ARR[0] + 2;

# tamanho do array. Nunca muda
N := TAMANHO(ARR) # 10

// Cria array com 10 int
var arr = new int[10];

// Acessa elementos do array
arr[0] = 5;
arr[1] = arr[0] + 2;

// tamanho do array. Nunca muda
var n = arr.length; // 10

A operação mais comum com um array é percorrer o array, passando por todos os elementos. Podemos fazer isso de duas maneiras:

1. Percorrer usando índice:

   Pseudo códigoJava

   PARA CADA I=0 ATÉ TAMANHO(ARR) FAÇA
       # FAZ ALGO COM ARR[I] AQUI
   FIM
   

   for (int i = 0; i < arr.length; i++) {
       // faz algo com arr[i] aqui
   }
   

   • acesso via índice do elemento atual (variável i)
   • especialmente útil para acessar elementos vizinhos (via i+1 ou i-1)

2. Percorrer elemento a elemento:

   Pseudo códigoJava

   PARA CADA ITEM EM ARR FAÇA
       # FAZ ALGO COM ITEM AQUI
   FIM
   

   for (var item : arr) {
       // faz algo com item aqui
   }
   

   • só acessa o elemento atual
   • mais legível

Vamos agora usar esses novos conceitos em exercícios de Arrays.

Entregador mais próximo

Para desenvolver um aplicativo de entrega de comida, é útil saber qual entregador está mais próximo do restaurante. Faça uma função que recebe as coordenadas x, y de um restaurante, uma lista de coordenadas x e uma lista de coordenadas y de entregadores. Sua função deve devolver o índice do entregador mais próximo do restaurante.

Observação 1: a distância de um ponto $(x_1, y_1)$ a outro ponto $(x_2, y_2)$ é dada por $\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$.

ENTREGADOR_MAIS_PROXIMO(X, Y, XE, YE)
    MAIS_PROXIMO := 0
    DIST_MAIS_PROXIMO := DIST(X, Y, XE[0], YE[0])

    PARA CADA I=1 ATÉ N FAÇA
        DIST := DIST(X, Y, XE[i], YE[i])
        SE DIST < DIST_MAIS_PROXIMO ENTÃO
            DIST_MAIS_PROXIMO := DIST
            MAIS_PROXIMO := I
        FIM 
    FIM

    DEVOLVE MAIS_PROXIMO

Diferença de listas

Faça uma função que recebe 2 listas de inteiros e retorna uma nova lista com os elementos da primeira lista que não estão na segunda lista.

DIFF_LISTAS(A1, A2)
    COUNT_DIFF := 0

    PARA CADA I=0 ATÉ TAMANHO(A1) FAÇA
        ESTA_EM_A2 = Falso
        PARA CADA J=0 ATÉ TAMANHO(A2) FAÇA
            SE A1[I] = A2[J] ENTÃO
                ESTA_EM_A2 = Verdadeiro
            FIM
        FIM
        SE NÃO ESTA_EM_A2 ENTÃO
            COUNT_DIFF := COUNT_DIFF + 1
        FIM
    FIM

    ARR_DIFF = NOVO_ARRAY(COUNT_DIFF)
    COUNT := 0

    PARA CADA I=0 ATÉ TAMANHO(A1) FAÇA
        ESTA_EM_A2 = Falso
        PARA CADA J=0 ATÉ TAMANHO(A2) FAÇA
            SE A1[I] = A2[J] ENTÃO
                ESTA_EM_A2 = Verdadeiro
            FIM
        FIM
        SE NÃO ESTA_EM_A2 ENTÃO
            ARR_DIFF[COUNT] = A1[I]
            COUNT := COUNT + 1
        FIM
    FIM


    DEVOLVE ARR_DIFF

Valor da nota fiscal

Faça uma função que recebe duas listas com informações de uma nota fiscal e devolve o preço total da nota. A nota fiscal é representada pelas duas listas, uma com preços de produtos e outra com a respectiva quantidade de itens comprados daquele produto. Você pode assumir que só é possível comprar quantidades inteiras de um produto.

VALOR_DA_NOTA(P, Q)
    VALOR_TOTAL := 0

    PARA CADA I=0 ATÉ TAMANHO(P) FAÇA
        VALOR_TOTAL := VALOR_TOTAL + P[I] * Q[I]
    FIM

    DEVOLVE VALOR_TOTAL

05 - Strings

Strings em Java possuem recursos muito parecidos com o que já conhecemos de Python. Veja alguns exemplos introdutórios abaixo.

S := "Bla bla bla"

# mostra no terminal
PRINT("Valor de s:" + S)

# cópia de trechos da string
bla1 := SUBSTRING(S, 0, 3) # Bla
bla3 := SUBSTRING(S, 8) # Vai até o fim se não passar o segundo

LOWER := LOWERCASE(S)

# checa se a string é vazia
v := EH_VAZIO(S)

# checa se a string é só de espaços em branco
v := SO_ESPACOS(S)

# checa se duas strings são iguais
igual := S = bla1

String s = "Bla bla bla";

// mostra no terminal
System.out.println("Valor de s: " + s);

// cópia de um trecho da String
String bla1 = s.substring(0, 3); // Bla
String bla3 = s.substring(8); // bla - vai até o fim da String se não passar o segundo

String lower = s.toLowerCase(); // bla bla bla

// checa se é string vazia
s.isEmpty();

// checa se a string é só de espaços em branco
s.isBlank();

// checa se duas strings são iguais
boolean igual = s.equals(bla1);

Em Pseudo código vamos tratar String sempre como um array, porém na implementação em Java existem algumas diferenças importantes.

String vs Char

Em Java a String é uma sequência de char, um objeto que representa um único caractere. Quando queremos representar um único caractere usando aspas simples (por exemplo, 'a'). Quando queremos uma sequência de char sempre usamos aspas duplas (por exemplo, "texto")

char c = 'a'; // só um caractere

// substitui toda ocorrência da letra 'a' por 'e'
String ble = s.replace('a', 'e');  // Ble ble ble

Algumas operações corriqueiras com strings são:

1. Percorrer caracteres usando índice:

   Pseudo códigoJava

   PARA CADA I=0 ATÉ TAMANHO(S) FAÇA
       # FAZ ALGO COM S[I] AQUI
   FIM
   

   for (int i = 0; i < s.length(); i++) {
       char c = s.charAt(i);
       // faz algo com c aqui
   }
   

   • pode acessar vizinhos
   • tem índice e caractere ao mesmo tempo

2. Processar por linhas:

   Pseudo códigoJava

   PARA CADA LINE EM DIVIDE(S, "\n") FAÇA
       # FAZ ALGO COM LINE AQUI
   FIM
   

   for (String line : s.split("\n")) {
       // usa line aqui
   }
   

3. Separar por espaços em branco:

   Pseudo códigoJava

   PARA CADA ITEM EM DIVIDE(S, "\s") FAÇA
       # FAZ ALGO COM ITEM AQUI
   FIM
   

   for (String word : s.split("\\s")) {
       // usa word aqui
   }
   

A operação DIVIDE(S, P) divide uma string pelo padrão P, retornando um ARRAY de String com as partes de S. Padrões comuns são "\n" (linhas) e "\s" (espaços).

Java tem uma extensa documentação online. Todos os métodos de String podem ser vistos neste link.

Vamos agora praticar com alguns exercícios.

Palavras iguais

De acordo com o Novo Acordo Ortográfico da Língua Portuguesa, usa-se o hífen em compostos que têm palavras iguais ou quase iguais, sem elementos de ligação. Faça uma função que recebe uma string e devolve true se ela for composta por duas palavras iguais ou false, caso contrário.

Por exemplo, sua função deve devolver true para as seguintes entradas: "pega-pega", "cri-cri", "zum-zum.

Alguns exemplos para os quais sua função deve devolver false são: "zigue-zague", "pingue-ongue", "abobrinha".

PALAVRAS_IGUAIS(S)
    PARTES := DIVIDE(S, "-")

    SE TAMANHO(PARTES) != 2 ENTÃO
        DEVOLVA FALSO
    FIM

    DEVOLVE PARTES[0] = PARTES[1]

Lista celulares

O departamento de marketing da sua empresa está interessado em obter apenas os números de telefone celular, separando-os dos telefones fixos. Para simplificar esta operação serão considerados números de celular apenas aqueles que, após o código de área, iniciarem com o dígito adicional 9.

Você recebeu a tarefa de obter uma lista com os números de celular, sem o código de área. Entretanto, o cadastro de telefones do departamento de marketing não está padronizado e existem números seguindo 3 formatos distintos:

1. Números completos (13 ou 14 caracteres), incluindo o código do país (+55) e o código de área (ex: 11);
2. Número contendo apenas o código de área (10 ou 11 caracteres);
3. Número sem código de área (8 ou 9 caracteres).

Faça uma função que recebe uma lista de números de telefone e retorna uma lista contendo apenas os telefones celulares. Cada telefone da lista de entrada (recebida como argumento da sua função) pode estar em qualquer um dos 3 formatos acima. Os telefones da lista de saída (retornada pela sua função) devem conter apenas os dígitos do telefone, removendo o código do país e código de área se for necessário.

CELULARES(T)
    COUNT_CELULARES := 0

    PARA CADA ITEM EM T FAÇA
        DIGITO1 := VAZIO
        SE TAMANHO(ITEM) = 14 ENTÃO
            DIGITO1 := ITEM[5]
            SE DIGITO1 = "9" ENTÃO
                COUNT_CELULARES := COUNT_CELULARES + 1
            FIM
        FIM
        SE TAMANHO(ITEM) = 11 ENTÃO
            DIGITO1 := ITEM[2]
            SE DIGITO1 = "9" ENTÃO
                COUNT_CELULARES := COUNT_CELULARES + 1
            FIM
        FIM

        SE TAMANHO(ITEM) = 9 ENTÃO
            DIGITO1 := ITEM[0]
            SE DIGITO1 = "9" ENTÃO
                COUNT_CELULARES := COUNT_CELULARES + 1
            FIM
        FIM
    FIM

    LISTA_CELULAR := NOVO_ARRAY(COUNT_CELULARES)
    NUM_CELULARES := 0
    PARA CADA ITEM EM T FAÇA
        DIGITO1 := VAZIO
        SE TAMANHO(ITEM) = 14 ENTÃO
            DIGITO1 := ITEM[5]
            SE DIGITO1 = "9" ENTÃO
                LISTA_CELULAR[NUM_CELULARES] := SUBSTRING(ITEM, 5)
                NUM_CELULARES := NUM_CELULARES + 1
            FIM
        FIM
        SE TAMANHO(ITEM) = 11 ENTÃO
            DIGITO1 := ITEM[2]
            SE DIGITO1 = "9" ENTÃO
                LISTA_CELULAR[NUM_CELULARES] := SUBSTRING(ITEM, 2)
                NUM_CELULARES := NUM_CELULARES + 1
            FIM
        FIM

        SE TAMANHO(ITEM) = 9 ENTÃO
            DIGITO1 := ITEM[0]
            SE DIGITO1 = "9" ENTÃO
                LISTA_CELULAR[NUM_CELULARES] := ITEM
                NUM_CELULARES := NUM_CELULARES + 1
            FIM
        FIM
    FIM

    DEVOLVE LISTA_CELULAR

Extras

Diferença de listas (II)

Nosso algoritmo ficou um bocado grande. Vamos tentar deixá-lo mais fácil de ler.

Valor da nota fiscal (II)

O programa atual só aceita quantidades inteiras de produtos.

Lista celulares (II)

Nosso algoritmo ficou grande e repetitivo.