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.

Solução dos Exercícios e Desafio da Semana

Olá! É hora de conferir a solução do exercício e do desafio. Primeiro vamos ao exercício: escrever um módulo com duas funções que calculam o fatorial de um número, sendo uma recursiva e a outra linear:

# coding: utf-8
# fatorial.py

def fatorial_recursivo(numero):
    if numero == 1:
        return 1
    return numero * fatorial_recursivo(numero - 1)

def fatorial_linear(numero):
    k = numero - 1
    fatorial = numero
    while k > 0:
        fatorial = fatorial * k
        k -= 1
    return fatorial

if __name__ == '__main__':
    print fatorial_recursivo(5)
    print fatorial_linear(5)

Não tem muito mistério na solução acima. Apenas quero destacar um ponto: na versão linear, temos um comando que em Python pode ser reescrito de forma simplificada: "fatorial = fatorial * k". Isto pode ser reescrito como "fatorial *= k". Tal operação significa que a variável "fatorial" irá receber o resultado do seu valor atual multiplicado pelo valor da variável "k". Esta forma do comando também é válida para outras operações, tais como soma, subtração e divisão.

Agora a solução do desafio: o problema das Torres de Hanoi. Para resolver este problema utilizamos o princípio da indução, fazendo algumas suposição que assumiremos como verdade.

Como chegamos a resolução do problema para "n" anéis? Vamos simplificar: Suponha que você sabe solucionar o problema para "n - 1" anéis. Para solucionar o problema com "n" anéis, solucione o problema com "n - 1" anéis primeiro, mas movendo estes "n - 1" anéis para o pino temporário. Sendo assim, ao final desta etapa você terá "n - 1" anéis no pino temporário e o maior anel ainda estará no pino inicial. O pino destino estará, então, vazio, e você poderá mover o maior anel para ele diretamente. Agora, basta solucionar novamente o problema para "n - 1" anéis, movendo os "n - 1" anéis to pino temporário para o pino destino, utilizando o pino inicial como pino temporário.

Calma, se você ainda não entendeu não se preocupe, isto é normal. Leva um certo tempo para se acostumar com toda essa maluquice! Mas com a prática isto se tornará tão natural como se levantar pela manhã ao acordar. Vejamos como ficaria o código:

# coding: utf-8
# hanoi.py

def hanoi(n, inicial, destino, temporario):
    if n == 1:
        print 'Mova um anel do pino', inicial, 'para o pino', destino
    else:
        hanoi(n - 1, inicial, temporario, destino)
        print 'Mova um anel do pino', inicial, 'para o pino', destino
        hanoi(n - 1, temporario,  destino, inicial)

if __name__ == '__main__':
    # executar o procedimento para 5 anéis, sendo o pino 1 o inicial, o pino 2 o destino
    # e o pino 3 é o temporário
    hanoi(5, 1, 2, 3)

Executem o código acima e verifiquem que o resultado está correto! Estudem um pouco o seu funcionamento até que tenham entendido como ele funciona. Caso ainda tenham dúvidas, enviem um comentário que irei tentar ajudar a compreender melhor a solução.

Até a próxima!

Funções Recursivas

Hoje vou entrar num assunto que costuma espantar algumas pessoas, mas que pode ser bastante útil na criação de algoritmos para a resolução de problemas computacionais: as funções recursivas.

Funções recursivas são funções que chamam a si mesma de forma que, para resolver um problema maior, utiliza a recursão para chegar as unidades básicas do problema em questão e então calcular o resultado final.

Hmm... Ainda parece difícil de entender, certo? Bom, vamos ver como isto se aplica na prática. Voltamos ao nosso primeiro problema: a sequencia de Fibonacci. Nela nós temos dois casos base: O primeiro elemento da sequencia sempre é 1, assim como o segundo elemento da sequencia também é sempre 1.

Temos então o caso base. Para calcular os demais, utilizamos o seguinte parâmetro: o valor "i" da sequencia será o valor "i-1" da sequencia somado ao valor "i-2" da sequencia. Ou seja: fibonacci(i) = fibonacci(i - 1) + fibonacci(i - 2). Perceberam como podemos recorrer à própria funcão para calcular o valor de um elemento da sequencia? Vejamos como isto se traduz em código Python:

# coding: utf-8
# fib_recursivo.py

def fibonacci(indice):
    if indice == 1 or indice == 2:
        return 1
    return fibonacci(indice - 1) + fibonacci(i - 2)

A função agora ficou bem mais simples de entender que as versões anteriores com "for" e "while", certo? Pelo menos para mim esta forma é bem mais legível e podemos perceber diretamente como é o seu funcionamento. No entanto, as funções recursivas embutem alguns problemas. Pois é! Nem tudo é maravilhas no mundo de Alice!

