Design, Lógica

Tail-recursive algorithms

What is a tail recursive algorithm?

 

  If you’re a programmer for some time now, you probably know what a recursive function/method is. I mean, if you don’t, you probably shouldn’t be here in the first
place. This is NOT the place to be learning this kind of stuff… Just kidding. I shouldn’t be explaining this here but I will anyway. Firstly because I am one of those good guys, you know? Also because my mom taught me to be kind to people. But mainly because it’s straightforward: A recursive function is one that calls itself. Pretty much like a dog trying to bite his own tail. An algorithm to implement the Fibonacci sequence could be made recursive, for instance this one in Scala (and I’m gonna use this language in this post as I’m getting familiar with the language):


def fibonacci(x: Int): Int =
 if(x == 0 || x == 1) 1
 else fibonacci(x-1) + fibonacci(x-2)

  Alright! It’s a piece of cake in theory really. In practice? Well, not exactly. It can be very very frustrating, especially if you have a bigger function and you need
to debug it (Debug Hell). Cool. No, wait! But what about this tail-recursive thing? In traditional recursion, you perform your recursive calls first and only then you
use the returned values to calculate the result. For example, take the traditional implementation of the factorial function.


def fat(x: Int): Int =
  if(x <= 1) 1
  else x*fat(x-1)

It would be calculated like this:


fat(4) =
 4*(fat(3)) =
 4*(3*fat(2)) =
 4*(3*(2*fat(1))) =
 4*3*2*1 = 24

In tail-recursive style though, you perform the calculations first and then the recursive call is executed, passing the current result to the next recursive step.
Still using the factorial:


def loop(y: Int, x: Int):Int =
 {
    if(x <= 1) y;
    else {
      val sum: Int = y*x;
      loop(sum, x-1);
    }

}

def fat(n: Int) = loop(1,n)

In this case, we have an accumulator that already has the partial result and only passes it to the next recursion, if there is one:


fat(4) =
 loop(1,4) =
 loop(4,3) =
 loop(12,2) =
 loop(24, 1) =
 24


“Tail-recursive or not tail-recursive: that is the question!”


  Notice in this last example there is no calculation after the recursion. The recursive call is the last action in the function. Nothing else. That pretty much differentiates a tail-recursion algorithm. In a general way, if the last action of a function is to call a function (itself or another one), only one stack frame would be necessary for both. This type of call is known as a “tail call”. But what is a stack frame after all? And what difference does it make to reuse a stack frame?


“A Stack frame, a Stack frame. My kingdom for a Stack frame!”


To run your code, the Virtual Machine uses a special architecture to manage all the variables and methods in memory. For example, in the JVM memory is divided in 4 types: Heap (where instance variables, references and objects go), Stack(containing methods and the order of calls), code (contains the bytecode) and static (keeps static data and methods).

So stacks. Imagine a big stack in memory to keep the calls to your methods. Say you have a method prepare() that calls doSomething() and this last one calls doSomethingElse(). In the stack, they would be in that same order bottom-up (see picture 1). Of course, these methods have data like local variables and stuff, so where do they keep this data? On the method’s frame. The elements in the stack are called “frames”. These frames are simply blocks in memory that stores a method call and its data just like explained before.

Picture 1

Picture 1: In the picture you see the stack executing a method call. Notice that every new call is put on top of the last one, i.e the lower one is the first in Stack (top).



Back on the tail-recursive algorithms. Think about it: if one can reuse the stack frame for different calls, the execution uses constant stack space, which means the function is executed as a simple loop. Yes, there is an equivalence between a tail-recursive function and a loop. Which means you can convert a while loop, for example, into a tail-recursive function and vice-versa! It can be a big deal for the VM executing your code to reuse the current stack frame time and time again especially in deep recursions. You avoid the trap of falling into a stackoverflow error, which is basically a stack running out of stack frames. And clearly this allows for some optimization. However, if you find yourself in a situation where you have a clean non tail-recursive function (like fibonacci or factorial above) but there’s no risk to get a StackOverflow error because you’re not running deep recursion chains, so don’t lose your sleep on it. Clarity and good design are often more important aspects of an application than computational efficiency. Though, learning this feature of functional programming can help you if you need a different recursive strategy. Who knows?

Anúncios
Padrão
Lógica

Brincando com números primos

“Escolha um número primo maior que 3. Eleve-o ao quadrado e subtraia 1 dele. O resultado é divisível por 24! Mas, por que?”

Há alguns dias atrás, o Joshua Bloch, programador proeminente e mais conhecido pelo seu belo livro Effective Java, propôs esse problema de aritmética no twitter. Pelo visto, o Joshua Bloch gosta bastante de desafios matemáticos. Na verdade, todo bom programador que eu conheço ou mesmo apenas ouvi falar, tem uma quedinha pela ciência exata. Mas veja bem, isso não significa que para ser bom programador TEM que ser bom em matemática. Isso é apenas uma correlação, não implica causalidade.

Mas, vamos ao que interessa. Por que sempre que eu escolher um primo maior que 3, elevá-lo ao quadrado e subtrair por 1, o resultado sempre será divisível por 24? É bem simples entender porque, mas preste atenção.
Vamos por partes. Escolha um primo (digamos p) maior que 3. Logo temos p > 3.
Elevando ao quadrado e subtraindo 1, temos p²-1, certo?
O que exatamente é p² – 1? Nada mais que o produto de (p + 1) x (p – 1).
A partir daí é “sacada”. Vamos juntar os fatos:

1 – Você sabe que, qualquer que seja o número escolhido, ele faz parte da sequência: p – 1, p, p + 1. Você sabe também que a cada 3 números inteiros em sequência, um tem que ser divisível por 3. Como esse não é p (por definição), será ou p+1 ou p – 1.

2 – Também sabe que acima de 2, todos os primos são ímpares. Logo p + 1 e p – 1 são pares.

3 – Se p – 1 e p + 1 são pares, ao menos um deles tem de ser divisível por 4. Enquanto o outro será divisível por 2 (e não divisível por 4) e 3.

4 – Para um número ser divisível por 8, ele precisa ser divisível por 2 e 4. E para ser divisível por 24, tem de ser divisível por 3 e 8. Logo, temos que (p – 1)(p + 1) cumpre essa premissa perfeitamente. Daí, (p + 1) (p – 1) sempre será divisível por 24.

É uma prova simples e sem muita formalidade. Porém, elegante o bastante para ser apreciada por aqueles que curtem uma aritmética básica. Espero que tenham gostado!

Padrão
Design, Design Patterns, Lógica

Tua hierarquia não irá te salvar garoto – Strategy

Imagine que hoje seu chefe chegou inspirado e te deu a missão de desenvolver o protótipo de um jogo de esportes. Nesse jogo, existem vários jogadores de modalidades distintas. De forma que todos eles possuem capacidades físicas inerentes aos esportes que praticam. Tipo, um jogador de futebol consegue correr muito rápido e pular razoavelmente alto. Um jogador de vôlei, por outro lado, não corre tanto assim, mas pula muito alto. Você, como excelente desenvolvedor em Orientação a Objetos pensa: “Já matei! Mais um problema manjado de herança!”. Bom, não necessariamente está errado. Você provavelmente vai surgir com uma solução. Mas, é esta solução a melhor? É a mais flexível, mais fácil de testar e de melhor manutenção?

Vamos lá, a primeira coisa a se fazer se você quer criar uma hierarquia de tipos é criar uma classe ‘pai’. Para jogadores parece bem óbvio… hum… Jogador. Vamos assumir para fins didáticos que a classe Jogador tem apenas 2 métodos: correr() e pular(), ambos abstratos. Em seguida, bolamos as classes filhas, digamos: JogadorFutebol e JogadorHoquei. No caso, teríamos:

public abstract class Jogador {
     public abstract void correr();
     public abstract void pular();
}
public class JogadorFutebol extends Jogador {
   public void correr() {
       System.out.println("correr como jogador de futebol...");
   }
   public void pular() {
       System.out.println("Pular como jogador de futebol...");
   }
}

public class JogadorHoquei extends Jogador {
    public void correr() {
        System.out.println("Correr de patins...");
    }
public void pular() {
        System.out.println("Não pular...");
    }
}

