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!

Solucionando Problemas com Algoritmos

Olá! Esta semana vou tentar explicar um pouco sobre algoritmos. Um algoritmo nada mais é que uma sequencia de passos lógicos que, ao serem seguidos, levam à solução de um determinado problema. Nos posts anteriores nós já utilizamos alguns algoritmos para resolver os problemas da sequencia de Fibonacci e do fatorial. Estes são algoritmos simples, fáceis de entender e de se desenvolver. No entanto, alguns problemas exigem algoritmos bastante complexos para sua solução e, em alguns casos, não será possível encontrar um algoritmo para solucionar um problema em tempo hábil. Vou explicar esta última sentença mais adiante.

Para exemplificar, vou sugerir que o leitor faça um exercício. Abra o bloco de notas ou o seu editor favorito, ou mesmo apanhe um pedaço de papel e um lápis, e escreva em ordem numerada os passos que você efetua para ir ao trabalho pela manhã ao acordar, ou, se você é estudante, os passos que você efetua para chegar à escola ou universidade ou onde quer que você estude.

Isto que você fez também é um algoritmo, que soluciona o problema de ir a um local ao acordar pela manhã. Alguns irão escrever uma longa lista, bem detalhada. Outros irão escrever uma lista mais curta e simples. Cada lista é válida.

Para esta semana, não irei escrever nenhum código no post, mas irei propor um exercício, que consiste em desenvolver um algoritmo para solucionar um problema computacional, e então escrever um módulo Python que implemente tal algoritmo. A seguir descrevo o problema:

Considere que, para um determinado número inteiro n existe uma sequencia de números a partir de n que leva ao número 1. Tal sequencia será definida da seguinte forma:

• se n for ímpar, multiplique n por 3 e some 1 para obter o próximo número da sequencia
• caso contrário, ou seja, se n for par, divida o por 2 para obter o próximo número

Para determinar se um número é ímpar ou par utilize o operador "%". Este operador retorna o resto da divisão, logo, se "n % 2 == 1" significa que o número é ímpar, pois o resto da divisão por 2 foi igual a um.

Vejamos um exemplo, para n igual a 22 teremos a seguinte sequencia:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

O tamanho da sequencia, neste caso, é 16. O problema que proponho é, dados dois números, a e b, determinar qual o tamanho da maior sequencia gerada por todos os números entre estes, incluindo os próprios a e b.

Para solucionar estes problema, escreva um módulo "seq_3n1.py" com terá uma função "solucionar(a, b)" que retornará o tamanho da maior cadeia gerada

Publicarei uma solução para o exercício mais tarde esta semana no blog.