A esta altura, você já sabe de algum problema que acontecerá com esta função?

Bom, o primeiro problema está na repetição do cálculo do mesmo valor. Vejamos um exemplo: calcular o quinto valor da sequencia.

1 =>                      x    =           fibonacci(5)
                                        /                 \
2 =>                      x    = fibonacci(4)    +       fibonacci(3)
                                  /       \                /        \
3 =>             x =   fibonacci(3) + fibonacci(2) + fibonacci(2) + fibonacci(1)
...
...

Perceba que, no passo 2 precisamos calcular o fibonacci(4) e o fibonacci(3). Então, no passo 3, precisamos calcular novamente o fibonacci(3) para encontrar o valor do fibonacci(4) do passo 2.

Mas existem outro problema com as funções recursivas. A pilha de chamadas não pode ser infinita, e alguns compiladores ou interpretadores limita o número máximo de chamadas a funções na pilha. Explico: Quando chamamos fibonacci(5), esta chamada irá chamar primeiramente fibonacci(4), sendo assim, a primeria chamada é colocada numa pilha e o controle passa para a segunda chamada. Então, fibonacci(4) chama fibonacci(3), sendo colocada também na pilha enquanto fibonacci(3) assume o controle. Agora imagine que você chamou fibonacci(1000). Quando a chamada chegar a fibonacci(2) serão 998 chamadas de função na pilha, sem contar que cada chamada ainda irá chamar uma segunda ramificação. Se você tentar desenhar uma árvove com as chamadas, verá que a coisa fica bem complexa.

Então meu conselho é o seguinte: use funções recursivas com cautela. Elas são ótimas para solucionar vários tipos de problemas, mas se você notar que a função está duplicando o trabalho ou que a pilha de chamadas será muito grande de acordo com o grau de recursividade, tente uma nova estratégia, como utilizar um algoritmo linear, sem recursão.

Para o exercício hoje vou fazer um pouco diferente. Vou propor um exercício simples e um desafio, um pouco mais complexo. O exercício é escrever um módulo com duas funções: a primeira calcula o fatorial de um número de forma recursiva e a segunda efetua o mesmo cálculo de forma linear, sem recursão.

O desafio é escrever um módulo que calcula a solução do problema da Torre de Hanoi. Tal solução pode ser encontrada de forma simples mas engenhosa utilizando recursão.

Para quem não conhece, a Torre de Hanoi consiste em ter 3 pinos onde no primeiro pino são postos "n" anéis de tamanhos decrescente. O problema é mover todos os "n" anéis para um pino destino, utilizando o terceiro pino como auxiliar, movendo sempre apenas um anel por vez e com a restrição de que num pino não se pode ter um anel menor abaixo de um anel maior.

É isto! Ainda nesta semana post a solução dos exercícios e do desafio. Até a próxima!

Solução do Problema Proposto: conversor.py

Bom Dia! No post anterior eu propus um problema que consistia em escrever um módulo para converter temperaturas entre graus Celsius e graus Fahrenheit. Hoje vou postar uma solução. Vejamos abaixo:

# coding: utf-8
# conversor.py

def celsius_para_fahr(graus):
    # a fórmula pode ser encontrada em:
    # http://www.albireo.ch/temperatureconverter/formula.htm
    graus_fahr = graus * 9.0 / 5.0 + 32.0
    return graus_fahr

Para testarmos nosso módulo, vamos escrever um outro módulo: "testa_conversor.py"

# !/bin/env python
# coding: utf-8
# testa_conversor.py

import conversor

def testes():
    pares = [(0.0, 32.0), (100.0, 212.0), (32.0, 89.6), 
             (38.0, 100.4), (20.0, 68.0)]
    
    for celsius, fahr in pares:
        calculado = conversor.celsius_para_fahr(celsius)
        if calculado != fahr:
            print "A função retornou um resultado inesperado na conversão do valor:", celsius
            print "O resultado esperado era:", fahr, " e o calculado foi:", calculado
        else:
            print "OK!"

if __name__ == '__main__':
    testes()

No módulo de teste incluí mais alguns detalhes que merecem uma explicação mais detalhada. No final do módulo podemos ver um "if" que testa de a variável "__name__" é igual à string "__main__" e, caso seja, chama a função "testes()". Não, isto não é magia negra... Acontece que em Python, algumas variáveis especiais são definidas pelo interpretador no momento que este importa o módulo. Neste caso, a variável "__name__" será definida como a string "__main__" quando o módulo for o mesmo que foi passado na linha de comando para execução, ou seja, quando executamos: python testa_conversor.py.

