20

O motivo da questão é estudo/aprendizagem. Conhecer/aplicar técnicas e conceitos de programação, transformando algo "material" em "aplicação".


Recebi um vídeo no Whatsapp, onde bolinhas coloridas misturadas eram separadas por cores passando pelos pinos. Ou era muita tecnologia mecânica ou vídeo fake. No final, era um vídeo fake, onde uma design gráfico reproduziu um Tabuleiro de Galton para um trabalho de estudo.

Querendo saber mais, encontrei no Wikipedia, e gostaria de transformá-lo em um "programa".

Tabuleiro de Galton


O tabuleiro basicamente simula o "Teorema do limite central" (link): O teorema descreve a distribuição da média de uma amostra aleatória de uma população com variância finita.

Teorema


Ideia:

Começando pelo tabuleiro, resolvi criar uma matriz, onde tenho malhas e pinos, formando uma linha:

-------Malha------->
[P1][P2][P3][P4][P5]...

Valores dos pinos:

Como as chances na descida das bolas sempre é maior do centro para as laterais, criei os pinos com valores, sendo que, quanto maior, mais chances de "continuar" ali. Mas também, como os pinos são "intercalados" e não alinhados verticalmente, também considerei esse fato.

Criando as malhas:

// Definicoes
$qtdMalhas = 15;
$qtdPinos = 15;

// Auxiliares malhas/pinos
$am = $ap = 0;

// Criando as malhas e seus pinos
while ($am <= $qtdMalhas) {

    while ($ap < $qtdPinos) {

        if ($ap < ($qtdPinos/2)) {

            if ($am % 2 == 0) {
                $m[$am][$ap] = $ap;
            } else {
                $m[$am][$ap] = $ap+1;
            }
        } else {

            if ($am % 2 == 0) {
                $m[$am][$ap] = $qtdPinos-$ap-1;
            } else {
                $m[$am][$ap] = $qtdPinos-$ap;
            }
        }

        $ap++;      
    }

    $ap = 0;
    $am++;  
}

Estrutura da malha:

Considerando a matriz basicamente no seguinte formato:

$m[0][0]-$m[0][1]-$m[0][2]-$m[0][3]-$m[0][4]...
$m[1][0]-$m[1][1]-$m[1][2]-$m[1][3]-$m[1][4]...
$m[2][0]-$m[2][1]-$m[2][2]-$m[2][3]-$m[2][4]...
$m[3][0]-$m[3][1]-$m[3][2]-$m[3][3]-$m[3][4]...
$m[4][0]-$m[4][1]-$m[4][2]-$m[4][3]-$m[4][4]...
...

Imprimindo a malha:

// Zera auxiliares malhas/pinos
$am = $ap = 0; 

// Imprime a malha
while ($am < $qtdMalhas) {

    echo '<br>|';

    while ($ap < $qtdPinos) {

        echo $m[$am][$ap].'|';

        $ap++;
    }

    $ap = 0;
    $am++;
}

Resultado:

|0|1|2|3|4|5|6|7|6|5|4|3|2|1|0|
|1|2|3|4|5|6|7|8|7|6|5|4|3|2|1|
|0|1|2|3|4|5|6|7|6|5|4|3|2|1|0|
|1|2|3|4|5|6|7|8|7|6|5|4|3|2|1|
|0|1|2|3|4|5|6|7|6|5|4|3|2|1|0|
|1|2|3|4|5|6|7|8|7|6|5|4|3|2|1|
|0|1|2|3|4|5|6|7|6|5|4|3|2|1|0|
|1|2|3|4|5|6|7|8|7|6|5|4|3|2|1|
|0|1|2|3|4|5|6|7|6|5|4|3|2|1|0|
|1|2|3|4|5|6|7|8|7|6|5|4|3|2|1|
|0|1|2|3|4|5|6|7|6|5|4|3|2|1|0|
|1|2|3|4|5|6|7|8|7|6|5|4|3|2|1|
|0|1|2|3|4|5|6|7|6|5|4|3|2|1|0|
|1|2|3|4|5|6|7|8|7|6|5|4|3|2|1|
|0|1|2|3|4|5|6|7|6|5|4|3|2|1|0|

Poderia fazer a malha de outras formas ?

Sim, usando zero e um para os pinos mas acredito que teria mais trabalho ao sortear conforme a probabilidade de cada pino. Entre outras formas.


Com a malha pronta, como posso fazer para "passar as bolinhas entre ela" ?

A ideia seria fazer sorteio entre os valores dos pinos abaixo, considerando que as chances dela se manter sempre mais próxima ao pino de maior valor, ou seja, um sorteio com probabilidades diferentes, e assim obter o resultado como o "Tabuleiro de Galton".


Fiquem a vontade em postar a sua forma de fazer.

