Solução do problema 3n + 1

Olá pessoal! Hoje trago a solução do problema 3n + 1 proposto no início da semana. Então vamos direto a ela:

# coding: utf8
# seq_3n1.py

resolvidos = {1: 1}

def solucionar(a, b):
    maior = 0
    while a <= b:
        num = calc_seq(a)
        if num > maior:
            maior = num
        a += 1

    return maior

def calc_seq(a):
    if a in resolvidos:
        return resolvidos[a]
    if (a % 2) == 0:
        new_a = a / 2
    else:
        new_a = 3 * a + 1
        
    passos = 1 + calc_seq(new_a)
    resolvidos[a] = passos 
    return passos
    
if __name__ == '__main__':
    maior = solucionar(1, 10)
    print "A maior sequencia gerado por um número entre 1 e 10 tem tamanho:", maior
    
    maior = solucionar(100, 200)
    print "A maior sequencia gerado por um número entre 100 e 200 tem tamanho:", maior
    
    maior = solucionar(201, 210)
    print "A maior sequencia gerado por um número entre 201 e 210 tem tamanho:", maior
    
    maior = solucionar(900, 1000)
    print "A maior sequencia gerado por um número entre 900 e 1000 tem tamanho:", maior   

Note que, para calcular a sequencia, utilizo uma função recursiva. Esta função primeiro verifica se já sabemos o tamanho da cadeia para o número que estamos procurando no dicionário "resolvidos". Caso este valor não esteja presente, calculamos o próximo elemento da sequencia e atribuímos o tamanho da sequencia como sendo o tamanho da sequencia do proximo elemente acrescido de 1, salvando este tamanho no dicionário.

Você pode estar se perguntando qual a razão de utilizarmos este dicionário, mas a razão é de simplesmente evitar cálculos repetidos. Inevitavelmente, quando estivermos calculando todas as sequencias de 100 a 200, por exemplo, iremos nos encontrar recalculando a mesma sequencia inúmeras vezes. Mas, se já tivermos calculado uma sequencia anteriormente, podemos simplesmente consultar o tamanho da sequencia gerada no dicionário, o que nos salvará um tempo precioso.

Bom, é isto. Como vocês podem notar, a solução é bastante simples e, com a ajuda de um dicionário, uma estrutura de dados valiosa que temos presente na linguagem Python, foi possível evitar um problema que frequentemente nos deparamos ao utilizar funções recursivas, que é a repetição de cálculos.

Espero ter sido claro na minha explicação e, como sempre, se tiverem dúvidas fiquem a vontade para enviar comentários. Até o próximo post!