Números aleatórios

[coin-toss.jpg]

[dice.jpg]

Sequências de números aleatórios (ou seja, imprevisíveis) são úteis em muitas aplicações. São úteis, em particular, para gerar dados de teste de programas. Números verdadeiramente aleatórios são muito difíceis de obter (veja random.org); por isso, devemos nos contentar com números pseudo­aleatórios, gerados por algoritmos. Para simplificar a linguagem, omitiremos o pseudo no que segue.

A função rand

A função  rand  (o nome é uma abreviatura de random) da biblioteca stdlib gera números inteiros aleatórios.  Cada invocação da função produz um inteiro aleatório no intervalo fechado  0 .. RAND_MAX.  A macro RAND_MAX está definida na interface stdlib.h e é menor ou igual a INT_MAX.  (Para aplicações pouco exigentes, podemos supor que os números gerados por rand são mais ou menos uniformemente distribuídos no intervalo 0 .. RAND_MAX, ou seja, que cada número do intervalo tem mais ou menos a mesma probabilidade de ser gerado.)

Exercícios 1

  1. [Roberts]  O seguinte programa promete simular uma jogada de um dado de 6 faces. Qual o defeito do programa?
    int RolaDado (void) {
        int r = rand ();
        if (r < RAND_MAX/6) return 1;
        else if (r < 2 * RAND_MAX/6) return 2;
        else if (r < 3 * RAND_MAX/6) return 3;
        else if (r < 4 * RAND_MAX/6) return 4;
        else if (r < 5 * RAND_MAX/6) return 5;
        else return 6;
    }
    
  2. [Roberts]  O seguinte programa promete simular uma jogada de um dado de 6 faces. Qual o defeito do programa?
    int RolaDado (void) {
        int r = rand ();
        if (r < RAND_MAX/6) return 1;
        else if (r < RAND_MAX/6 * 2) return 2;
        else if (r < RAND_MAX/6 * 3) return 3;
        else if (r < RAND_MAX/6 * 4) return 4;
        else if (r < RAND_MAX/6 * 5) return 5;
        else return 6;
    }
    
  3. [Roberts] Sutil.  O seguinte programa promete simular uma jogada de uma moeda. Qual o defeito do programa?
    char *RolaMoeda (void) {
        int r;
        r = rand () % 2;
        if (r == 1) return "cara";
        else return "coroa";
    }
    

Inteiros aleatórios

Como obter um número inteiro aleatório num dado intervalo 0..N-1?  A primeira ideia é usar a expressão  rand() % N  (que dá o resto da divisão de rand() por N). Essa ideia seria razoável se rand produzisse números verdadeiramente aleatórios.  Como os números produzidos por rand são apenas pseudo­aleatórios, os últimos dígitos de cada número podem não ser aleatórios, e assim o resto da divisão por N pode não ser aleatório (poderia ser sempre ímpar, por exemplo).

[Dilbert cartoon]

Eric Roberts escreveu uma pequena biblioteca random que procura contornar a dificuldade apontada no parágrafo anterior e fornecer inteiros razoavelmente aleatórios no intervalo low..high.  Eis uma das funções da biblioteca:

// A função randomInteger devolve um inteiro 
// aleatório entre low e high inclusive,
// ou seja, no intervalo fechado low..high.
// Vamos supor que low <= high e que
// high - low <= RAND_MAX. (O código foi copiado
// da biblioteca random de Eric Roberts.)

int randomInteger (int low, int high)
{
    double d;
    d = (double) rand () / ((double) RAND_MAX + 1);
    int k = d * (high - low + 1);
    return low + k;
}

Primeiro, a função transforma o inteiro produzido por rand em um número real d no intervalo semi-aberto [0,1). Depois, transforma d em um número inteiro k no intervalo 0 .. high-low. Finalmente, transforma k em um inteiro no intervalo low..high.

Para aplicações pouco exigentes, podemos supor que os números produzidos por randomInteger são distribuídos mais ou menos uniformemente no intervalo low..high, especialmente se high − low for muito menor que RAND_MAX.

Exercícios 2

  1. No código de randomInteger, por que não escrever  (RAND_MAX+1)  no lugar de  ((double)RAND_MAX+1)?  Por que não escrever  RAND_MAX  no lugar de  ((double)RAND_MAX+1)?
  2. Analise o código para verificar que o inteiro produzido por randomInteger (0, RAND_MAX) é igual ao produzido por rand ().
  3. Prove que o número k que randomInteger devolve é tal que  lowkhigh.  Prove também que randomInteger devolve low quando rand gera 0.  Prove ainda que randomInteger devolve high quando rand gera RAND_MAX.
  4. Use a função randomInteger para simular o rolar de um dado de 6 faces.

Semente

A função rand tem uma memória interna que armazena o inteiro, digamos r, produzido pela execução anterior da função. A cada nova execução, a função usa r para calcular um novo inteiro aleatório.  (O inteiro calculado passa a ser o novo valor de r.)

Onde tudo isso começa?  O inteiro r que corresponde à primeira invocação de rand é conhecido como semente (= seed).  Dada a semente, a sequência de inteiros produzida por rand está completamente determinada.

O programador pode especificar a semente por meio da função srand da biblioteca stdlib, que recebe a semente (um unsigned int) como argumento.  Se o programador não especificar a semente, o sistema adota o valor 0.  A seguinte função da biblioteca de Roberts usa o relógo para especificar a semente:

#include <time.h>

// A função randomize inicializa o gerador
// de números aleatórios de modo que os
// resultados das invocações de randomInteger
// sejam imprevisíveis.

void randomize (void)
{
    srand (time (NULL));
}

Exercícios 3

  1. Escreva um programa que receba, pela linha de comando, dois inteiros positivos n e s e imprima os números produzidos por n invocações da função rand com semente s.
  2. Escreva um programa que receba, pela linha de comando, os inteiros positivos n, l, hs e imprima os números produzidos por n invocações da função randomInteger com argumentos lh e semente s.

Permutações aleatórias

Uma permutação de um vetor é qualquer rearranjo dos elementos do vetor; cada elemento do vetor muda de posição ou permanece onde está.

A seguinte função faz uma permutação aleatória de um vetor v[0..n-1].  Se os elementos do vetor forem distintos entre si, todas as n! permutações são igualmente prováveis.

// Faz uma permutação aleatória dos elementos
// do vetor v[0..n-1].

void permutacaoAleatoria (int v[], int n) {
  int r, k, t;
  for (k = n-1; k > 0; k--) {
     r = randomInteger (0, k); // 0 <= r <= k
     t = v[k], v[k] = v[r], v[r] = t;
  }
}

Veja a animação produzida por Mike Bostock. (Dica de Yoshiharu Kohayakawa.)

Exercícios 4

  1. Escreva um programa que receba, pela linha de comando, os inteiros positivos m e n e imprima m permutações aleatórias sucessivas do vetor v[0 .. n−1] definido por v[i] = i.
  2. Escreva um programa que receba, pela linha de comando, os inteiros positivos m, n, v0, … , vn−1 e imprima m permutações aleatórias sucessivas do vetor (v0, … , vn−1).