3
  • Sempre que uma bolinha bate em um prego/pino, a chance dela cair para a esquerda é de 50% e para a direita é de 50%. Isso mostra que a sua primeira figura tem um erro: é impossível que as bolas atinjam as duas lacunas na extrema esquerda ou as duas da extrema direita, seria necessário mais duas fileiras de pregos/pinos para isso. 16/04/2018 às 16:46
  • Assim sendo, se você tiver n fileiras de pinos, a sua abordagem ao problema fica muito mais simples se você simplesmente fizer n sorteios de números 0 ou 1. Melhor ainda, sorteie um número aleatório, faça um % (1 << n) e então conte quantos bits 1 tem no número produzido. 16/04/2018 às 16:46
  • Então... como eu até coloquei mais no final, eu poderia trabalhar com 0 e 1, tendo a probabilidade 50% e 50% como disse, com a ideia dela "ir" para a lateral mas podendo voltar para o centro. Dessa forma é só simplificar os loops que criam a matriz. Feito isso, eu faria um rand de 2 número, e caso o número for ímpar, vou para a esquerda da matriz, e caso for par, vou para a direita. Com isso, os valores dos arrays seriam o "número da coluna" que a bolinha irá cair. Essa é uma ideia com o 0 e 1. Seria + - isso que você pensou ?
    – rbz
    16/04/2018 às 16:57

1 Resposta 1

13
+50

Fiz com isso:

<?php
    function cai_bolinha($linhas) {
        $sorteio = mt_rand() % (1 << $linhas);
        return substr_count(decbin($sorteio), '1');
    }

    $linhas = 15;
    $bolinhas = 100000;

    $casas = [];
    for ($i = 0; $i <= $linhas; $i++) {
        $casas[$i] = 0;
    }

    for ($i = 0; $i < $bolinhas; $i++) {
        $casa_resultante = cai_bolinha($linhas);
        $casas[$casa_resultante]++;
    }

    for ($i = 0; $i <= $linhas; $i++) {
        echo $i . "->" . $casas[$i] . "\n";
    }
?>

Eis a saída (pode variar, obviamente):

0->5
1->35
2->310
3->1459
4->4079
5->9071
6->15089
7->19622
8->19771
9->15366
10->9265
11->4136
12->1409
13->334
14->46
15->3

Veja aqui funcionando no ideone.

O truque é que o mt_rand() vai gerar um número aleatório qualquer. Esse número, em binário é representado por zeros e uns, onde zero significa cair para a esquerda e um significa cair para a direita. O % (1 << $linhas) serve para que o resultado tenha a quantidade de bits que nos interessa, representado pela variável $linhas, que corresponde a quantidade de linhas de pinos que a bolinha tem que atravessar, que é a mesma quantidade de sorteios "esquerda ou direita", com 50% de probabilidade para cada lado.

Com isso, o número $sorteio corresponde a um número onde cada bit descreve para que lado a bolinha foi. Se esse número for zero (todos os bits são zero), então em todos os sorteios ela foi para a esquerda. Se todos os bits forem 1, então em todos os sorteios ele foi para a direita. Observe que esses dois casos são bastante raros e improváveis e as maiores probabilidades são que o número resultante seja composto de uma mistura de zeros e uns.

Depois disso, tendo esse $sorteio, ao contar quantos bits 1 existem nele, descobre-se em qual casa a bolinha caiu, onde a casa zero é a da extrema esquerda e a casa $linhas a da extrema direita.

No segundo laço for, realizo 100000 sorteios (a variável $bolinhas) com bolinhas caindo para observar a distribuição. Observe que a distribuição resultante é uma aproximação da distribuição normal (na verdade é uma distribuição binomial), e como esperado, as casas centrais (7 e 8) são que acumularam os maiores números de bolinhas, enquanto que as casas extremas (0 e 15) os menores números.

Sinta-se livre para experimentar outros valores para as variáveis $linhas e $bolinhas.

11
  • Perfeito! Eu não conhecia o mt_hand() e o operador <<. Depois vou dar uma olhada com mais calma ! Mas de início, o que entendi foi que você sorteou 0 ou 1, N vezes (que seria a qtd de colunas) para uma bolinha. Assim, você somou tudo, ou seja os 1, e isso dá o valor da coluna que ela caiu, correto ?
    – rbz
    16/04/2018 às 18:18
  • *Eu digo "colunas" no lugar da sua variável "linhas" pois pensando visualmente no tabuleiro, ficaria em pé. Assim facilita a associação ! rs
    – rbz
    16/04/2018 às 18:18
  • 1
    @RBZ Na verdade, eu poderia ter sorteado 0 ou 1, repetidamente por $linhas vezes. Mas ao invés disso eu simplesmente sorteei um número aleatório (é o que o mt_rand() faz) e forcei ele a ter o número desejado de bits ($linhas) ao descartar os demais bits com o %. Como um número é composto de zeros e uns, contando quantos são os bits 1, eu consigo saber quantas vezes a bolinha foi para a direita (subtraindo isso de $linhas seria quantas vezes foi para a esquerda). 16/04/2018 às 18:22
  • 1
    @RBZ O nome dessa variável é $linhas porque ela é o número de linhas de pregos/pinos que a bolinha tem que percorrer para descer. Para cada linha de pregos/pinos, a bolinha pode ou cair para a direita ou para a esquerda do pino. Logo, o número de linhas é o número de sorteios e também a quantidade de bits do número sorteado. E o número de casas onde a bolinha pode cair é igual ao número de linhas de pinos/pregos mais 1. 16/04/2018 às 18:23
  • 1
    @RBZ Se a cada passo você multiplica por 2, então ao realizar n passos, você vai multiplicar por 2 elevado a n. Assim sendo (a << b) vai resultar em a vezes 2 elevado a b. O (1 << $linhas) significa 1 multiplicado por [2 elevado 15], onde $linhas é 15. 16/04/2018 às 19:18

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .