Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Gerando números pseudo-aleatórios com o método do middle-square

0 votos
24 visitas
perguntada Dez 1, 2020 em Ciência da Computação por Felipe Yudi (46 pontos)  

O seguinte exercício for retirado do livro The art of computer programming, Vol2, Cap. 3.1 ex 8.

Examine o método do "middle-square" no caso de números com dois dígitos.

(a) O processo pode ser iniciado com qualquer um dos 100 valores possíveis, isto é, 00, 01, 02, ..., 99. Quantos desses valores levam ao ciclo 00, 00, ...

(b) Quantos ciclos finais existem? Qual o ciclo mais longo?

(c) Qual valor inicial gerará o maior número de elementos distintos antes da sequência se repetir?

Compartilhe

1 Resposta

0 votos
respondida Dez 1, 2020 por Felipe Yudi (46 pontos)  
editado Dez 17, 2020 por Felipe Yudi

O método middle-square é um método para a geração de sequências de números pseudo-aleatórios. Para gerar a seguência, escolha um número de n dígitos e o eleve ao quadrado. Geralmento, isso irá produzir um número de 2n digitos. Caso o quadrado tenha menos de 2n dígitos, acrescentamos zeros na frente até o quadrado atingir 2n dígitos. Após isso selecionamos os n dígitos centrais do quadrado e usamos como o novo número para o próximo termo da sequência.

Por exemplo, se escolhermos o número 44, então \(n=2\) assim esperamos que \(n^2\)produza um número de \(2n =4\) dígitos. Como \(44^2=1936\), selecionamos os n dígitos centrais de \(44^2\) (93) e o elevamos ao quadrado novamente, continuando o ciclo.

Porém se o número for 11, então \(11^2=121\), que tem 3 dígitos. Note que nesse caso, \(2n=4 \neq 3\). Assim, colocaremos zeros na frente de 121 até atingirmos 4 dígitos. Nosso número será 0121. Os n dígitos centrais são 12, e é esse o novo número usado na sequência.

O exemplo completo com o número 11 é:
Square: 0121 Seed: 12
Square: 0144 Seed: 14
Square: 0196 Seed: 19
Square: 0361 Seed: 36
Square: 1296 Seed: 29
Square: 0841 Seed: 84
Square: 7056 Seed: 5
Square: 0025 Seed: 2
Square: 0004 Seed: 0
A partir daí o ciclo se repete com zeros.

Uma função para calcular uma sequência gerada pelo método middle-square para números de dois dígitos é:

def middleSquare2(seed): 
    numbers_dic = {}
    counter = 0 
    while seed not in numbers_dic.values(): 
        numbers_dic[counter] = seed
        counter += 1
        square = str(seed * seed).zfill(4)
        seed = int(square[1:3])

    return numbers_dic

Ela retorna um dicionário onde as chaves são os contadores (número de vezes que o algorítimo foi aplicado) e os valores são os números pseudo-aleatórios gerados.

Por exemplo, se seed = 11:

print(middleSquare2(11))
{0: 11, 1: 12, 2: 14, 3: 19, 4: 36, 5: 29, 6: 84, 7: 5, 8: 2, 9: 0}

O comprimento dos ciclos e os últimos valores das sequências são:

for i in range(0, 100):
    a = middleSquare2(i)
    max_key = max(list(a.keys()))

    print("Number:", i, "Cycle length:", max_key, "Last Value:", a[max_key])

