Departamento de Ciência da
Computação - IME - USP
Para fazer o EP1 você não precisa ler este texto. Você deve simplesmente usar a "receita" dada no EP. A leitura do texto a seguir é destinada aos alunos que estiverem mais curiosos sobre o assunto. Mais ainda sobre este tópico pode ser lido na página Números aleatórios, escrita por Paulo Feofiloff.
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
X0, conhecido como semente,
o próximo número da seqüência é dado por
X1 = (aX0 +b) mod m.
Em geral, o número Xi+1 é obtido a partir
do número Xi pela fórmula
Xi+1 = (aXi +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
X0 = 3, a seqüê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
Yi = 1 + (Xi mod k).
Para a seqüê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 . . .
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 seqüência devolvida
X0 X1 X2 X3 X4 . . .
é obtida através do método das congruências lineares através da expressão
Xi+1 = (aXi +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 seqüê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 seqüência começa a se repetir a partir de um certo ponto; notem o
1 6 . . . 1 6 . . .Há quem chame esse tipo de seqüência de cíclica. A posição na seqüê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 seqüê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 seqüencia dos números a serem adivinhados também muda. Por isto que cada vez que o programa é executado com a mesma semente a seqüência de números gerada é precisamente a mesma.
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, n1, k1, n2 e k2. O programa gerar n1 números pseudo-aleatórios com valores entre 1 e k1 e n2 números pseudo-aleatórios com valores entre 1 e k2.
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