Números pseudo-aleatórios

Por vezes necessitamos de simular acontecimentos aleatórios no computador:

Podemos fazer tudo isto usando geradores de números pseudo-aleatórios.

Pseudo-aleatórios em C

#include <stdlib.h>

int rand(void);

Exemplo

Gerar e imprimir uma amostra de pseudo-aleatórios.

#include <stdlib.h>
#include <stdio.h>

int main(void) {
   int i;
   printf("RAND_MAX=%d\n", RAND_MAX);
   for (i = 0; i<10; i++)
      printf("%d\n", rand());
   return 0;
} 

Execução

RAND_MAX=2147483647
804289383
846930886
1681692777
1714636915
1957747793
424238335
719885386
1649760492
596516649

Explicação

Gerar valores num intervalo


Exemplo:

Lançar uma moeda

Solução 1: Dividir o intervalo [0,RAND_MAX] a meio.

if (rand() < RAND_MAX/2) {
   cara ++; /* saiu cara */
} else {
   coroa ++; /* saiu coroa */
}

Solução 2: Usar o resto da divisão por 2.

if (rand()%2 == 0) {
   cara ++; /* saiu cara */
} else {
   coroa ++ /* saiu coroa */
}

Lançar uma moeda (2)

Simulando 1 milhão de lançamentos.

Generalizando

Para obter um valor entre 0 e \(N-1\) podemos usar o resto de divisão por \(N\):

rand() % N

Alternativas melhores

Solução 1: Converter o resultado de rand() num valor fracionário \([0,1[\) e multiplicar por \(N\):

(int)((double)rand() / ((double)RAND_MAX+1)*N)


Solução 2: Dividir o intervalo de 0 a RAND_MAX em aproximadamente \(N\) partes (sem usar virgula flutuante):

rand() / (RAND_MAX/N + 1)

Exemplos

Simular o lançamento de um dado; resultados entre 1 e 6.

d = 1 + rand() % 6;
    // OK mas tem pior distribuição

d = 1 + (int)((double)rand() /
              ((double)RAND_MAX+1)*6); 
    // Solução melhor (1)

d = 1 + rand()/(RAND_MAX/6 + 1);
    // Solução melhor (2)

Nota: para um jogo simples a primeira solução será suficiente!

Colecionar estatísticas

Lançar um dado várias vezes e calcular qual o valor médio: \[ \text{valor médio} = \frac{\sum\text{valores obtidos}}{\text{número de lançamentos}} \]

Valor médio

#include <stdio.h>
#include <stdlib.h>
#define N 1000000  // 1 milhão de lançamentos

int main(void) {
    double soma = 0.0;
    int i, d;

    for (i = 0; i<N; i++) {
       d = 1 + rand()%6;
       soma += (double)d;
    }
    printf("Valor médio: %.15f\n", soma/N);
}

Execução

$ gcc -o dado1 dado1.c
./dado1
valor médio= 3.498953000000000


Quando simulamos mais lançamentos o resultado aproxima-se de 3.5. Porque será?

Justificação

Justificação (cont.)

Com \(n\) lançamentos cada face sai aproximadamente \(\frac{n}{6}\) vezes; logo:

\[ \begin{aligned} s & \approx \frac{n}{6}\times 1 + \frac{n}{6}\times 2 + \frac{n}{6}\times 3 + \frac{n}{6}\times 4 + \frac{n}{6}\times 5 + \frac{n}{6}\times 6 \\ & = \frac{n}{6}\times (1+2+3+4+5+6) \\ & = \frac{n}{6}\times 21 = \frac{7n}{2} \end{aligned} \]

O valor médio será então: \(s/n = \left(\frac{7n}{2}\right)/n = \frac{7}{2} = 3.5\)

Exercício

Substituir a fórmula para gerar o valor do dado pelas com melhor distribuição

    d = 1 + (int)((double)rand() /
              ((double)RAND_MAX+1)*6); 
              
    d = 1 + rand()/(RAND_MAX/6 + 1);

Verificar o efeito sobre o valor médio calculado.

Repetibilidade

Exemplo

#include <stdio.h>
#include <stdlib.h>

int main(void) {
   srand(1);  // iniciar a semente
   for (int i = 0; i<5; i++)
      printf("%d\n", rand());
   printf("\n");

   srand(1);  // re-inicializar a semente
   for (int i = 0; i<5; i++)
      printf("%d\n", rand());
}

Execução

Repete a sequência de 5 pseudo-aleatórios:

1804289383
846930886
1681692777
1714636915
1957747793

1804289383
846930886
1681692777
1714636915
1957747793

Porquê repetibilidade?

Simular imprevisibilidade

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    int i;
    srand((unsigned)time(NULL));
      // time(NULL) retorna o
      // número de segundos desde 1 Jan 1970
    for (i = 0; i<5; i++)
       printf("%d\n", rand());
}

Estimar probabilidades

Estimar probabilidades

#define N 1000000 // 1 milhão de experiências

int dado(void);   // função auxiliar

int main(void) {
  int i, d1, d2, conta = 0;
  for(i = 0; i<N; i++) {
    d1 = dado(); 
    d2 = dado();
    if(d1+d2 == 7 || d1+d2 == 8)
      conta ++;
  }
  printf("Soma 7 ou 8: %.15f\n", 
         (double)conta/(double)N);
}

Função auxiliar

/* Simular o lançamento de um dado */
int dado(void) {
    return 1 + rand()%6;
}

Resultados

Soma 7 ou 8:  0.305117000000000