Legal! Isso funciona! Então beleza, agora seu chefe chega e diz que seus clientes estão loucos ensandecidos para que o jogo dê suporte a tênis! Bom, agora você vai ter apenas que criar mais uma classe filha de Jogador, só que dessa vez o jogador corre muito e não pula (o cliente pediu isso especificamente =P). Daí, resolve criar a classe JogadorTenis, que… “peraí! Eu posso herdar o corre() do jogador de futebol e o pula do jogador de hóquei e vou economizar um monte de código!” Hehe, tá, mas existem alguns problemas aí. Muitas linguagens nem mesmo suportam herança múltipla! Outra, herança múltipla pode te trazer outros problemas seríssimos. “Ah, então eu escolho uma das duas pra herdar e o outro método eu copio. =]” Nossa! Eu não sei como eu penso nessas coisas… Mas é uma idéia terrível! Primeiro, você não deve herdar classes com o objetivo de economizar linhas de código! Isso escapa completamente o objetivo de OO. Você herda quando uma classe realmente têm um relacionamento “IS-A”. Ou seja,  quando ela for uma especialização da classe pai e esta for uma generalização das filhas. No caso, JogadorTenis não é um JogadorHoquei nem tampouco um JogadorFutebol. Esqueça economizar linhas de código.

Esse primeiro motivo deve bastar, mas eu ainda completo com o segundo. Você ainda assim estaria duplicando código de outras classes. Por exemplo, se você resolve criar uma classe JogadorTenis que ‘extends’ Jogador, e implementa o método correr() como escrito na classe JogadorFutebol e pular() como na classe JogadorHoquei você estaria duplicando código 2 vezes! E isso é ruim, muito ruim. Imagina se mais tarde é descoberto um erro no método da classe pai? “Copia e cola” seria o seu segundo nome… É… herança parece ser uma má idéia nesse caso aí. Outro problema: caso o jogador se machuque e não consiga mais, digamos, correr. Como fazer a instância de um jogador de futebol executar um correr() diferente dinamicamente? E agora? De fato, você ficaria sem saída. Você poderia fazer vários tipos de jogador de futebol representando os estados do seu JogadorFutebol, sendo que cada uma herdando a classe pai… não, essa não é uma solução elegante. A sua hierarquia iria aumentar, o que significa que a raiz do seu problema ia crescer e assim sucessivamente.  Imagina agora se surge um JogadorPoker. Mas enfim… a ideia está próxima! O que você acha de composição? Pense nos comportamentos que os jogadores podem ter relacionados com as suas ações. Por exemplo, correr como? Pular de que maneira? Correr rápido é uma forma de correr. Não correr poderia ser outra. Correr de patins seria outra… E pular? Pular alto como um jogador de vôlei seria uma forma. Pular baixo seria outra… já deu pra pegar a idéia. Então, podemos encapsular esses comportamentos visto que são eles que mudam (e não os jogadores como estávamos pensando no começo do problema!). Esses comportamentos serão uma hierarquia por si próprios. E a maldita da composição, onde entra na história? Os seus jogadores vão possuir(HAS-A) esses comportamentos. Mais explicitamente, no caso de correr:

public interface AcaoCorrer {
     public void correr();
}
public class CorrerComPatins implements AcaoCorrer {
     public void correr() {
         System.out.println("Correndo com patins...");
     }
}
public class CorrerRapido implements AcaoCorrer {
     public void correr() {
         System.out.println("Correndo rápido como um jogador de futebol...");
     }
}
public class NaoCorrer implements AcaoCorrer {   
     public void correr() {
         System.out.println("Não corre.");
     }
}

public abstract class Jogador {

     AcaoCorrer acaoCorrer;
     AcaoPular acaoPular;

     public Jogador() {
         this.acaoCorrer = new NaoCorrer();
         this.acaoPular = new NaoPular();
     }
     public void correr() {
         this.acaoCorrer.correr();
     }
     public void pular() {
         this.acaoPular.pular();
     }

     public abstract void exibir();
     public void setAcaoCorrer(AcaoCorrer acaoCorrer) {
         this.acaoCorrer = acaoCorrer;
     }
//Foi omitido, mas suponha que existe uma ampla variedade de formas de pular, sendo todas filhas de AcaoPular    
    public void setAcaoPular(AcaoPular acaoPular) {
         this.acaoPular = acaoPular;
    }
}


Funciona do mesmo jeitinho e com mais vantagens:

1 – Temos um design voltado a interfaces ao invés de classes. Favorece a flexibilidade. Quando fazemos um comportamento ser representado por uma interface, ao invés de ser implementado na classe Jogador ou em uma de suas subclasses, estamos de certa forma “liberando” esse comportamento pra fora da classe. O comportamento (ou a hierarquia de comportamentos) está fora da própria classe. Além disso, estamos nos referindo ao comportamento de forma generalista, no caso AcaoCorrer > CorrerComPatins por exemplo. E na implementação apenas mencionamos como atributo o tipo da interface AcaoCorrer e não as reais implementações.

2 – É menos complexo você compor uma classe com outra do que começar uma nova hierarquia. Você estará sujeito a menos erros bobos assim.  Ah sim! E hierarquias podem se tornar coisas do capeta depois de 3 níveis.

3 – Podemos mudar o comportamento dinamicamente ou “on the fly”. Com os métodos setter dos comportamentos, podemos mudar o tipo de comportamento que quisermos quando bem entendermos. Exemplo:


public class Jogo {

    public static void main(String[] args) {

//Um jogador de futebol corre muito e pula normalmente

        Jogador jogadorFutebol = new JogadorFutebol();

        jogadorFutebol.correr();

        jogadorFutebol.pular();

//Um jogador de hoquei corre de patins e não pula

         Jogador jogadorHoquei = new JogadorHoquei();

         jogadorHoquei.correr();

         jogadorHoquei.pular();

//Um jogador de hoquei machucado, não consegue correr nem pular

         jogadorHoquei.setAcaoCorrer(new NaoCorrer());

         jogadorHoquei.correr();

         jogadorHoquei.pular();

    }

}

Note que é possível setar os comportamentos de correr e pular porque o parâmetro esperado no método setter é uma generalização – uma interface. Qualquer classe que implemente a interface em questão (o que significa que esse comportamento saiba correr ou pular) poderá ser passada como novo comportamento do Jogador.  Caso surja um JogadorPoker, ele será composto por comportamentos já existentes, NaoCorrer e NaoPular. Logo, não haverá duplicação alguma de código.

Todos esses passos mostrados acima compõem o conhecido padrão de projeto Strategy. Esse padrão está catalogado como um dos 23 Design Patterns do “Gang of Four” ou “GoF”.  Da próxima vez que você se deparar com um problema que tenha essa natureza de encapsular vários algoritmos ou comportamentos num mesmo objeto, lembre-se do padrão Strategy, que pode “mudar as vísceras” de um objeto.  Calma! Não saia por aí dizendo que conheceu um jeito de modelar objetos que mudou a sua vida (principalmente se você descobriu isso aqui nesse blog, nesse caso pesquise mais um pouco =P ). Esta é uma solução para esse tipo de problema, NÃO PARA TODOS.  Por isso, use-a com equilíbrio.

Existem várias APIs famosas que usam Strategy, como JPA (que usa 3 algoritmos diferentes de mapear classes a tabelas do BD) e o componente JComponent (na escolha de Borders) do Swing.  Como eu falei, essa solução clássica resolve vários problemas, e se você for do tipo que se depara com muitos, Strategy vai ser algo comum na sua vida. Por isso, ao se deparar com um problema que parece ser facilmente resolvido estendendo classes e/ou criando uma nova hierarquia, pense se composição não seria uma melhor solução. Não apenas você ficará feliz com uma solução elegante e abrangente, mas os programadores que porventura pegarem esse código no futuro também ficarão. =]

Padrão
Experiências, Lógica

Quando a realidade esmaga a intuição

Suponha que você esteja num programa desses tipo porta dos desesperados. O apresentador lhe convida a participar do jogo que funciona da seguinte forma:

