quarta-feira, 25 de março de 2015

Percurso em árvore e problemas do URI (1191/1194)

Dado uma árvore binária (cada nó tem 0, 1 ou 2 filhos), existem duas formas prioritárias de percorrer os nós, que são em largura (BFS) ou em profundidade (DFS). (Não vamos falar disto aqui, mas são assuntos necessários para entender).

Na busca em profundidade, é possível estabelecer uma ordem de prioridade para as visitas:
  • Pré-ordem: Primeiro visita o próprio nó, depois a sub-árvore esquerda e em seguida a direita.
  • In-ordem: Primeiro visita a sub-árvore esquerda, depois o próprio nó e por último a direita.
  • Pós-ordem: Primeiro visita a sub-árvore esquerda, depois a direita e por último o próprio nó.
Por visitar, entenda uma operação qualquer (pode ser printar, inserir em uma pilha etc). Como exemplo, veja a imagem abaixo.

terça-feira, 24 de março de 2015

Herança múltipla e composição

Dependendo da classe que tentamos criar, pode ser que desejemos herdar informações de duas classes diferentes. Mas isso pode gerar um problema, conhecido como Diamond Problem, como no exemplo abaixo (animais são o exemplo mais fácil).

Sapo é um animal terrestre e aquático, que herdam de animal. Então há conflitos em relação à funções de Animal herdadas por sapo, uma vez que há duas descrições (mesmo que iguais) dos métodos.

Cada linguagem trata de forma diferente o problema. Em Java, não há herança múltipla, então o problema não ocorre. No entanto, é possível fazer algo parecido, utilizando composição.

Em Java, é possível definir interfaces, que podem se resumir em "classes somente com métodos não especificados (define-se nome, parâmetros e tipo retornado)". Delega-se a responsabilidade de descrever o método para as classes que implementarem a interface.

Basicamente, a interface diz que métodos devem ser implementados na interface e tem grandes vantagens. Funciona também de modo semelhante à classe abstrata, pois pode ser criado um vetor de elementos que implementam a interface (não faz sentido falar "herdam"), mas não pode ser instanciada.

Uma das desvantagens de usar herança em relação a composição é que herança aumenta o acoplamento das classes, ou seja, as subclasses são muito dependentes das classes superiores, e uma alteração nestas gera grande impacto naquela.

Para maiores informações sobre em qual situação se aplica cada, sugiro esta leitura.

Até mais!

segunda-feira, 23 de março de 2015

QuadTree

QuadTree é uma estrutura de dados utilizada para armazenar dados espaciais, e tem como grande vantagem a compressão de dados (que especificamente iremos explorar aqui). Parece um pouco com a árvore binária, mas ao invés de cada nó ter dois filhos, tem quatro, como o nome sugere, e, enquanto a árvore binária pode mapear uma reta, a QuadTree pode ser usada para mapear um espaço 2D.

Funciona assim: suponha que você tem uma imagem no formato .pnm, que nada mais é do que é uma matriz de lado N com bits 1 ou 0, digamos N = 8.


Se a matriz está totalmente preenchida com 1s, não vale a pena armazenar 8x8 = 64 valores, basta um. Mas se temos uma matriz da forma:

domingo, 22 de março de 2015

Conjuntos-Disjuntos (Disjoint-Set)

Uma estrutura de dados muito interessante e útil é a utilizada para identificar conjuntos disjuntos, ou seja, conjunto que não estão ligados, em um grafo. Por exemplo:

Grafo bidirecional
No grafo acima de N = 6 nós, os nós (1, 2 e 5) formam um conjunto conexo (a partir de um deles você consegue chegar nos outros), assim como (3, 4) e (6), totalizando 3 conjuntos conexos.

sexta-feira, 20 de março de 2015

Fala pessoal,

Pretendo atualizar o blog com alguns tópicos sobre competições de programação, problemas e possíveis soluções. Muito provavelmente não sei de muita coisa, mas vou escrever sobre o que conheço.