Outro detalhe é que definimos uma lista de tuplas com as temperaturas que queremos testar e utilizamos esta lista no "for". Como o "for" retorna cada elemento da lista utilizada e, neste caso, cada elemento é uma tupla que contém dois elementos, podemos tirar vantagem do "desempacotamento automático" que a linguagem nos oferece, atribuindo cada elemento da tupla a uma variável. Ou seja, no primeiro passo da iteração "for", a variável "celsius" receberá o valor do primeiro elemento da tupla e a variável "fahr" receberá o valor do segundo elemento da tupla, que são 0.0 e 32.0, respectivamente. Isto facilita em muito a codificação e dá um poder especial ao "for".

Outra coisa que não expliquei em posts anteriores é o funcionamento do comando "if". Tal comando funciona para a execução condicional de um bloco de operações. Ele testa uma condição e, caso esta retorne um valor que possa ser avaliado como "verdadeiro", o primeiro bloco do "if" é executado. No comando "if", opcionalmente, podemos especificar um segundo bloco de operações que deve ser executado caso a condição seja avaliada como "falsa". Isto pode ser realizado através do "else". Existe ainda uma terceira operação, o "elif", mas vou deixar para explicar o funcionamento deste num post futuro.

Bom pessoal, é isto! Ainda esta semana publico mais um post do nosso tutorial!

Mais sobre Módulos e Introdução sobre Funções

Nesta semana vou explicar um pouco mais sobre os módulos e introduzir um novo conceito: funções!

Os módulos em Python são definidos pelo arquivo .py o qual contém a sua lógica. Tal módulo pode ser reutilizado em outros módulos. Para isto, utilizamos o comando "import". Vejamos como isto funciona na prática

# !/bin/env python
# coding: utf-8
# fib.py

def fibonacci(indice):
    if indice == 1 or indice == 2:
        return 1
    a = 1
    b = 1
    for k in range(indice - 2):
        a, b = b, a + b
    return b

# !/bin/env python
# coding: utf-8
# main.py

import fib
for k in range(10):
    print u'O', k + 1, 'numero de Fibonacci é:', fib.fibonacci(k + 1)

O primeiro código, "fib.py" se refere a definição de uma função, "fibonacci", que recebe como parâmetro um número que indica o índice na sequência de Fibonacci que desejamos calcular o valor. Tal valor será passado para a variável "indice", que tem escopo local à função, ou seja, ela somente existirá dentro do corpo da função. O mesmo acontece no caso para as demais variáveis definidas dentro da função: "a", "b" e "k". Assim como no "for", para iniciar o bloco da função devemos terminar a linha com a definição do nome e dos parâmetros com um sinal de dois pontos, e identar o bloco de código da função com espaços.

No segundo código, "main.py", nós importamos o primeiro módulo definido em "fib.py". Para isto utilizamos o comando "import fib". Note que, ao importar o módulo, a extensão ".py" é omitida. Outro ponto que devo ressaltar é que o nome do arquivo deve obedecer as regras de definição dos nomes de variáveis. Peço perdão por não ter explicado tais regras antes: o nome do arquivo deve começar com uma letra do alfabeto ou um sinal de sublinhado ( _ ), e pode ser seguido por uma ou mais letras, números ou sinais de sublinhado; para as letras não são permitidos caracteres acentuados.

Voltando aos módulos, devemos ter um cuidado especial na utilização destes para evitar referências cíclicas. Isto ocorre quando um módulo "A" importa um módulo "B" e este também importa o módulo "A", formando um ciclo. Tal situação causará um erro no interpretador, mas não vou entrar em detalhes agora sobre o porquê isto ocorre. Apenas tenha em mente que tal situação deve sempre ser evitada.

No módulo "main.py", crio um loop que vai de 0 a 9 - lembrem que o "range()" retorna a lista iniciada em 0 e vai até o número anterior ao informado - e imprimo o valor da variável "k + 1" e o valor retornado pela função "fibonacci(k + 1)". Como a função foi definida no módulo "fib", para ter acesso a mesma devo informar ao interpretador onde encontrá-la. Para isto, adicionamos o nome do módulo seguido por um ponto e depois pelo nome da função, ficando com "fib.fibonacci(k + 1)".

A saída gerada ao executar o módulo "main.py" no terminal será:

$ python main.py
O 1 numero de Fibonacci é: 1
O 2 numero de Fibonacci é: 1
O 3 numero de Fibonacci é: 2
O 4 numero de Fibonacci é: 3
O 5 numero de Fibonacci é: 5
O 6 numero de Fibonacci é: 8
O 7 numero de Fibonacci é: 13
O 8 numero de Fibonacci é: 21
O 9 numero de Fibonacci é: 34
O 10 numero de Fibonacci é: 55