Existem 3 portas. As 3 estão fechadas de forma que você não consegue ver o que cada uma contém. Porém, uma delas esconde um carro como premiação e as outras duas um bode cada. A decisão de onde estará a porta com o carro é feita aleatoriamente. E depois de escolhida a porta, o prêmio é fixado a ela. Imagine que você (o participante) escolhe uma das 3 portas. Logo após você anunciar  sua escolha, o apresentador faz aquele suspense e abre uma das outras 2 portas, de forma que ele sempre deixa um bode sair. Agora você tem 2 portas: uma com o carro e uma com o bode. Agora o apresentador lhe faz a pergunta chave: “Você deseja trocar de porta ou continuar na mesma?” Qual seria a melhor decisão para você ganhar o carro? “Obviamente dá no mesmo. É  50% de chance de qualquer jeito…” Pois é. Fácil, né? NÃO! Por mais que a sua intuição clame desesperadamente para ser ouvida, a verdade é que, trocar de porta, nesse caso, dobra suas chances de vencer em relação a continuar com a primeira escolha. Mais especificamente, ao trocar de porta você tem 2/3 de chance de ganhar o carro.

 

The Monty Hall Problem


Esse problema,”The Monty Hall Problem”, ficou conhecido mundialmente após Marilyn Vos Savant publicá-lo em uma coluna sua numa revista de puzzles e matemática nos E.U.A. Os leitores da revista ao se depararem com o problema ficaram chocados com a resposta. E não eram pessoas do dia-a-dia ou alunos prevestibulandos, eram de fato Ph.Ds em matemática, doutores em estatísticas, cientistas renomados e etc. Estes enviaram cartas agressivas para a senhora Vos Savant em sua própria coluna, expondo o erro crasso que ela supostamente havia cometido. Eles argumentavam coisas do tipo

“Não vou nem mesmo perder muito tempo com a explicação do problema. Queira reconhecer seu erro e admitir que a resposta é 50% como nós dois bem sabemos…”

“Quer você mude sua resposta, quer não, a resposta é 50-50 de chance. Esse país já está cheio de ignorantes em matemática. Não precisamos do maior QI do mundo propagando isso. Que vergonha!”

Após algumas semanas de cartas e mais cartas, explicações e mais explicações, os matemáticos cederam e aceitaram a resposta de Vos Savant. “Quando a verdade se choca tão violentamente com a intuição” – disse ela – “as pessoas ficam chocadas.”

Paul Erdös (pronuncia-se ‘Erdish’), grande matemático húngaro, maior publicador de trabalhos na área, foi uma das pessoas que se chocaram com a resposta. E pior ainda: por não entender porque a resposta está certa. Aconselho esse livro, contando mais sobre essa e outras histórias.

 

O que danado isso tem a ver com programação ?


Bom, desafiei algumas pessoas no trabalho com esse problema a título de brincadeira. Como era de se esperar, todos responderam que a chance era 50-50 e protestaram veementemente quando eu falei que era muito melhor idéia trocar de porta. Experimente. As pessoas realmente enlouquecem com isso. É a intuição delas que está em jogo! Após muita discussão, foi feito um simulador em Java para provar que a chance era de 50%. Catch-22. O programa respondeu que era melhor trocar de porta, com aproximadamente 2/3 de chance de vencer ao fazer isso. Muito bem. A resposta passou a ser aceita, mas não se fazia ideia do porquê disso acontecer. Uns falaram em paradoxo, ainda outros em 2 respostas corretas, enfim. O programa que simulava o problema foi escrito de forma bem algorítmica, bem orientado a estatística mesmo e nada revelava sobre o insight da solução. Daí me veio a ideia de escrever um simulador com código orientado a objetos e bem fluente, de modo que o código se comunique conosco, dizendo o porquê de nossas chances aumentarem ao trocar de porta. Igual uma equação matemática ou um gráfico “falam” com a gente. Daí que surgiu a ideia do post. O ponto aqui não é recriminar as pessoas que não aceitaram a resposta do desafio, afinal de contas, eu também não aceitei de imediato.  Mas mostrar como a solução vem a tona facilmente se nos empenharmos em fazer um código que reflita o modelo de negócio de forma mais real possível. Isso se aplica ao Monty Hall Problem, ao jogo da velha que você fez no 1° período, ao sistema de GPS que você programou, ao sistema do seu banco e por aí vai.

Primeiramente, vamos entender porque a solução é realmente trocar de porta e depois vamos analisar como bom código, escrito com fluência, refletindo os requisitos do problema especificado, ajudam a entender a solução. Se você já leu até aqui, não pare agora 😉

 

Exagere sempre que puder