Number: 0 Cycle length: 0 Last Value: 0
Number: 1 Cycle length: 1 Last Value: 0
Number: 2 Cycle length: 1 Last Value: 0
Number: 3 Cycle length: 1 Last Value: 0
Number: 4 Cycle length: 2 Last Value: 0
Number: 5 Cycle length: 2 Last Value: 0
Number: 6 Cycle length: 2 Last Value: 0
Number: 7 Cycle length: 3 Last Value: 0
Number: 8 Cycle length: 3 Last Value: 0
Number: 9 Cycle length: 4 Last Value: 0
Number: 10 Cycle length: 0 Last Value: 10
Number: 11 Cycle length: 9 Last Value: 0
Number: 12 Cycle length: 8 Last Value: 0
Number: 13 Cycle length: 7 Last Value: 0
Number: 14 Cycle length: 7 Last Value: 0
Number: 15 Cycle length: 5 Last Value: 10
Number: 16 Cycle length: 6 Last Value: 0
Number: 17 Cycle length: 6 Last Value: 0
Number: 18 Cycle length: 3 Last Value: 0
Number: 19 Cycle length: 6 Last Value: 0
Number: 20 Cycle length: 2 Last Value: 60
Number: 21 Cycle length: 8 Last Value: 0
Number: 22 Cycle length: 4 Last Value: 10
Number: 23 Cycle length: 4 Last Value: 10
Number: 24 Cycle length: 1 Last Value: 57
Number: 25 Cycle length: 5 Last Value: 0
Number: 26 Cycle length: 5 Last Value: 10
Number: 27 Cycle length: 5 Last Value: 0
Number: 28 Cycle length: 5 Last Value: 0
Number: 29 Cycle length: 4 Last Value: 0
Number: 30 Cycle length: 2 Last Value: 10
Number: 31 Cycle length: 10 Last Value: 0
Number: 32 Cycle length: 2 Last Value: 0
Number: 33 Cycle length: 4 Last Value: 0
Number: 34 Cycle length: 6 Last Value: 10
Number: 35 Cycle length: 5 Last Value: 10
Number: 36 Cycle length: 5 Last Value: 0
Number: 37 Cycle length: 6 Last Value: 0
Number: 38 Cycle length: 8 Last Value: 0
Number: 39 Cycle length: 4 Last Value: 10
Number: 40 Cycle length: 1 Last Value: 60
Number: 41 Cycle length: 6 Last Value: 0
Number: 42 Cycle length: 14 Last Value: 0
Number: 43 Cycle length: 4 Last Value: 0
Number: 44 Cycle length: 7 Last Value: 0
Number: 45 Cycle length: 2 Last Value: 0
Number: 46 Cycle length: 10 Last Value: 0
Number: 47 Cycle length: 3 Last Value: 60
Number: 48 Cycle length: 3 Last Value: 10
Number: 49 Cycle length: 2 Last Value: 60
Number: 50 Cycle length: 0 Last Value: 50
Number: 51 Cycle length: 1 Last Value: 60
Number: 52 Cycle length: 3 Last Value: 10
Number: 53 Cycle length: 3 Last Value: 60
Number: 54 Cycle length: 7 Last Value: 0
Number: 55 Cycle length: 2 Last Value: 0
Number: 56 Cycle length: 8 Last Value: 0
Number: 57 Cycle length: 1 Last Value: 24
Number: 58 Cycle length: 6 Last Value: 0
Number: 59 Cycle length: 4 Last Value: 10
Number: 60 Cycle length: 0 Last Value: 60
Number: 61 Cycle length: 5 Last Value: 0
Number: 62 Cycle length: 4 Last Value: 0
Number: 63 Cycle length: 10 Last Value: 0
Number: 64 Cycle length: 5 Last Value: 0
Number: 65 Cycle length: 5 Last Value: 10
Number: 66 Cycle length: 6 Last Value: 10
Number: 67 Cycle length: 4 Last Value: 10
Number: 68 Cycle length: 5 Last Value: 0
Number: 69 Cycle length: 14 Last Value: 0
Number: 70 Cycle length: 2 Last Value: 10
Number: 71 Cycle length: 3 Last Value: 0
Number: 72 Cycle length: 4 Last Value: 0
Number: 73 Cycle length: 3 Last Value: 0
Number: 74 Cycle length: 4 Last Value: 60
Number: 75 Cycle length: 5 Last Value: 0
Number: 76 Cycle length: 13 Last Value: 0
Number: 77 Cycle length: 12 Last Value: 0
Number: 78 Cycle length: 4 Last Value: 0
Number: 79 Cycle length: 2 Last Value: 57
Number: 80 Cycle length: 2 Last Value: 60
Number: 81 Cycle length: 9 Last Value: 0
Number: 82 Cycle length: 5 Last Value: 0
Number: 83 Cycle length: 6 Last Value: 60
Number: 84 Cycle length: 3 Last Value: 0
Number: 85 Cycle length: 5 Last Value: 10
Number: 86 Cycle length: 5 Last Value: 10
Number: 87 Cycle length: 9 Last Value: 0
Number: 88 Cycle length: 5 Last Value: 60
Number: 89 Cycle length: 12 Last Value: 0
Number: 90 Cycle length: 1 Last Value: 10
Number: 91 Cycle length: 6 Last Value: 0
Number: 92 Cycle length: 11 Last Value: 0
Number: 93 Cycle length: 6 Last Value: 0
Number: 94 Cycle length: 7 Last Value: 60
Number: 95 Cycle length: 2 Last Value: 0
Number: 96 Cycle length: 9 Last Value: 0
Number: 97 Cycle length: 2 Last Value: 60
Number: 98 Cycle length: 1 Last Value: 60
Number: 99 Cycle length: 3 Last Value: 60

(a) 62 números levam a um ciclo de zeros. São eles:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 25, 27, 28, 29, 31, 32, 33, 36, 37, 38, 41, 42, 43, 44, 45, 46, 54, 55, 56, 58, 61, 62, 63, 64, 68, 69, 71, 72, 73, 75, 76, 77, 78, 81, 82, 84, 87, 89, 91, 92, 93, 95, 96]

(b) Há 6 ciclos possíveis. Eles terminam em [0, 10, 60, 57, 50, 24]. Já o ciclo mais longo é de tamanho 14. São eles os ciclos iniciados em 42 e 69

(c) As sequências que gerarão o maior número de elementos distintos antes de se repetir são as iniciadas em 42 e 69. São elas:
42: {0: 42, 1: 76, 2: 77, 3: 92, 4: 46, 5: 11, 6: 12, 7: 14, 8: 19, 9: 36, 10: 29, 11: 84, 12: 5, 13: 2, 14: 0}
69: {0: 69, 1: 76, 2: 77, 3: 92, 4: 46, 5: 11, 6: 12, 7: 14, 8: 19, 9: 36, 10: 29, 11: 84, 12: 5, 13: 2, 14: 0}

comentou Dez 17, 2020 por leonardocarvalho (21 pontos)  
Boa tarde, Felipe

Gostei bastante da solução, ela é simples e eficiente em encontrar o número de ciclos de números até bem maiores do que 100. Testei com 1.000.000 e levou cerca de apenas 30 segundos para achar todos os tamanhos de ciclos na minha máquina.
Só encontrei um problema no código que é no for loop. A função print tem que estar dentro dele para que todos os ciclos sejam impressos na tela conforme o algoritmo for avançando. Da forma como está será apenas impresso valor do último ciclo, ou seja:

Number: 99 Cycle length: 3 Last Value: 60

Arrumando isso ele funcionará da forma descrita na sua resposta.
comentou Dez 17, 2020 por Felipe Yudi (46 pontos)  
Obrigado pelo aviso Leonardo! Já corrigi.
...