![[coin-toss.jpg]](img/coin-toss.jpg "Copiado de https://blog.gaiam.com/the-flip-side-confronting-the-negative-to-find-the-positive/")
![[dice.jpg]](img/dice.jpg "Copiado de www.dispatch.com/content/stories/life_and_entertainment/2010/09/18/jersey-shore-of-yore.html")
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
pseudoaleatórios,
gerados por algoritmos.
Para simplificar a linguagem, omitiremos o pseudo
no que segue.
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.
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;
}
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;
}
char *RolaMoeda (void) {
int r;
r = rand () % 2;
if (r == 1) return "cara";
else return "coroa";
}
Como obter um número inteiro aleatório num dado intervalo 0..N-1 para N ≤ RAND_MAX? 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. os últimos dígitos de um números produzidos por rand podem não ser aleatórios (eles poderiam ser ser todos ímpares, por exemplo).
![[Dilbert cartoon]](img/dt011025.gif "Copiado de dilbert.com/strip/2001-10-25")
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.
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.
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 o valor desejado da 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ógio do sistema 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));
}
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.)