Para começar, se você é iniciante, sugiro fortemente que utilize o URI Online Judge, que é um site brasileiro de problemas com corretor online, então basta submeter seu código e esperar para saber se está certo ou não. A interface gráfica deste site é muito boa, e o fórum é ativo.

Outros sites famosos são o SPOJ br, UVa Online Judge, ACM-ICPC Live Archive e muitos outros (acho que esses já são suficientes).

Eu praticamente só uso os dois primeiros, mas vocês podem me encontrar lá:

Até breve!

terça-feira, 17 de março de 2015

Subclasses, herança e conceitos básicos

Algumas classes podem se estruturar hierarquicamente. Exemplo clássico:

Imagine que criamos a classe Shape (formas, em português), que define genericamente uma, com funções e atributos básicos comuns de todas as formas geométricas, como nome e área.

No entanto, para alguns objetos específicos, é interessante ter outros dados como diâmetro, no caso do círculo, tamanho do lado, no caso de um quadrado, ou hipotenusa, no caso de triângulos retângulos, mas que não fazem sentido serem definidos para os dois casos.

É possível definir então subclasses, que são classes que herdam atributos e funções de outras classes (chamadas de superclasses).
As subclasses herdam todos os atributos e métodos definidos na superclasse, mesmo que não definidos explicitamente na classe (por exemplo, se for omitido a declaração do método getNome na classe Triângulo, será utilizado o método definido na superclasse).

Pode ser ainda que não faça sentido instanciar um objeto Shape (queremos tratar formas específicas, e Shape é genérico). Nesse caso, declaramos Shape abstrata. Podemos declarar uma classe abstrata, mas não é possível instanciar (ou seja, podemos declarar um vetor de Shapes, mas o vetor será preenchido por Triângulos, Quadrados e Círculos, e não por Shapes puramente). Isso é uma vantagem grande quando queremos tratar os elementos que tem características diferentes como iguais (em um for, por exemplo, podemos percorrer um vetor de "coisas").

Aqui estão as classes (considere Triangle como triângulo retângulo equilatéro):
public class Shape {
    private String name;
    Shape(String n) { name = n; }
    public String getName() { return name; }
    public float calculateArea() { return 0.0f; }
   
    public static void main(String[] args) {
        Circle c = new Circle("Circle C", 3);
        Triangle s = new Triangle("Triangle S", 3);
        Shape shapeArray[] = {c, s};
        for(int i = 0; i < shapeArray.length; i++) {
            System.out.println("The area of " + shapeArray[i].getName()
                    + " is " + shapeArray[i].calculateArea() + " sq. cm.\n");
        }
    }
}

public class Circle extends Shape {
    private int radius;
    Circle(String n, int r) {
        super(n);
        radius = r;
    }
    public int getRaio() { return radius; }
   
    public float calculateArea() {
        float area;
        area = (float)(3.14*radius*radius);
        return area;
    }
}

public class Triangle extends Shape {
    private float hipotenusa;
    Triangle(String s, int h) {
        super(s);
        hipotenusa = h;
    }
    public float getHipotenusa() { return hipotenusa; }
   
    public float calculateArea() {
        float area;
        area = (float) (hipotenusa*hipotenusa/4.0);
        return area;
    }
}

Fizemos o método getRaio, getName e getHipotenusa porque não queremos que o usuário modifique os dados, mas apenas consiga lê-los (por isso nome, raio e hipotenusa são privados). Observe ainda que sobrescrevemos (overriding) alguns métodos. Isso faz com que um método da subclasse seja chamado ao invés do método da superclasse. Observe, no entanto, que é possível chamar o método equivalente da superclasse utilizando super() dentro da função.

Java permite ainda a sobrecarga de métodos (overload), em que criamos dois métodos com o mesmo nome, mas que difere no número de parâmetros (então a Java Virtual Machine saberá qual método você quer chamar).

domingo, 15 de março de 2015

