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.
Sem comentários:
Enviar um comentário