|
Por vezes necessitamos de simular acontecimentos aleatórios no
computador, por exemplo, para baralhar
cartas.
Em 1946, John von Neumann propôs o middle-square method
para gerar sequências de números
pseudo-aleatórios no intervalo [0,1[.
Parte-se de uma semente, que é um número inteiro positivo com dígitos.
Calcula-se o quadrado desse número;
se tiver menos de dígitos,
acrescentam-se zeros à esquerda.
Os dígitos centrais definem o
pseudo-aleatório resultante e a próxima semente.
Por exemplo, partindo de 1111, calculamos o seu quadrado, que é
1234321, e acrescentamos um zero para ter um número com
dígitos. Fica e o pseudo-aleatório é 0,2343.
Depois, partindo de 2343, calculamos o seu quadrado, que é
5489649, e temos de acrescentar um zero.
Fica e obtém-se 0,4896.
Os pseudo-aleatórios seguintes seriam
0,9708 e 0,2452, como se ilustra abaixo.
Como o maior inteiro de dígitos é , o seu quadrado é
inferior a e, por isso, dígitos bastam para o representar,
sendo, por vezes, todos necessários.
Todas as sequências acabam por ter repetições,
algumas muito rapidamente, como
as que começam com 1001, 0020 ou 9800.
)
Escreva um programa que, dados , e uma semente com dígitos,
imprima a sequência dos primeiros pseudo-aleatórios com
dígitos gerados por este método, partindo de .
A primeira linha tem dois inteiros positivos e , separados por
um espaço.
O primeiro é o número de pseudo-aleatórios a gerar.
Segue-se uma linha com inteiros (cada um entre 0 e 9),
separados por um espaço, que
são os dígitos da semente inicial , lidos
da esquerda para a direita.
| |
|
Número de pseudo-aleatórios pedidos
|
| |
|
Número de dígitos na semente |
O output tem linhas, uma por cada pseudo-aleatório gerado.
Apresenta-os pela ordem em que foram calculados,
sem espaços entre os dígitos e sempre com o prefixo "0," (sem aspas).
6 2
1 1 1 1
0,2343
0,4896
0,9708
0,2452
0,0123
0,0151
4 2
0 0 2 0
0,0004
0,0000
0,0000
0,0000
5 1
5 2
0,70
0,90
0,10
0,10
0,10
7 2
9 8 0 0
0,0400
0,1600
0,5600
0,3600
0,9600
0,1600
0,5600
3 18
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 7 6 8 7 6
0,999999999999753752000000000000000000
0,000000060638077504000000000000000000
0,976443381110870016000000000000000000
ToPAS'2023
|