Sempre que você se deparar com um problema de lógica, uma boa abordagem é estressar o problema. Exagere. Tanto pra mais quanto pra menos, exagere! Claro, isso vai te ajudar a pensar não só no problema ali, mas em outras versões adaptadas do mesmo. Meio que estudando o problema olhando todos os seus lados assim como alguém estuda um cubo mágico antes de tentar completá-lo.

Vos  Savant fez isso ao dar a primeira dica da solução. Imagine que você tem, não 3 portas, mas 1.000.000 delas. Um carro e 999.999 bodes. Se o apresentador abrisse todas as portas exceto a 777.777, você trocaria bem rápido, não ? Esse primeiro argumento mata a questão. Porque se você diz que não trocaria, você está dizendo que a probabilidade de você estar certo na primeira vez que escolheu 1 entre 1 milhão de portas é a mesma que a probabilidade de você acertar agora com 1 entre 2 portas!  É danado né? Você ver o apresentador abrir 999.998 portas com bodes e ainda assim você achar que a sua porta tem um carro, e não a outra, a única que ele não abriu!

A segunda dica da solução é a mais simples, Marilyn Vos Savant desenhou todas as hipóteses possíveis e a conclusão vem rápido:

Possibilidades existentes

Se você não trocar de portas, você perde 2 em 3 vezes!

Analisando o problema com Orientação a Objetos


Como falei, o algoritmo feito inicialmente para o simulador era extremamente algorítimico: utilizando arrays, números pra representar portas, o main era o programa de auditório e por aí vai. É verdade que é bem mais rápido de se fazer se você quiser apenas provar que trocar é a melhor solução. Mas não dá pra ter insight nenhum da solução olhando pra um código não OO. Por isso, implementei um código bem simples em Java que possui uma representação mais realista. Temos assim, classe Porta, classe Participante e classe Show para retratar esse problema. Veja abaixo:

public class Show {

  private List<Porta> portas;

  private Participante participante;

  public Show(int quantidadePortas) {

    this.participante = new Participante();
 
    this.portas = new ArrayList<Porta>();

    for(int i = 0; i < quantidadePortas; i++) {
      this.portas.add(new Porta(i));
    }

    Porta premiada = sortearPorta();
    premiada.setPremiada(true);
  }

  public boolean simular(boolean trocar) {
    participante.escolherQualquerPorta(this.portas);
    abrirPortas();
    if(trocar) {
      participante.trocarPorta(this.portas);
    }
    return this.participante.getPorta().premiada();
  }

  public void setPortas(List<Porta> portas) {
    this.portas = portas;
  }

  private Porta sortearPorta() {

    int numPorta = sortearNumero(this.portas.size()-1);

    return this.portas.get(numPorta);
  }

  private void abrirPortas() {

    Porta escolhida = this.participante.getPorta();

    Porta portaRestante = null;

    this.portas.remove(escolhida);

    if(escolhida.premiada()) {
      portaRestante = sortearPorta();
    }
    else {
      for(Porta porta : this.portas) {
        if(porta.premiada()) {
          portaRestante = porta;
          break;
        }
      }
    }

    this.portas.clear();
    this.portas.add(escolhida);
    this.portas.add(portaRestante);
  }

  private int sortearNumero(int maximo) {
    return (int)Math.round(Math.random()*(maximo));
  }

  public List<Porta> getPortas() {
    return portas;
  }

  public static void main(String... args) {

    int acertos = 0;

    int rodadas = 100;

    int numPortas = 3;

    for(int i = 0; i < rodadas; i++) {

      Show show = new Show(numPortas);

      boolean resultado = show.simular(true);
      if(resultado) {
        acertos++;
      }
    }

    System.out.println("Taxa de acerto: " + 100*(((double)acertos/(double)rodadas)) + "%");
  }

}

class Participante {

  private Porta porta;

  public void escolherQualquerPorta(List<Porta> portas) {
    int numPorta = (int)Math.round(Math.random()*(portas.size()-1));
    this.porta = portas.get(numPorta);
  }

  //Troca pela primeira porta que não seja a dele
  public void trocarPorta(List<Porta> portas) {
    for(Porta temp : portas) {
      if(temp.getNumero() != this.porta.getNumero()) {
        this.porta = temp;
        break;
      }
    }
  }