Bom, por hoje é só! Tenho gostado dos comentários que o blog vem recebendo e um deles sugeriu que fossem propostos exercícios. Sendo assim, vou propor um! Crie um módulo "conversor.py" que contém uma função "celsius_para_fahr(graus)". Tal função retornará o valor em graus Fahrenheit que corresponde ao valor em graus Celsius passado como parâmetro pela variável "graus".

Mais para o fim da semana eu publico mais um post com uma solução do exercício. Até breve!

Utilizando Módulos

Nesta semana vou explicar um pouco de como Python lida com módulos .

Os "módulos" são os arquivos que nós criamos cujo conteúdo são as linhas de código do nosso programa. Para a linguagem Python, tais arquivos devem terminar com a extensão ".py", por exemplo: "modulo1.py", "alunos.py", "cliente.py", etc.

Para criar tais arquivos, você pode usar um editor de texto, tal como o Notepad no Windows, ou o Vim no Linux e demais sistemas Unix. O meu predileto, no linux, é o Vim. Já no Windows não tenho um predileto, pulava de um para outro de tempos em tempos. Um dos bons editores que encontrei é o Komodo Edit, da ActiveState.

Tais editores são melhores que os editores do tipo Notepad por oferecerem variadas funções para auxiliar na programação, tais como auto-completar palavras chave e colorir o código para melhor leitura e entendimento do mesmo, além de indicar possíveis erros de digitação.

Vou utilizar o exemplo da semana passada e escrever um módulo que imprime os 100 primeiros números da sequência de Fibonacci:

#!/bin/env python
# coding: utf-8

a = 1
b = 1
print "Os 100 primeiros números de Fibonacci são:", a, b,
for k in range(98):
    print a + b,
    a, b = b, a + b

Salve estas linhas num arquivo, "c:\tutorial-python\fibonacci.py" por exemplo, se você está no Windows, ou "~/tutorial-python/fibonacci.py" no caso de você utilizar Linux.

Espero que os usuário Linux estejam familiarizados com o terminal. Para os usuários Windows, este não é tão comum, portanto vou explicar como chegar até ele: Clique no menu "Iniciar", depois "Executar...". Na caixa de diálogo que aparece, digite "cmd", sem as aspas, e clique "Ok". Uma janela preta aparecerá. Este é o terminal! Para navegar nas pastas do seu computador, utilize o comando "cd". Este comando funciona da mesma forma, tanto no Linux quanto no Windows. No caso do Windows, digite:

cd \tutorial-python

No caso do Linux:

cd ~/tutorial-python

Para executar o arquivo, digite:

python fibonacci.py

Se você está no Windows, provavelmente obterá um erro parecido com "comando não encontrado". Isto se deve ao fato de o interpretador Python não estar nos caminhos que o Windows busca os comandos por padrão. Você pode resolver isto de duas formas:

• Adicionar o caminho da pasta "c:\Python25" entre as pastas de busca padrão do Windows, algo para usuários mais experientes
• Utilizar o caminho completo sempre que for executar um arquivo

Para utilizar o caminho completo, você deve executar o arquivo da seguinte forma:

c:\python25\python fibonacci.py

No entanto, no caso do Windows, quando você instala o interpretador Python este registra automaticamente a extensão ".py" como executável. Sendo assim, você também pode executar o arquivo digitando apenas:

fibonacci.py

O leitor atento deve ter notado uma linha estranha no código acima: # coding: utf-8. Esta linha indica que a codificação do texto do arquivo é UTF-8, o que permite o uso de caracteres acentuados no código. Por isso, recomendo sempre adicionar esta linha no cabeçalho de seus módulos. Mesmo que você esteja escrevendo um programa totalmente em Inglês.

Existem algumas vantagens óbvias de se programar escrevendo arquivos e não diretamente no interpretador como nós utilizamos até agora. Uma delas é que, ao se encerrar o interpretador, qualquer código que você tenha escrito estará perdido. Já utilizando arquivos, tudo está salvo, podendo ser reutilizado no futuro.

No entanto, utilizar o interpretador também tem lá suas vantagens, tais como fazer testes rápidos de algum trecho de código sem a necessidade de se criar um arquivo para isto. Porém, se você pretende programar pra valer, você terá que lidar com arquivos para escrever seus códigos.

Bom pessoal, por hoje é isso! Gostaria de agradecer os incentivos que tenho visto nos comentários. Algumas pessoas comentaram também que pulei certas etapas no processo. Realmente isto é verdade, mas pulei estas etapas meio que de propósito, para evitar ter que explicar algumas dezenas de definições, as quais espero explicar gradualmente no decorrer das postagens. Como havia dito no post inaugural, minha intenção é escrever um post por semana, mas se for o caso vou tentar escrever mais de um post em algumas semanas. Caso o ritmo fica muito acelerado, postem comentários que voltarei a limitar os posts a um por semana.

Vejo vocês no próximo post!