Projeto de Algoritmos

Números aleatórios

Sequências de números aleatórios são úteis em muitas aplicações. São úteis, em particular, para testar programas. Números verdadeiramente aleatórios são muito difíceis de obter; por isso, devemos nos contentar com números pseudoaleatórios, gerados por algoritmos. Para simplificar a linguagem, omitiremos o "pseudo" no que segue.

A função rand

A função  rand  (abreviatura de random), definida na biblioteca stdlib, gera números aleatórios.  Cada invocação da função produz um número aleatório no intervalo fechado  0..RAND_MAX .  A constante RAND_MAX está definida no arquivo-interface stdlib.h.

Exercícios

  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;
        r = rand ();
        if (r < RAND_MAX / 6) return 1;
        else if (r < RAND_MAX * 2 / 6) return 2;
        else if (r < RAND_MAX * 3 / 6) return 3;
        else if (r < RAND_MAX * 4 / 6) return 4;
        else if (r < RAND_MAX * 5 / 6) return 5;
        else return 6;
    }
    
  2. [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

Eric Roberts escreveu uma pequena biblioteca (veja random) que torna mais amigável o uso da função rand.  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.
// O código foi copiado da biblioteca random 
// de Eric Roberts.

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

Como a função faz o serviço? Primeiro, 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+1. Finalmente, transforma k em um inteiro no intervalo low..high.

A qualidade dos números produzidos pela função não é boa se a diferença high − low for grande, especialmente se high − low for maior que RAND_MAX.

Exercícios

  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. Verifique que o número produzido pela função RandomInteger quando low = 0 e high = RAND_MAX é igual ao produzido por rand.

  3. Use a função RandomInteger para simular o rolar de um dado de 6 faces.

Sementes

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

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

O programador pode especificar a semente por meio da função srand, que tem um unsigned int como argumento e está na biblioteca stdlib.  (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 seja imprevisível.

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

 

 


URL of this site: www.ime.usp.br/~pf/algoritmos/
1998 | Last modified: Mon Jan 10 11:33:35 BRST 2011
Paulo Feofiloff
IME-USP

Valid HTML 4.01 Transitional    Valid CSS!