  public Porta getPorta() {
    return porta;
  }

  public void setPorta(Porta porta) {
    this.porta = porta;
  }

}

class Porta {

  private int numero;

  private boolean premiada;

  public Porta(int numero) {
    this.numero = numero;
  }

  public int getNumero() {
    return numero;
  }

  public void setNumero(int numero) {
    this.numero = numero;
  }

  public boolean premiada() {
    return premiada;
  }

  public void setPremiada(boolean premiada) {
    this.premiada = premiada;
  }

}

Esse é o código pra simular o resultado do problema proposto.  Por default ele está trocando de porta. Se você quiser testar sem trocar de porta basta modificar o parâmetro do método ‘simular’ para false.  Mas o propósito disso tudo é analisar esse código. Um princípio muito importante de desenvolvimento de software é a chamada “Divisão de Responsabilidades”. Cada classe tem um propósito, e apenas um. O mesmo é válido para métodos.  As classes acima possuem essa característica.  Por exemplo,  a classe Participante reproduz as ações que o participante fará durante o jogo: escolherPortaAleatoriamente() e trocarPorta(). Participante não sorteia porta ou simula o jogo de alguma forma. Quem faz isso é a classe Show, que representa o jogo como um todo.  Dessa forma, o código fica mais fácil de entender. Logo, a chave para o problema ser do jeito que é também fica na cara. Por exemplo, no problema citado, uma parte do código que me dá um bom insight do porquê da solução é:

 


Porta escolhida = this.participante.getPorta();

Porta portaRestante = null;

if(escolhida.premiada()) {
  portaRestante = sortearPorta();
}
else {
  for(Porta porta : this.portas) {

    if(porta.premiada()) {
      portaRestante = porta;
      break;
    }
  }
}

Se você observar bem, verá que esse método revela a intenção do apresentador do programa, digamos, a mente dele ao manipular as portas. Note que existem 2 portas que são escolhidas pelo apresentador para NÃO serem abertas: ‘escolhida’ e ‘portaRestante’. Ou seja, a porta escolhida pelo participante inicialmente e mais uma porta restante. Sempre teremos 2 portas ao final: uma delas é a escolhida pelo participante e a outra… bem, aí que está a ‘mágica’. Observe como a outra porta é escolhida para permanecer fechada. O apresentador do programa não escolhe por acaso! Veja que o método ‘abrirPortas’ tem acesso a informações a coisas que supostamente não era pra ter. Mas são regras do jogo! Logo, ele sabe o que está por trás das portas. Vou repetir: A classe Show tem acesso a informações encapsuladas em todas as portas – se ela esconde um bode ou um carro. Participante só tem acesso a porta que ele escolheu. Agora observe a forma como o apresentador pensa pra decidir que portas ficarão fechadas. O if-else é como se estivesse perguntando a si mesmo: “A porta escolhida pelo participante  é a premiada? Se for, vamos escolher qualquer uma outra pra ficar fechada. Caso a porta que ele esteja agora tenha um bode, abra todas EXCETO a que tem o carro.” Então há ganho de informação na passagem da primeira escolha pra segunda! E o apresentador sabe de tudo isso pelo acesso que ele tem às portas. Na primeira escolha, o participante tem 1/3 de chance de acertar. Mas na segunda, o participante deve antecipar que o apresentador sempre vai abrir uma porta com um bode. O ganho de informação se concretiza quando o participante realiza que ele está de fato trocando a chance de apostar em uma porta pela chance de apostar em duas.  E no código isso fica explícito na forma do apresentador decidir que portas serão abertas.

Ganho de informação? É. Tipo, caso um E.T aterrise no programa logo após o momento que o apresentador abriu uma porta e saiu um bode, e ele veja que existem apenas 2 portas, onde em uma delas está o prêmio, com certeza as chances serão de 50%. Mas aí que tá: ele não teve o ganho de informação obtido no momento da abertura da porta!

Modifique o atributo ‘numPortas’ no método main para 10.000 e veja como as suas chances aumentam. Isso corresponde ao primeiro argumento de Vos Savant para trocar de portas. Repare que a cada porta existente nesse caso, o apresentador irá pensar de forma a só abrir as portas com bodes. Ganho de informação multiplicado… Se eu fosse você, trocaria fácil!

