sexta-feira, 19 de junho de 2009

Adicionando tela de fundo.

Olá! Continuando nosso pequeno joguinho, esta semana vamos fazer a tela de fundo um pouco mais interessante que apenas um fundo preto e opaco... Vamos adicionar estrelas, com movimento!

Abaixo está o código da classe "Background", que devemos salvar no arquivo "background.py".

# coding: utf8
# background.py

import pygame
import random

class Background(object):
    
    def __init__(self, max_stars=100):
        self.max_speed = 6
        screen = pygame.display.get_surface()
        size = screen.get_size()
        back = pygame.Surface(size).convert()
        back.fill( (0,0,0) )
        self.image = back
        self.stars = []
        for _ in range(max_stars):
            rand = random.randint
            self.stars.append( [rand(0, size[0]), rand(0, size[1]), rand(1, self.max_speed)])
    
    def update(self):
        size = pygame.display.get_surface().get_size()
        for star in self.stars:
            star[1] += star[2]
            if star[1] >= size[1]:
                star[1] = 0
                star[0] = random.randint(0, size[0])
                star[2] = random.randint(1, self.max_speed)
    
    def draw(self, screen):
        image = self.image
        image.fill( (0, 0, 0) )
        for star in self.stars:
            image.set_at(star[:2], (255, 255, 255))
        
        screen.blit(self.image, (0, 0))

Como vocês podem ver, a classe é bem simples. Inicializamos a o objeto background com um número máximo padrão de 100 estrelas, cada estrela irá se mover de cima para baixo na tela, dando a impressão que estamos percorrendo o espaço. Atribuímos também a velocidade máxima com que cada estrela poderá se movimentar.

Preenchemos a tela com o tradicional fundo preto, criamos uma "Surface" que será onde iremos desenhar nossas estrelas e salvamos essa "Surface" na variável "self.image".

Agora a parte interessante. A criação das estrelas. Para nosso exemplo, faremos da forma mais simples possível: uma array com 3 números, representando a posição da estrela e sua velocidade (x, y, velocidade).

O método "update(self)" é onde ocorre a atualização do estado do nosso background. O que faremos aqui é simplesmente adicionar a velocidade (star[2]) à coordenada y da posição (star[1]). Caso após adicionarmos a velocidade a estrela suma, ou seja, sua cordenada y passe a ser maior que o tamanho da nossa tela na vertical, reposicionamos esta estrela, colocando-a no topo da tela, com novos valores para a coordenada x e para a velocidade. Note que para a velocidade sempre iremos desejar um valor >= 1, pois caso contrário teríamos uma estrela estática.

O método "draw(self)" é mais simples ainda. Preenchemos a nossa imagem com preto e então percorremos a lista de estrelas, adicionando um ponto branco para cada uma delas em sua posição atual. Após isso chamamos "blit" na variável "screen". O que está função faz é copiar o conteúdo de uma "Surface" para outra. Assim, ao copiarmos o fundo para a "Surface" screen, estaremos substituindo a imagem que será mostrada na tela na próxima atualização.

O que resta agora é apenas alterar a classe "Game" para utilizar o nosso background animado. Abaixo está o código da classe com as devidas alterações:

# coding: utf8
# game.py

import pygame
import random

from pygame.locals import *
import background

class Game(object):
    
    def __init__(self, size):
        pygame.init()
        flags = DOUBLEBUF
        self.screen = pygame.display.set_mode(size, flags)
        self.screen_size = self.screen.get_size()
        
        pygame.mouse.set_visible(False)
        pygame.display.set_caption('Meu Primeiro Jogo em Python')
        
        self.run = True
        self.list = {
            'player': pygame.sprite.RenderPlain(),
            'enemy': pygame.sprite.RenderPlain(),
            'fire': pygame.sprite.RenderPlain(),
            'enemy_fire': pygame.sprite.RenderPlain(),
        }
        self.player = None
        self.background = background.Background()
    
    def update_actors(self):
        if self.background is not None:
            self.background.update()
        
        for actor in self.list.values():
            actor.update()
    
    def draw_actors(self):
        if self.background is not None:
            self.background.draw(self.screen)
        else:
            self.screen.fill(0)
        
        for actor in self.list.values():
            actor.draw(self.screen)
    
    def act_actors(self):
        pass
    
    def manage(self):
        pass
    
    def handle_events(self):
        player = self.player
        for event in pygame.event.get():
            t = event.type
            
            if t in (KEYDOWN, KEYUP):
                k = event.key
            
            if t == QUIT:
                self.run = False
            elif t == KEYDOWN and k == K_ESCAPE:
                self.run = False
            elif t == KEYUP:
                pass
    
    def loop(self):
        clock = pygame.time.Clock()
        
        while self.run:
            clock.tick(1000)
            
            self.handle_events()
            self.manage()
            
            self.act_actors()
            self.update_actors()
            self.draw_actors()
            
            pygame.display.flip()

