Programação com Python: Yin & Yang

Muitos são os que advogam que vivemos num mundo pleno de opostos: ciências e humanidades é um exemplo paradigmático. E, mesmo dentro de cada categoria, ainda nos oferecem outras oposições: ciência versus engenharia ou arte versus design. Em qualquer das situações alguns ainda pretendem destacar o nobre (e.g., ciência) e o menos nobre (e.g., design). Nada de mais ilusório. Tudo se interliga e alimenta mutuamente.

A programação é um campo onde se juntam os quatro aspectos referidos: ciência e arte, engenharia e design. O que os une: a criatividade! Um excelente programa é aquele que é eficaz e eficiente, mas também belo, elegante e funcional. Esses aspectos sobressaem tanto mais quanto mais complexo for o problema que são supostos resolver. Dominar a complexidade é pois a tarefa principal do programador consciente. Isso só se consegue com rigor e disciplina, mas também com treino, exploração e intuição.

O exemplo que a seguir apresentamos é simples, servindo apenas para demonstrar algumas ideias básicas sobre como dominar a complexidade. O problema é o seguinte: quais os pares de números inteiros positivos, até um certo limite, que são primos entre si. Dos números dizem-se primos entre si se apenas admitirem como divisores comuns a unidade.

A estratégia será a seguinte:
a) gerar os pares de números até ao limite dado
b) para cada par: calcular os divisores de cada número, determinar a sua intersecção, e verificar se esta se reduz ao número 1.
c) acumular os resultados parciais

def primos_entre_si(limite):
    """Devole a lista dos pares de números que são primos entre so."""
    # Acumula resultado
    resultado = []
    # Gera pares a testar
    for i in range(limite):
        for j in range(limite):
            # testa
            if pes(i,j):
                resultado.append((i,j))
    # Devolve resultado
    return resultado

Este código traduz a nossa estratégia. É simples e claro. Mas mais do que isso: torna explícito algumas decisões. Por exemplo, que vamos acumular os resultados numa lista. Como princípio de projecto estas decisões devem ser tomadas o mais tarde possível. O ponto b) está concentrado numa chamada de função (pes). Mas nem tudo são rosas no código apresentado. Basta ter consciência de uma ineficiência: analisa pares de números idênticos, (n,n), ou repetidos, (n,m) e (m,n). Este problema pode ser tratado agora ou mais tarde, pois não interfere com o resto do programa. Este facto, poder deixar para mais tarde, é sempre um sinal de que o programa está a ser bem desenhado! Passemos então à a questão de saber se dois números são primos ente si (função pes). Aqui entra o conhecimento que temos sobre o domínio: dois números são primos entre si se o seu máximo divisor comum for 1.

def pes(m,n):
   """Primos entre si?"""
   return mdc(m,n) == 1

E agora, para concluir, o programa que calcula o máximo divisor comum. Uma vez mais vem em nosso auxílio o conhecimento que temos sobre o Algoritmo de Euclides:

def mdc(m,n):
    """Algoritmo de Euclides para o máximo divisor comum."""
    if n == 0:
        return m
    else:
        return mdc(n, m % n)

É recursivo! Mas podemos facilmente propor uma solução iterativa, se não estamos confortáveis com a recursividade:

def mdc_iter(m,n):
    while n > 0:
        m, n = n, m % n
    return m

Podemos também ser tentados a usar:

def mdc_iter_b(m,n):
    while n:
        m, n = n, m % n
    return m

A diferença entre estas duas últimas soluções é ténue. Mas não gostamos da última. O código fica menos claro e mais dependente do modo como a linguagem Python interpreta a condição Falso.

Por falar da linguagem, e do conhecimento que se tem sobre a linguagem, podíamos usar como solução para o cálculo do máximo divisor comum:

def mdc_py(m,n):
    from fractions import gcd
    return gcd(m,n)

A partir da versão 2.6 apareceu o novo tipo Fraction. Como sabemos, a simplificação de fracções passa por saber o máximo divisor comum. Por isso o módulo usa esta operação.

Regressemos ao programa principal para corrigir as ineficiências. Sabemos o que fazer para evitar repetições:

def primos_entre_si_b(limite):
    """Devolve a lista dos pares de números que são primos entre so."""
    # Acumula resultado
    resultado = []
    # Gera pares a testar
    for i in range(1,limite):
        for j in range(i+1,limite):
            # testa
            if pes(i,j):
                resultado.append((i,j))
    # Devolve resultado
    return resultado
 
def pes(m,n):
    """Primos entre si?"""
    return mdc(m,n) == 1

Foi só mexer no comando range dos dois ciclos for!

Juntemos as peças do puzzle:

# Primos entre si
 
def primos_entre_si(limite):
    """Devole a lista dos pares de números que são primos entre so."""
    # Acumula resultado
    resultado = []
    # Gera pares a testar
    for i in range(1,limite):
        for j in range(i+1,limite):
            # testa
            if pes(i,j):
                resultado.append((i,j))
    # Devolve resultado
    return resultado
 
def pes(m,n):
    """Primos entre si?"""
    return mdc(m,n) == 1
 
def mdc(m,n):
    from fractions import gcd
    return gcd(m,n)
   
if __name__ == '__main__':
    print primos_entre_si(100)

E podemos terminar. Ou será que não? Vamos ver o que acontece se eu coloco os números que são primos entre si numa grelha quadrada. Para ficar mais bonito vou usar o módulo cImage. Mas não quero mexer no que fiz: o cálculo e a visualização devem estar bem separados. A estratégia, uma vez mais neste caso, é simples:

a) criar uma imagem vazia com a dimensão do número máximo (do limite)
b) colorir os pixeis nas posições que correspondem a pares de números primos entre si:

from cImage import *
 
def mostra_pes(limite,lista_pares):
    janela = ImageWin('Primos',limite,limite)
    imagem = EmptyImage(limite,limite)
    pixel_vermelho = Pixel(255,0,0)
    for cord_x,cord_y in lista_pares:
        imagem.setPixel(cord_x,cord_y,pixel_vermelho)
        imagem.setPixel(cord_y,cord_x,pixel_vermelho)
    imagem.draw(janela)
    janela.exitOnClick()

Ligamos as duas partes:

def main(limite):
    lista = primos_entre_si(limite)
    mostra_pes(limite,lista)

Notar como restaurámos a matriz completa, incluindo os pares (x,y) e (y,x)). E executamos!

Que bela textura obtida a partir da matemática... olhem bem para a imagem e descubram o padrão. Há uma ordem escondida!!

Vimos que era importante ter conhecimento sobre o domínio mas também sobre a linguagem. Além disso, com rigor e disciplina, avançando passo a passo, não procurando resolver todo o problema de uma só vez, construímos uma solução simples, clara, eficiente, reutilizável. Arte, Design, Ciência e Engenharia.

(*) As imagens são do excelente livro: The Plenitude: Creativity, Innovation, and Making Stuff, Rich Gold, MIT Press, 2007.

Programação com Python

domingo, 17 de janeiro de 2010

Yin & Yang

Sem comentários:

Enviar um comentário

Bem Vindo

Acerca de mim

Pesquisar neste blogue

Arquivo do blogue

Seguidores