Departamento de Ciência da Computação - IME - USP

MAC0121 Algoritmos e Estruturas de Dados I

Mais ainda sobre este tópico pode ser lido na página Números aleatórios, escrita por Paulo Feofiloff, na página Linear Congruential Generator e Pseudorandom number generator da Wikipedia.

ALEATÓRIOS UMA OVA!

Geração de números aleatórios é um assunto amplamente estudado e que tem aplicações em várias áreas. Números aleatórios usados em computadores comuns não são verdadeiramente "aleatórios" sendo por isso chamados de números pseudo-aleatórios. Existem máquinas especialmente construídas para a geração de números aleatórios.

Existem vários algoritmos para geração de números pseudo-aleatórios em computadores. Os algoritmos são chamados de geradores de números aleatórios.

Um dos mais conhecidos geradores de números aleatórios é baseado no chamado método das congruências lineares. Dado um número inicial X₀, conhecido como semente, o próximo número da sequência é dado por

X₁ = (aX₀ + b) mod m.

Em geral, o número X_i+1 é obtido a partir do número X_i pela fórmula

X_i+1 = (aX_i + b) mod m,

onde a, b e m são números criteriosamente escolhidas. O operador mod indica resto da divisão. Os números assim gerados estão entre 0 e m-1.

Por exemplo, para a=7, b=1, m=13 e X₀=3, a sequência de números gerada é

9 12 7 11 0 1 8 5 10 6 4 3 9 . . .

Uma forma de usar esse gerador de números aleatórios para gerar números entre 1 e k, é usar a fórmula

Y_i = 1 + (X_i mod k).

Para a sequência do exemplo mostrado acima, os números gerados entre 1 e k=5 seriam

5 3 3 2 1 2 4 1 1 2 5 4 5 . . .

Um pouco mais sobre números aleatórios

Para os mais curiosos, segue uma pequena explicação bem simplificada sobre o fenômeno de "os números estão repetindo", que ocorre ao usarmos algum gerador de números aleatórios.

Um gerador de número aleatórios é uma função que devolve os números de uma sequência, um número a cada chamada da função. No caso deste exercício-programa, a sequência devolvida

X₀ X₁ X₂ X₃ X₄ . . .

é obtida através do método das congruências lineares através da expressão

X_i+1 = (aX_i + b) mod m,

onde a, b e m são constantes inteiras.

Considere, para simplificar muito as coisas, um gerador de números aleatórios que devolve números inteiros entre 0 e 6. Suponha que a sequência devolvida por esse tal gerador é

1 6 0 5 3 3 4 2 1 2 1 6 0 5 3 3 4 2 1 2 1 6 . . .

Com isto queremos dizer que o primeiro valor obtido pelo gerador é o número 1, o segundo valor obtido é o número 6, e assim por diante. Reparem que a sequência começa a se repetir a partir de um certo ponto; notem o


1 6 . . . 1 6 . . .

Há quem chame esse tipo de sequência de cíclica. A posição na sequência a partir da qual o gerador começa a devolver os números é determinada por um valor, a chamada semente do gerador, que pode ou não ser fornecida ao gerador para que ele faça o seu serviço. Por exemplo, digamos que seja fornecido ao nosso gerador imaginário o número 1234 como semente, a partir daí ele pode, digamos, devolver os números abaixo, na ordem em que aparecem,

3 3 4 2 1 2 1 6 0 5 3 3 4 2 1 2 1 6 0 5 3 3 . . .

Já, se fornecermos a semente 4321, o gerador talvez passe a devolver os números

4 2 1 2 1 6 0 5 3 3 4 2 1 2 1 6  1 6 0 5 3 3 4 2

Resumindo, a semente só determina o ponto exato do início da sequência cíclica a partir do qual os números são devolvidos pelo gerador.

De volta ao EP1, a variável semente armazena o valor usado como semente do gerador. Se vocês mudarem esse número, a sequência dos números a serem adivinhados também muda. Por isto que cada vez que o programa é executado com a mesma semente a sequência de números gerada é precisamente a mesma.

Exemplos de execuções de um gerador

Considere os seguintes exemplos de possíveis execuções de seu programa para gerar números pseudo-aleatórios usando o método da congruência linear.

Esse gerador de números aleatórios usa os valores de a=1277, b=1, m=131072. Isto, em particular, significa que o gerador produzirá números inteiros entre 0 e 131071.

A entrada do programa são 5 números inteiros, semente, n₁, k₁, n₂ e k₂. O programa gerar n₁ números pseudo-aleatórios com valores entre 1 e k₁ e n₂ números pseudo-aleatórios com valores entre 1 e k₂.

Os números em vermelho foram digitados por usuário hipotético.

Exemplo 1

Digite o valor da semente: 123
Digite os valores de n1, k1, n2 e k2: 4 10 8 9
 4 numeros gerados entre 1 e 10:  1  6  3  4
 8 numeros gerados entre 1 e  9:  3  6  9  3  2  1  2  3

Exemplo 2

Digite o valor da semente: 999
Digite os valores de n1, k1, n2 e k2: 1 1 1 1
 1 numeros gerados entre 1 e  1:  1
 1 numeros gerados entre 1 e  1:  1

Exemplo 3

Digite o valor da semente: 6
Digite os valores de n1, k1, n2 e k2: 10 4 10 13
10 numeros gerados entre 1 e  4:  4  1  2  3  4  1  2  3  4  1
10 numeros gerados entre 1 e 13:  8  4 12  5  2  8 10  7 12  6

Exemplo 4

Digite o valor da semente: 12
Digite os valores de n1, k1, n2 e k2: 1 6 52 13
 1 numeros gerados entre 1 e  6:  2
52 numeros gerados entre 1 e 13: 12 10  4  8  9 10  6  3  5 11
                                 13  4 13  9 13  3  9 10 12 12
                                 10  8  4  9  3  8 11 11  5  8
                                  1 13  7  6 13  5 11  4 13 13
                                  1 12  1  5  2  4 11  7 10  1
                                 10  3