if __name__ == '__main__':
    game = Game( (640, 480) )
    game.loop()

Como você pode observar, com poucas linhas de código criamos um fundo de tela animado bem legal. No próximo post vou adicionar algumas naves. Até!

sexta-feira, 29 de maio de 2009

Loop Básico com PyGame

Bom Dia! Vou postar hoje o código de um loop básico para o jogo com naves usando PyGame. Para instalar a biblioteca PyGame vá até o site www.pygame.org e siga as instruções.

Vejamos abaixo o código:

# coding: utf8
# game.py

import pygame
import random

from pygame.locals import *

class Game(object):
    
    def __init__(self, size):
        pygame.init()
        flags = DOUBLEBUF
        self.screen = pygame.display.set_mode(size, flags)
        self.screen_size = self.screen.get_size()
        
        pygame.mouse.set_visible(False)
        pygame.display.set_caption('Meu Primeiro Jogo em Python')
        
        self.run = True
        self.list = {
            'player': pygame.sprite.RenderPlain(),
            'enemy': pygame.sprite.RenderPlain(),
            'fire': pygame.sprite.RenderPlain(),
            'enemy_fire': pygame.sprite.RenderPlain(),
        }
        self.player = None
        self.background = None
        self.actors = None
    
    def update_actors(self):
        if self.background is not None:
            self.background.update()
        
        for actor in self.list.values():
            actor.update()
    
    def draw_actors(self):
        if self.background is not None:
            self.background.draw(self.screen)
        else:
            self.screen.fill(0)
        
        for actor in self.list.values():
            actor.draw(self.screen)
    
    def act_actors(self):
        pass
    
    def manage(self):
        pass
    
    def handle_events(self):
        player = self.player
        for event in pygame.event.get():
            t = event.type
            
            if t in (KEYDOWN, KEYUP):
                k = event.key
            
            if t == QUIT:
                self.run = False
            elif t == KEYDOWN and k == K_ESCAPE:
                self.run = False
            elif t == KEYUP:
                pass
    
    def loop(self):
        clock = pygame.time.Clock()
        
        while self.run:
            clock.tick(1000)
            
            self.handle_events()
            self.manage()
            
            self.act_actors()
            self.update_actors()
            self.draw_actors()
            
            pygame.display.flip()

if __name__ == '__main__':
    game = Game( (640, 480) )
    game.loop()

Este será o corpo de nossa classe principal do jogo. Salve este arquivo e o execute. Você verá que o PyGame abrirá uma janela com tamanho 640x480 preenchida com a cor preta. Ao pressionar a tecla ESC a aplicação é terminada.

Pode não parecer, mas com estas poucas linhas de código já temos a estrutura básica para o nosso jogo. No construtor da class "Game" nós inicializamos a tela do jogo, utilizando o parâmetro "DOUBLEBUF", mais a diante explico o motivo de se utilizar este parâmetro. Então informamos um título para a janela e que desejamos que o mouse não seja visível dentro da janela do jogo.

As variáveis "run" e "list" são então inicializadas. A primeira indica se o jogo deve continuar ou não. A segunda guarda lista de sprites em quatro categorias. A classe "pygame.sprite.RenderPlain" é responsável por guardar as lista com os sprites e ela também será responsável por desenhar esta lista na tela. Na categoria "player" teremos apenas o sprite da nossa nave. Em "enemy" teremos os sprites das naves inimigas. Em "fire" adicionaremos os sprites dos nossos tiros, e, finalmente, em "enemy_fire" adicionaremos os sprites dos tiros das naves inimigas.

Temos então as variáveis "player" e "background", que serão exatamente objetos que representam o jogador e o plano de fundo de nosso jogo.

O método "update_actors" é o responsável por atualizar o estado de nossos objetos do jogo. Primeiro nós atualizamos o estado do plano de fundo, se houver um, e então atualizamos os atores, que são os objetos na nossa lista de sprites.

No método "draw_actors" temos um comportamento semelhante ao método "update_actors", mas nesse caso iremos escrever os pixels dos nossos plano de fundo e sprites na tela.

Em "act_actors" por enquanto não iremos ter nenhum código, mas é aqui que nós iremos tratar a ação de nosso jogo. Esta parte será explicada em um próximo post. O método "manage" será responsável por controlar se adicionamos mais inimigos ou não dependendo do estado do jogo. Por enquanto não irei mostrar o código desta parte também.

Em "handle_events" nós perguntamos ao pygame quais eventos ocorreram e então os tratamos. Por enquanto só temos interesse nos eventos do tipo "QUIT" e "KEYDOWN". Caso o evento "QUIT" aconteça ou no caso de "KEYDOWN" com a tecla "ESC" sendo pressionada, nós ajustamos a variável "run" para "False", o que fará que o loop principal de nosso jogo termine.

Chegamos, então, ao loop principal do jogo. Aqui criamos a variável "clock". Esta variável irá controlar a velocidade do jogo, de forma que o jogo não fique demasiado lento em máquinas menos potentes nem demasiado rápido em máquinas mais potentes.

Então temos nosso loop. Nós primeiros tratamos os possíveis eventos, depois atualizamos o estado do jogo para só então desenharmos os objetos na tela.

A última linha deste loop: "pygame.display.flip()" é bem interessante. Lembram do parâmetro "DOUBLEBUF" que utilizamos anteriormente na inicialização da tela? Pois aquele parâmetro informa ao pygame que, quando escrevermos os pixels na tela, na verdade estaremos escrevendo pixels numa espécie de buffer, que não é mostrado imediatamente na tela. Sendo assim, quando chamamos a função "pygame.display.flip()" este buffer é inteiramente copiado para a tela e a superfícies que estava sendo mostrada se tornará o novo buffer. Esse é o motivo da função se chamar "flip", pois ela "troca" as superfície atual com a temporária.

O "double buffering" como chamamos esta técnica é utilizado para evitar que durante o processo de desenho dos pixels o usuário veja imagens aparecendo uma após a outra na tela, causando um efeito indeseável e até mesmo problemas como o de sprites que são desenhados sobre outros sprites.

Bom, é isso! Em breve trarei mais um post com a classe "Background" que irá mostrar estrelas no plano de fundo, movimentandos no estilo dos famosos "vertical scrollers".

quinta-feira, 28 de maio de 2009

Retomando os Trabalhos!

Olá pessoal! Faz algum tempo que não atualizo o blog, é que estive muiiittoooo ocupado com o trabalho...

Bom, hoje vou começar a entrar nos detalhes do nosso projeto, finalmente! Vou falar um pouco do pygame, a biblioteca Python utilizada no desenvolvimento de jogos. Esta biblioteca irá nos fornecer praticamente tudo o que precisamos para desenvolver um jogo em Python, no que se diz respeito a parte programática da coisa.

Como é sabido, na história do desenvolvimento de jogos quase sempre se utilizam linguagens de baixo nível, tais como C/C++. Isto ocorre devido ao fato da necessidade de desempenho que está implícita na programação de jogos.

No entanto, tal desempenho vem com um custo. O desenvolvedor passa a ter que tratar de detalhes que não têm relação com o desenvolvimento do jogo propriamente dito, tais como o gerenciamento de memória e o tratamento de erros. Outro detalhe é que no desenvolvimento de jogos sempre temos algumas características que estão sempre presentes, tais como os sprites - figuras animadas ou não, e as rotinas que manipulam estes sprites, utilização de sons, recursos de rede, etc. Tendo isto em mente, surgiram várias bibliotecas dedicadas a facilitar a vida dos desenvolvedores de jogos, oferecendo o suporte básico a tais funcionalidades. Este é o caso da biblioteca SDL, a qual é a base da biblioteca pygame.

Ou seja, temos a biblioteca SDL, totalmente otimizada para linguagens de baixo nível, e temos o pygame, que possibilita o acesso a SDL através da linguagem Python. Isto torna o desenvolvimento de jogos utilizando Python uma realidade, já que temos apenas que nos preocupar com a criação do jogo em si, e, uma vez que com Python temos uma forma simples de expressar nossas ideias, deixando os detalhes de baixo nível para o pygame, podemos focar apenas na parte criativa.

Conceitos Básicos

O loop principal de um jogo é bastante simples. Basicamente temos que tratar os eventos, tais como o movimento do mouse ou uma tecla ser pressionada ou a recepção de dados via rede, executar a inteligência artificial e então o desenho do plano de fundo e de personagens visíveis. Vejamos abaixo como isso é feito de um modo geral:

01. Inicializar estruturas internas
02. Carregar dados do jogo
03. Repetir:
04.    Capturar e tratar eventos
05.    Executar a inteligência artificial
06.    Desenhar plano de fundo
07.    Desenhar personagems
08.    Emitir sons se necessário
09. Terminar o loop se o usuário deseja terminar o jogo.

Este pseudo código resume o laço principal de qualquer jogo, por mais avançado que seja, sempre terá um loop parecido com este.

No próximo post pretendo mostrar os passo para a criação de um jogo bem simples, onde o jogador controla uma nave espacial e deve derrotar os inimigos, no estilo "vertical scroller", ou seja, os inimigos irão aparecer no topo da tela e seguirão para baixo tentando acertar a nave do jogador. Espero postar uma primeira parte ainda hoje, ou no máximo amanhã. Então fiquem ligado!

quinta-feira, 19 de março de 2009

Herança

Esta semana vou falar sobre mais um tópico relativo a orientação a objetos: herança.

Herança consiste em fazer com que uma classe "herde" os atributos e métodos de uma outra classe, podendo reescrevê-los ou adicionar funcionalidade à estes.

Vamos a um exemplo prático, a partir da classe que especificamos anteriormente:

# coding: utf-8
# mamifero.py

class Mamifero:
    
    def som(self):
        print 'emitir um som'

class Homem(Mamifero):
        
    def som(self):
        print 'Oi!'

class Cachorro(Mamifero):
    
    def som(self):
        print 'Wufff! Wufff!'

class Gato(Mamifero):
    
    def som(self):
        print 'Meawwwww!'

mamifero = Mamifero()
mamifero.som()

animais = [Homem(), Cachorro(), Gato()]

for animal in animais:
    animal.som()
    

No código acima, criamos 3 classes onde estas herdam os atributos da classe "Mamifero". Neste caso estou demonstrando como podemos reescrever os métodos de uma classe para alterar o funcionamento deste numa classe mais específica.

Ao executar o código acima, no "for" mais abaixo no código, percorreremos uma lista de animais, chamando o método "som()" para cada um deles. Como cada animal foi criado a partir de uma classe específica, o método desta classe mais específica é chamado, e não o da classe mais genérica, "Mamifero". Sendo assim, o som emitido será o que nós esperamos.

Estou indo devagar nesta introdução à classes por este ser um tópico que causa muita confusão nos programadores iniciantes, mas que após um certo tempo de prática se mostra um paradigma interessante e fácil de lidar no dia a dia, tornando a abstração de problemas reais em algoritmos mais simples.

domingo, 1 de março de 2009

De Volta Após o Carnaval!

Olá Pessoal!

Pois é, passado o carnaval, estamos de volta! Esta semana vou entrar num tema bastante interessante: orientação a objetos.

Um conceito fundamental de orientação a objetos é o conceito de classes. Uma classe é uma abstração de um modelo, incluindo dados sobre o modelo e ações que podem ser tomadas sobre este modelo.

Um exemplo clássico de classe apresentada nos cursos de programação é a classe Mamífero. Vou utilizá-la aqui também, por ser de simples entendimento.

Vamos pensar um pouco sobre um mamífero... O que os mamíferos tem em comum? Podemos citar a data de nascimento, por exemplo. Este, aliás, é um atributo comum a todos os seres vivos, não somente os mamíferos... ;-)

Então, como definimos uma classe em Python? Não poderia ser mais simples. Vejamos o exemplo abaixo:

# coding: utf-8
# mamifero.py

class Mamifero:
    def __init__(self):
        self.nascimento = '5 de julho de 1981'

mamifero = Mamifero()
print mamifero.nascimento

No código acima, definimos a classe "Mamifero" e criamos um método, que é uma função pertencente à classe, chamado "__init__". Este método é especial, servindo como inicializador. Ou seja, sempre que um objeto da classe "Mamifero" for criado, este método especial será chamado.