Agora é com você… pronto pra colocar o Sérgio Mallandro no bolso?

Padrão
Experiências, Lógica

Números “aleatórios” – Random

Você já se perguntou como o Math.random() gera um número aleatório ? Já? Bom, eu me perguntava bastante. Tanto que um dia resolvi revirar o que havia por trás dele. Isso já faz algum tempo, mas de qualquer forma, é algo interessante pra postar aqui.

Antes de mais nada não podemos descrever esses números como aleatórios ou randômicos porque é 100% previsível o número que o Math.random() vai gerar. Tá, tudo bem. Pra quem não se apega a detalhes e acha que isso é apenas semântica, vai em frente e chama isso de aleatório. Mas eles não são! São pseudoaleatórios. “Pseudo” porque são previsíveis como já falei. Como assim previsíveis? Veja. Em computação, existem os chamados “Pseudo Random number generators” ou geradores de números pseudo-aleatórios. Esses são baseados em uma equação que, recebendo como parâmetro um valor numérico, retorna uma série numérica. Os números que compõem essa série são normalmente bem diferentes uns dos outros (primos, ímpares, primos entre si, múltiplos de 7, próprio zero e assim por diante), o que podemos dizer que a equação gera números randômicos. O problema é que com o tempo, essa série começa a se repetir.

Mas… peraí! É previsível o número que o Math.random() vai gerar? Hã… sim! Ora, é baseado numa equação. E java.util.Random utiliza LCG  (Linear congruential generator):

 

Equação LCG

Equação LCG

Obviamente existem outras equações pra gerar essas sequências. Inclusive Von Neumann mesmo inventou uma (não muito boa por sinal).

Vamos ver na prática agora, como o Random gera a mesma sequência “aleatória” numa aplicação bem simples:

<code>

</p>

<pre>import java.util.Random;

public class GeradorAleatorio {

    private Random random;

    public GeradorAleatorio(long semente) {
         random = new Random(semente);
     }

     public int gerarInt() {
          return random.nextInt();
     }

     public long gerarLong() {
          return random.nextLong();
     }

     public double gerarDouble() {
          return random.nextDouble();
     }

     public static void main(String[] args) {
           GeradorAleatorio gerador =
           new GeradorAleatorio(10);
           long l = gerador.gerarLong();
           System.out.println(l);
      }
}

</code>

Pode rodar o código quantas vezes quiser. A sequência gerada sempre será “-4972683369271453960” seguido de “4755622236989466036“. Como o Random trata pra te entregar um valor double mais “bonitinho” é outra história.

Enfim, a questão é que a gente acabou de ver que esses números são sempre os mesmos pra o mesmo valor inicial passado (ou seed – semente). Daí surge a pergunta: “Como gerar números imprevisíveis?” Bom, existe uma técnica bem comum que é passar o System.currentTimeMillis() como seed ou valor inicial. Como esse valor corresponde ao número de milissegundos passados desde 1970 pra o tempo atual, esse valor irá variar numa amplitude maior ainda. Tornando-o estatisticamente imprevisível.

<code>
    GeradorAleatorio gerador =
    new GeradorAleatorio(System.currentTimeMillis());
    long l = gerador.gerarLong(); 
    System.out.println("O long aleatório foi: " + l);

</code>
Agora pode rodar o código quantas vezes quiser que o resultado será sempre diferente. Note que em teoria, o número sorteado ainda é previsível. Imagine que o mundo congelou no momento que a semente é passada para o construtor da classe Random e você pôde ver que número foi esse. Jogando ele na equação, você poderia prever com 100% de certeza que número seria sorteado. Mas enquanto o mundo não congelar tendenciosamente para alguns, o truque está seguro.

public class GeradorAleatorio {

 

private Random random;

 

public GeradorAleatorio(long semente) {

random = new Random(semente);

}

 

public int gerarInt() {

return random.nextInt();

}

 

public long gerarLong() {

return random.nextLong();

}

 

public double gerarDouble() {

return random.nextDouble();

}

 

public static void main(String[] args) {

GeradorAleatorio gerador = new GeradorAleatorio(System.currentTimeMillis());

long l = gerador.gerarLong();

System.out.println(l);

}

 

}

Padrão