Primeiro post: Introdução a Java e POO

Opa pessoal,

Esse post deve introduzir Java, especialmente para quem já sabe C, de maneira rápida. No github (https://github.com/leaomatheus/Calculator) está o código de uma calculadora (muito simples) que servirá como exemplo (desenvolvi apenas a interface gráfica).

Você vai precisar da JDK (necessário para desenvolver em Java) e de uma IDE (ambiente de desenvolvimento). Caso, não tenha, pode usar a que estou usando, JDK 8 com NetBeans (que você pode baixar aqui).

Java se estrutura em classes (é orientada a objetos), o que torna maior a independência entre as partes dos códigos. No caso deste programa, há duas classes: uma que trata diretamente da leitura do input do usuário e do output do programa, e outra que trata das operações matemáticas (da interpratação da leitura).

Com as classes, podemos processar o que é interessante na própria classe e disponibilizar o que for útil às outras classes, privando-as também de algumas informações. Por exemplo, para a classe que trata do input só interessa saber, dada determinada expressão, qual o valor retornado, e não como a outra classe armazena as informações.

O esqueleto básico da calculadora é:

public class CalculatorEngine {
    private int value; //Valor do display
    private int keep; //Valor mantido acumulado da operação anterior
    private char toDo; //Operação a ser feita

    //Armazena a operação a ser realizada
    private void binaryOperation(char op);
    
    //Operações básicas da calculadora
    public void add() { binaryOperation('+'); }
    public void subtract() { binaryOperation('-'); }
    public void multiply() { binaryOperation('*'); }
    public void divide() { binaryOperation('/'); }
    public void equal() { compute(); }
    
    //Computa as operações acumuladas
    private void compute();
    
    //Limpa os dados
    public void clear();
    
    //Atualiza o valor dos dígitos após nova inserção
    public void digit(int x);
    
    //Retorna o valor a ser exibido no display
    public int display();
    
    //Construtor
    public CalculatorEngine();
    
    //Função main apenas para teste
    public static void main(String arg[]) {
        CalculatorEngine c = new CalculatorEngine();
    }
}

Observe que algumas funções são public (públicas) e outras private (privadas), justamente: se alguém for utilizar a função para usar na calculadora, só interessa disponibilizar algumas funções e variáveis. No caso, basta ser capaz de

  • Consultar o display;
  • Carregar operações básicas;
  • Computar igualdades
  • Adicionar novos dígitos
  • Limpar os dados
Não importa como a classe trata e armazena os dados diretamente, por isso as demais funções são privadas.

Observe também que há uma função com o nome da classe: é o construtor, utilizado ao criar um novo objeto. Na main da classe, o construtor é usado para instanciar (criar, alocar espaço na memória) um objeto. O construtor pode receber ou não parâmetros, e pode realizar ou não alguma tarefa. No nosso caso, será usado para limpar as variáveis da classe.

Poderia ainda existir um destrutor (não feito nesse código), que seria usada ao destruir o objeto (desalocar o espaço na memória).

A interface gráfica também possui uma classe própria, que se utiliza de funções e objetos já prontos do NetBeans para criar botões e layouts. Em geral, cada botão tem um método da forma:

public class CalculatorUI {
    private void jButtonNumeroDoBotao() {
        //Método de update dos dados (add, subtract, multiply, divide, equal ou digit)
        //Update do display
    }
}

Cada classe pode ou não ter também uma função main. Quando o projeto é executado, uma classe é escolhida como Main e a função main daquela classe é equivalente ao método int main() de C, ou seja, é o método executado.

A classe CalculatorInput é, em teoria, equivalente à CalculatorUI, mas sem a interface gráfica (ao invés de apertar um botão e ter o resultado em tela, funciona apertando teclas e o resultado é no prompt de comando).

A imagem abaixo mostra uma visão da interface da calculadora:


Para quem já sabe C, espero que a introdução seja esclarecedora, e logo haverá mais posts.