Um outro detalhe é a variável "self". Tal variável representa o objeto para o qual o método foi chamado. No caso do método "__init__", o self representa o objeto que está sendo criado naquele momento.

No método "__init__", criamos um atributo para o objeto, indicando a data do nascimento. Para isto, simplesmente atribuimos uma nova propriedade ao objeto "self". A sintaxe da atribuição é bem simples: objeto.atributo = valor. Tal atribuição fará com que o objeto referenciado tenha um novo atributo, ou, caso o objeto já tenha o atributo especificado, atribuirá um novo valor a ele.

Para criar um novo objeto, a sintaxe também é bem simples: novo_objeto = Classe(). E para acessar um atributo do objeto utilizamos a sintaxe: objeto.atributo. Como vocês podem notar, a linguagem Python faz com que a criação e a utilização de classes e objetos seja o mais simples possível. Eu particularmente gosto do paradigma de orientação a objetos, e aconselho sempre utilizar classes em seus programas.

Vou manter este post bem básico mesmo, apenas com esta definição de classes. Na próxima semana vou mostrar um exemplo mais elaborado da utilização destas. Até o próximo post!

domingo, 8 de fevereiro de 2009

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!

quarta-feira, 4 de fevereiro de 2009

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.

sexta-feira, 30 de janeiro de 2009

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!

terça-feira, 27 de janeiro de 2009

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!


segunda-feira, 26 de janeiro de 2009

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!

terça-feira, 20 de janeiro de 2009

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!

quarta-feira, 14 de janeiro de 2009

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!

quinta-feira, 8 de janeiro de 2009

Controle de Fluxo

Depois das festas de Natal e Ano Novo, é hora de voltar ao trabalho!

Hoje vou escrever um pouco sobre o controle de fluxo. Para os leigos, o controle de fluxo consiste em dar uma sequência lógica ao programa, incluindo aí repetições de uma sequência de comandos e a chamada de funções para auxiliar na realização de uma tarefa.

Vou dar um exemplo simples: a sequência de Fibonacci.

Para os que ainda não a conhecem, tal sequência consiste em somar os dois números anteriores da sequência para obter o próximo valor. Os dois primeiros valores da sequência são 1 e 1. Sendo assim, a sequência segue como mostrado a seguir:

 1, 1, 2, 3, 5, 8, 13, 21, ....

Como poderíamos escrever um programa que mostra os 10 primeiros números da sequência de Fibonacci? Temos algumas opções. A primeira seria calcularmos de cabeça os números e apenas imprimí-los:

>>> fibonacci = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> print 'Os 10 primeiros números da sequência de Fibonacci são:', fibonacci

É uma solução bem simples, mas também muito limitada. O que acontece se agora desejarmos mostrar os 100 primeiros números da sequência? E os 1000 primeiros? Ficaria algo impraticável utilizando este método. Para resolver situações como esta existem os chamados "loops" na programação. Em python existem basicamente 2 tipos de "loops": os "while" e os "for". Vamos ver como poderíamos escrever os 100 primeiros números de fibonacci utilizando primeiramente um "while" e em seguida um "for":

>>> a = 1
>>> b = 1
>>> print "Os 100 primeiros números de Fibonacci são:", a, b
>>> num = 2
>>> while num < 100:
...    num += 1
...    print a + b,
...    a, b = b, a + b
... 

Deixe-me explicar o que ocorre no trecho de código acima, linha a linha:

a = 1

Primeiro número da sequência de Fibonacci


b = 1

Segundo número da sequência


print 'Os... são:', a, b

Imprime a string inicial e em seguida os 2 primeiros números, armazenados nas variáveis "a" e "b". Note que, ao separarmos os valores a serem impressos com uma vírgula, estes serão impressos na mesma linha.


num = 2

Como já mostramos os 2 primeiros números, inicializamos esta variável com o valor 2, indicando que temos mais 98 números a exibir.


while num < 100:

Aqui está o comando de controle da repetição. A sequência de comandos abaixo será executada enquanto o valor armazenado na variável "num" seja menor que 100. Outro fator que devemos levar em consideração é qual a sequência de comandos que será repetida. Na linguagem Python, este bloco de comandos será indicado pela identação do código, ou seja, pelo número de espaços em branco antes do primeiro caractere. Note também que, após digitar a linha com o comando "while" e pressionar a tecla "enter" o interpretador mostrará uma linha com "...", indicando que ele espera por um bloco de código. Assim sendo, para digitar o bloco de código que será repetido no loop, pressione a tecla "tab" no começo de cada linha, indicando a identação exigida para o bloco.


num += 1

Aqui nós incrementamos o valor da variável "num" em 1. Este comando produz o mesmo efeito que o comando: "num = num + 1". Note que o sinal de igual aqui informa atribuição e não a comparação de valores. Sendo assim, tal comando poderia ser traduzido para o Português como: atribua a variável "num" o valor da variável "num" acrescido do valor 1. Esta linha é importante pois sem ela nós estaríamos entrando num "loop infinito", mas isto eu vou explicar mais à frente.


print a + b,

Nesta linha nós exibimos o próximo valor da sequência, que nada mais é que a soma dos dois valores anteriores, armazenados nas variáveis "a" e "b".


a, b = b, a + b

Esta linha é o coração do algoritmo. E mostra também uma das vantagens da linguagem Python. Neste caso estamos efetuando duas atribuições em um único comando, e evitando o uso de uma variável temporária para a troca de valores. O que ocorre é que, do lado esquerdo do sinal de atribuição temos as variáveis que receberão os valores, os quais são calculados do lado direito da atribuição. sendo assim, a variável "a" receberá o valor da variável "b", e a variável "b" receberá o valor resultado da soma das variáveis "a" e "b". Para o leitor que já não é programador eu espero duas reações distintas para este comando. Ou você irá entender de cara que a operação faz todo o sentido ou ficará perdido sem saber o que realmente está acontecendo...

Deixe-me explicar de outra forma. O que o ocorre no fim das contas é que a operação será efetuada em duas etapas. Na primeira etapa, os valores do lado direito da atribuição são calculados. Numa segunda etapa a atribuição e efetivada. Sendo assim, na primeira iteração do loop, quando os valores de "a" e "b" são 1, teremos a seguinte sequência:

a, b = b, a + b
a, b = 1, 1 + 1
a, b = 1, 2
a = 1
b = 2

Perceba, então, que ao final da iteração teremos o valor do 2º termo da sequência armazenado na variável "a" e o valor do 3º termo armazenado na variável "b", possibilitando o cálculo do 4º termo na próxima iteração do loop. Se você ainda está em dúvida quanto ao funcionamento desta atribuição, podemos rescrevê-la da seguinte forma:

c = a + b
a = b
b = c

Para uns a primeira forma, com as duas atribuições numa só linha fará mais sentido, e para outros a segunda forma, com a utilização de uma terceira variável para armazenar o valor do próximo termo temporariamente é mais clara. Eu pessoalmente prefiro a primeira forma, numa única linha.

Bom, e como ficaria o código utilizando um "for" ao invés de um "while"? Para responder esta pergunta primeiro tenho que explicar como funciona o "for" na linguagem Python. E a solução não poderia ser mais simples: o comando "for" consiste em efetuar um "loop" sobre uma sequência de elementos de uma lista ou tupla. Ou seja, a variável do "loop" assumirá, a cada iteração, o próximo valor da lista. Vejamos como ficaria então o código:

>>> 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
... 

Perceba que o código é praticamente o mesmo. Apenas o "while" foi substituído pelo "for". Note ainda que não precisamos mais da linha "num += 1", pois o controle do loop é automático no "for". Outro fator que chama atenção é a utilização da função "range()". Esta função consiste simplesmente em construir uma lista, cujos valores serão os números inteiros a partir do zero até o valor passado como parâmetro menos 1:

>>> print range(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Ou seja, range(98) resulta em uma lista com os valores 0, 1, 2, ..., 97. A lista terá então 98 elementos. Outro fator que devemos ressaltar é que, apesar de não termos utilizado a variável "k" no código, ela irá assumir, a cada iteração do loop o valor associado na lista retornada pela função "range()", ou seja, na primeira iteração ela terá o valor 0, na segunda iteração terá o valor 1, e assim por diante, até que na última iteração ela terá o valor 97. O loop "for" termina quando se esgotarem os elementos da lista a ser percorrida.

É isso! Espero que vocês tenham entendido o funcionamento das estruturas "while" e "for" para a repetição de blocos de comandos. Até o próximo post!