Programação com Python: novembro 2013

sábado, 23 de novembro de 2013

Pirâmides e mais pirâmides: reflexões sobre um teste

O segundo teste de IPRP era fácil. Deliberadamente fácil! As questões colocadas foram várias vezes discutidas nas aulas e, por isso, esperava que o vosso desempenho fosse melhor do que o do primeiro teste. Assim aconteceu! No entanto, ainda existe muita dificuldade em entender os enunciados e, mesmo depois de entendidos, em passar do problema à solução. Nas turmas TP3 e TP9, a primeira pergunta era básica, a segunda envolvia o padrão ciclo-acumulador e a terceira revisitava o nosso velho conhecido módulo turtle, associado a um problema muito discutido nas aulas em volta da ideia de programação por analogia. Neste post vou retomar este último aspecto. O código aqui apresentado já foi dado na sua generalidade, mas vamos também apresentar versões mais simples e uma questão nova.

Comecemos pela pirâmide normal.

Uma solução possível consiste em ir imprimindo linha a linha, uma sequência de quadrados de um dado comprimento. Precisamos de saber duas coisas: (1) onde colocar a tartaruga no início de cada linha e, (2) onde recolocar a tartaruga para desenhar um quadrado dentro de cada linha. Definimos dois pontos de referência (posx e posy) e é em relação a eles que resolvemos a primeira questão. A segunda questão resolve-se depois de verificar que cada quadrado numa dada linha deve avançar na coordenada xx de um valor igual ao lado. O nosso programa vai assim funcionar de acordo com o que mostramos no desenho seguinte.

Posto isto o código completo.

import turtle
     
def quadrado(posx, posy,lado):
    turtle.showturtle()
    # posiciona
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    # desenha
    for i in range(4):
        turtle.forward(lado)
        turtle.left(90)
    turtle.hideturtle()
     
# Normal
def pir_normal(n,posx, posy,lado):
    for i in range(1,n+1):
        # desenha linha i
        # --- posiciona
        turtle.penup()
        turtle.goto(posx + (n-i)*lado/2, posy + (n-i)*lado)
        turtle.pendown()      
        # --- desenha 
        for j in range(1,i+1):
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.setx(turtle.xcor()+lado)
    turtle.hideturtle()

Quando nos pedem para desenhar a pirâmide, mas agora invertida.

Não temos mais do que usar a mesma lógica de há pouco e que a figura seguinte explicitas.

Uma vez mais partimos de uma posição de referência para gerar as posições seguintes pela ordem da figura. Falta o código (agora só com a parte de desenho da pirâmide).

# Invertida
def pir_invertida(n,posx, posy,lado):
    for i in range(1,n+1):
        # desenha linha i
        # --- posiciona
        turtle.penup()
        turtle.goto(posx+ (n-i)*lado/2,posy-(n-i)*lado)
        turtle.pendown()      
        # --- desenha 
        for j in range(1,i+1):
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.setx(turtle.xcor()+lado)    
    turtle.hideturtle()  

Paremos um pouco para ver a diferença entre os dois programas. Um olhar atento verificará que só numa instrução, a que calcula os pontos 1,2,3 e 4, há uma pequena diferença, que faz toda a diferença: num caso o valor de vyy vai diminuindo e no outro vai aumentando. Apenas isto!!

Passemos agora ao exemplo do teste em que se pretende uma forma “voltada” para a direita.

A grande diferença em relação aos dois casos anteriores, é que uma solução fácil envolve olhar para a figura como colunas de quadrados de um dado tamanho. Daí que agora o que se vai mudar dentro do segundo ciclo for é o valor da coordenada yy. O resto, cálculo das posições em cada coluna é semelhante.

Vamos ao código.

def pir_direita(n,posx, posy,lado):
    for i in range(1,n+1):
        # desenha coluna i
        # -- posiciona
        turtle.penup()
        turtle.goto(posx+(n-i)*lado,posy + (n-i)*lado/2)
        turtle.pendown()      
        # -- desenha
        for j in range(1,i+1):            
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.sety(turtle.ycor()+lado)
    turtle.hideturtle() 

Mudemos agora a figura de modo a estar “voltada” para a esquerda.

O que precisamos, também aqui, é saber calcular os pontos de referência para cada coluna. A figura seguinte mostra quais são.

Ilustremos agora com o código.

# Esquerda
def pir_esquerda(n,posx, posy,lado):
    for i in range(1,n+1):
        # desenha coluna i
        # posiciona
        turtle.penup()
        turtle.goto(posx - (n-i)*lado,posy+(n-i)*lado/2)
        turtle.pendown()      
        # desenha
        for j in range(1,i+1):        
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.sety(turtle.ycor()+lado)
    turtle.hideturtle()

Mais uma vez qual a diferença entre os dois últimos programas? Apenas um sinal dentro de uma instrução, só que agora é no caso da coordenada xx.

Estes exemplos mostram como por vezes uma simples alteração resolve um problema diferente. As soluções propostas também são consequência do modo como olhamos para as figuras e entendemos tratar-se de uma sequência de linhas ou uma sequência de colunas. Mas não podíamos ter olhado para as figuras como sequências de “diagonais”? claro que sim. Isso interfere com a construção da solução? Um pouco. Admitamos que é o exemplo da figura voltada para a direita. Eis o resultado.

# Diagonal
def pir_diagonal(n,posx, posy,lado):
    for i in range(1,n+1):
        # desenha linha i
        # posiciona
        turtle.penup()
        turtle.goto(posx,posy-i*lado)
        turtle.pendown()      
        # desenha
        for j in range(i,n+1):           
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.penup()
            turtle.goto(turtle.xcor() + lado,turtle.ycor()-lado/2)
            turtle.pendown()
    turtle.hideturtle()

Tente identificar nesta solução quais os pontos que estão a ser calculados. Para ajudar à visão vamos incorporar cor na nossa pirâmide.

# Com cores
def pir_diagonal_cores(n,posx, posy,lado,cores):
    for i in range(1,n+1):
        # desenha linha i
        # posiciona
        turtle.penup()
        turtle.goto(posx,posy-i*lado)
        turtle.pendown()      
        # desenha
        turtle.fillcolor(cores[i%len(cores)])
        for j in range(i,n+1):
            turtle.begin_fill()
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.end_fill()
            turtle.penup()
            turtle.goto(turtle.xcor() + lado,turtle.ycor()-lado/2)
            turtle.pendown()
    turtle.hideturtle()

Executando o código obtemos a figura seguinte, em que as cores tornam visível a lógica utilizada na solução.

Mas será que ainda podemos mudar de perspectiva, nem linhas, nem colunas, nem diagonais? Neste caso ainda é. Uma das soluções apresentadas no teste faz isso mesmo: não há linhas, nem, colunas, nem diagonais, mas apenas quadrados.

# minimalista
def pir_minimalista(n, lado):
    for i in range(n):
        for j in range(n-i):
            quadrado(i*lado,j*lado + i*(lado/2),lado)

Trata-se de uma solução minimalista, sem ponto inicial de referência (não tem parâmetros posx e posy) e em que se calcular tantos pontos quantos os quadrados na pirâmide... Tente perceber como tal é feito.

E agora vamos descansar...

Teste #1 - Alunos 3ª Fase

Pergunta 1

Quais as três características comuns a todos os objectos?

Todos os objectos têm identidade (o seu endereço na memória), valor (aquilo que o objecto é e sobre o quase incidem as operações) e tipo (que identifica o conjunto de valores e de operações que podem ser feitas sobre um objecto do tipo).

Pergunta 2

Desenvolver um programa modular para desenhar a figura: A técnica é sempre a mesma: olhar e ver. Neste caso vemos três triângulos em posições diversas. Vamos então construir um programa para desenhar um triângulo, em função do lado e da posição.

def triangulo(posx, posy,lado):
    turtle.showturtle()
    turtle.penup()
    turtle.goto(posx,posy)
    turtle.pendown()
    for i in range(3):
        turtle.forward(lado)
        turtle.left(120)
    turtle.hideturtle()

O resto é trivial: desenhamos os triângulos em sequência. Só precisamos estar atentos à posição e à orientação.

def tri_tri(posx,posy,lado):
    turtle.penup()
    turtle.goto(posx,posy)
    turtle.pendown()
    # triangulo 1
    triangulo(turtle.xcor(),turtle.ycor(),lado)
    # triangulo 2
    turtle.setx(turtle.xcor() + lado)
    triangulo(turtle.xcor(),turtle.ycor(),lado)
    # triangulo 3
    turtle.left(120)
    turtle.forward(lado)
    turtle.right(120)
    triangulo(turtle.xcor(),turtle.ycor(),lado)

Claro que temo que admitir que alguém olhe para a figura e veja apenas dois triângulos: um exterior, maior, e outro interior, mais pequeno. A relação entre o comprimento dos respectivos lados é de um para dois. Com esta visão a solução é diferente:

def tri_tri_bis(posx, posy, lado):
    """ Faz desenho do triângulo exterior, seguido do desenho do triângulo interior."""
    # Posiciona
    turtle.showturtle()
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    # Desenha triângulo exterior
    triangulo(turtle.xcor(),turtle.ycor(),lado)
    # Posiciona no meio da base do triângulo maior com a orientação certa
    turtle.penup()
    turtle.setx(turtle.xcor()+lado/2)
    turtle.pendown()   
    turtle.left(60)
    # Desenha triangulo interior
    triangulo(turtle.xcor(),turtle.ycor(), lado/2)

Pergunta 3

Pedem-nos um programa para manipular uma cadeia de caracteres trocando os seus n primeiros caracteres com os seus últimos n caracteres. Além disso temos que verificar se a operação é possível. A operação não poderá ser feita se o valor de n for maior do que metade do tamanho da sequência!

def troca_cad(cadeia,n):
    if len(cadeia) < 2*n:
        print('Impossível')
        return -1
    return cadeia[-n:] + cadeia[n:-n] + cadeia[:n] 

A solução faz o teste da possibilidade e, caso seja possível, constrói a nova cadeia de caracteres: os n últimos vêm para o início (cadeia[-n:]), os n primeiros vão para o fim (cadeia[:n]), e no meio fica o restante (cadeia[n:-n]).

quinta-feira, 21 de novembro de 2013

Teste # 2 - TP9

Pergunta 1

Listas são sequências (existe ordem), heterogéneas (os elementos da lista podem de qualquer tipo), mutáveis (é possível alterar o seu valor sem alterar a sua identidade.

Pergunta 2

def g(x,n):
    """calcula o valor aproximado de uma função g(x) pela soma de n parcelas."""
    soma = 0
    for i in range(n):
        soma += (-1)**i * (x**i) / factorial(i)
    return soma

Para quem não soubesse que o factorial existe no módulo math:

def factorial(x):
    fact = 1
    for i in range(1,x+1):
        fact *= i
    return fact

Pergunta 3

Só tem que comparar com o que foi feito nas aulas e apareceu aqui no blogue...

import turtle
   
def quadrado(posx, posy,lado):
    turtle.showturtle()
    # posiciona
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    # desenha
    for i in range(4):
        turtle.forward(lado)
        turtle.left(90)
    turtle.hideturtle()
   
def pir_quadrados_ld(n,posx, posy,lado,cores):
    for i in range(n,0,-1):
        # desenha linha i
        # posiciona
        turtle.penup()
        turtle.sety(posy+ (n-i)*lado/2)
        turtle.pendown()      
        # desenha
        for j in range(1,i+1):
                                  
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.penup()
            turtle.sety(turtle.ycor()+lado)
            turtle.pendown()
        # muda de linha
        turtle.penup()
        turtle.goto(turtle.xcor()+lado,posy)
        turtle.pendown()
    turtle.hideturtle() 

Teste # 2 - TP3

Pergunta 1.
Tuplos são sequências (existe ordem), heterogéneas (os elementos do tuplo podem de qualquer tipo), imutáveis (não é possivel alterar o valor sem alterar a identidade.

Pergunta 2.

def f(x,n):
    """calcula o valor aproximado de f(x) por soma das n primeiras parcelas."""
    soma = 0
    for i in range(n):
        soma += (-1)**i * (x**(2*i)) / factorial(2*i)
    return soma

Era aceitável o uso da função factorial do módulo math. Para quem não soubesse da sua existência:

def factorial(x):
    fact = 1
    for i in range(1,x+1):
        fact *= i
    return fact

Pergunta 3.
Tratava-se de uma variante do que foi tantas vezes feito em aula e apareceu aqui no blogue.

import turtle
   
def quadrado(posx, posy,lado):
    turtle.showturtle()
    # posiciona
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    # desenha
    for i in range(4):
        turtle.forward(lado)
        turtle.left(90)
    turtle.hideturtle()
 
 
 
def pir_quadrados_le(n,posx, posy,lado,cores):
    for i in range(1,n+1):
        # desenha linha i
        # posiciona
        turtle.penup()
        turtle.sety(posy+(n-i)*lado/2)
        turtle.pendown()      
        # desenha
        for j in range(1,i+1):            
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.sety(turtle.ycor()+lado)
        # muda de linha
        turtle.penup()
        turtle.goto(turtle.xcor()+lado, posy)
        turtle.pendown()
    turtle.hideturtle()

segunda-feira, 18 de novembro de 2013

Amigos, Amigos,...

Um dos problemas do livro (problema 5.8) fala-nos de palavras amigas. Elas são amigas se o número de posições em que os respectivos caracteres difere for inferior a 10%. A propósito deste problema um aluno de IPRP enviou-me o seguinte email (de que reproduzo a parte substantiva).

“Para comparar caractere a caractere estou a utilizar um ciclo for: ....... for car in cad1: if cad1[car] != cad2[car] ........ ou seja vou comparar os carateres de cada cadeia na mesma posição e ver se eles são diferentes o python diz-me que o que esta dentro de cad1 e cad2 tem de ser um numero inteiro tendo o meu código dado erro.”

Qual é o problema? A resposta remete para os dois modos de percorrer um ciclo for: por posição ou por conteúdo. No caso do aluno ele está a fazer uma travessia do ciclo por conteúdo:

1.for car in cad1:

Depois no teste usa a operação de indexação, que permite aceder ao conteúdo mas por posição! Por isso o erro de dizer que o índice tem que ser um inteiro. A solução passa por fazer a travessia por posição:

1.for i in range(len(cad1)):

2. if cad1[i] != cad2[i]

Já agora o programa completo.

def amigas(cad_1, cad_2):
    """palavras que diferem em menos de 10% dizem-se amigas. Assume igual comprimento"""
    # Calcula distancia
    diferem = 0
    for i in range(len(cad_1)):
        if cad_1[i] != cad_2[i]:
            diferem += 1
    percentagem = diferem / len(cad_1)
    return percentagem < 0.1

Este programa funciona para qualquer tipo de sequências: cadeias de caracteres, tuplos e listas. O curioso da questão é que a versão do aluno podia correr sem dar erro caso se use um tuplo (ou uma lista) formado(a) por inteiros que correspondam a índices válidos dessas sequências! Se não acredita experimente:

def amigas(cad_1, cad_2):
    """palavras que diferem em menos de 10% dizem-se amigas. Assume igual comprimento"""
    # Calcula distancia
    diferem = 0
    for car in cad_1:
        if cad_1[car] != cad_2[car]:
            diferem += 1
    percentagem = diferem / len(cad_1)
    return percentagem < 0.1
 
if __name__ == '__main__':
    c1 = [0,1,2,3,4,5,6,7,8,9,0,1,3,3,4,5,6,7,8,9,0]
    c2 = [0,1,4,3,4,5,6,7,8,9,0,1,3,3,4,5,6,7,8,9,0]
    c3 = (0,1,2,3,4)
    c4 = (4,3,2,1,0)
    print(amigas(c1,c2))
    print(amigas(c3,c4))

Moral desta última parte da história: muitas vezes os programas funcionam para certos valores dos parâmetros reais e parece que está tudo bem... quando não está.

domingo, 17 de novembro de 2013

Olhar e ver (IV)

Hoje volto a um exemplo com o módulo turtle e com quadrados. Podem pensar que é obsessão minha, e se calhar é. Então agora é o seguinte: escrever um programa que nos permita desenhar um lindo tabuleiro, semelhante ao de xadrez (ou damas, ou,...), mas podendo ter qualquer dimensão.

A ideia é partir do zero (embora saiba que já fizemos muita coisa parecida,...). A tendência natural é começarmos a pensar como é que vou conseguir aquele efeito das cores alternadas? A minha resposta inicial a essa questão é: não vou fazer. Vou desenhar um tabuleiro com quadrados todos brancos. Depois se verá. E mais? Voltamos ao tema olhar e ver: para mim tenho linhas de quadrados, todas do mesmo comprimento!!! Então tomo a primeira decisão: vou desenhar linha a linha.

import turtle
 
def tabuleiro(n):
    """Desenha um tabuleiro tipo xadrez de ordem n."""
    for i in range(1,n+1):
        # desenha linha i
        pass
         
         
if __name__ == '__main__':
    tabuleiro(4)
    turtle.exitonclick()

Este programa fantástico não faz (quase) nada. Bem, sempre mostra uma janela em branco. Agora: o que significa desenhar uma linha? Bem, significa ... desenhar n quadrados!

import turtle
 
def tabuleiro(n):
    """Desenha um tabuleiro tipo xadrez de ordem n."""
    for i in range(1,n+1):
        # desenha linha i
        for j in range(1,n+1):
            #desenha quadrado j da linha i
            pass
         
         
if __name__ == '__main__':
    tabuleiro(4)
    turtle.exitonclick()

Mais um pequeno passo para o resultado final. E agora aparece um ponto importante: desenhar um quadrado. Precisamos dessa função. Mas não chega, pois os quadrados são desenhados em posições diferentes. E aqui temos que tomar outra decisão importante. Como controlar a posição de cada quadrado??? A ideia óbvia é fazer uma função que desenhe um quadrado numa dada posição, algo que já fizemos por diversas vezes.

def quadrado(posx,posy,lado):
    turtle.showturtle()
    turtle.penup()
    turtle.goto(posx,posy)
    turtle.pendown()    
    for i in range(4):
        turtle.forward(lado)
        turtle.left(90)
    turtle.hideturtle()

Agora, vamos completar o programa principal.

def tabuleiro(posx,posy,lado,n):
    """Desenha um tabuleiro tipo xadrez de ordem n."""
    #posição inicial
    turtle.penup()
    turtle.goto(posx,posy)
    turtle.pendown()     
    for i in range(1,n+1):
        # desenha linha i
        for j in range(1,n+1):
            #desenha quadrado j da linha i
            quadrado(turtle.xcor(), turtle.ycor(),lado)
            # -- posiciona para próximo
            turtle.setx(turtle.xcor()+lado)

Se executarmos este código o que acontece? É tudo desenhado na mesma linha!! Razão: não actualizamos as coordenadas para o início de cada linha. Vamos a isso.

def tabuleiro(posx,posy,lado,n):
    """Desenha um tabuleiro tipo xadrez de ordem n."""
    #posição inicial
    turtle.penup()
    turtle.goto(posx,posy)
    turtle.pendown()     
    for i in range(1,n+1):
        # desenha linha i
        for j in range(1,n+1):
            #desenha quadrado j da linha i
            quadrado(turtle.xcor(), turtle.ycor(),lado)
            # -- posiciona para próximo
            turtle.setx(turtle.xcor()+lado)
        # posição nova linha
        turtle.penup()
        turtle.goto(posx,turtle.ycor()+ lado)
        turtle.pendown()        

Notar que a posição inicial no eixo dos xx é sempre a mesma (isto não é uma pirâmide!!). Só a posição do eixo dos yy deve ser incrementada do valor do lado em cada ciclo. Executando o programa completo eis o nosso tabuleiro.

E pronto, já está! Mas, espere. E a cor?? Oops, já me esquecia. Bom vamos lá às linhas e alternar a cor entre o branco e o preto. Uma solução simples passa por associar a cor ao facto de a coluna ter um índice par ou ímpar. Mas temos que alterar também a definição do quadrado.

def quadrado(posx,posy,lado,cor):
    turtle.showturtle()
    turtle.penup()
    turtle.goto(posx,posy)
    turtle.pendown()
    turtle.fillcolor(cor)
    turtle.begin_fill()
    for i in range(4):
        turtle.forward(lado)
        turtle.left(90)
    turtle.end_fill()
    turtle.hideturtle()

Sabendo desenhar um quadrado colorido o resto já não nos incomoda muito.

def tabuleiro(posx,posy,lado,n):
    """Desenha um tabuleiro tipo xadrez de ordem n."""
    #posição inicial
    turtle.penup()
    turtle.goto(posx,posy)
    turtle.pendown()     
    for i in range(1,n+1):
        # desenha linha i
        for j in range(1,n+1):
            #desenha quadrado j da linha i
            if j % 2 == 0:
                # desenha quadrado j
                quadrado(turtle.xcor(),turtle.ycor(),lado,'white')
            else:
                quadrado(turtle.xcor(),turtle.ycor(),lado,'black')            
            # -- posiciona para próximo
            turtle.setx(turtle.xcor()+lado)
        # posição nova linha
        turtle.penup()
        turtle.goto(posx,turtle.ycor()+ lado)
        turtle.pendown()   

Executando o novo programa obtemos, para um tabuleiro 4X4:

Não é bem o que queremos, mas está lá perto! Não tenho dúvidas que todos já antecipavam este desfecho. Afinal, é preciso alternar a cor que começa em cada linha. Vamos então concluir o programa corrigindo essa deficiência. A solução é do tipo da anterior: em cada linha trocamos as cores. Eis o produto acabado:

import turtle
 
def quadrado(posx,posy,lado,cor):
    turtle.showturtle()
    turtle.penup()
    turtle.goto(posx,posy)
    turtle.pendown()
    turtle.fillcolor(cor)
    turtle.begin_fill()
    for i in range(4):
        turtle.forward(lado)
        turtle.left(90)
    turtle.end_fill()
    turtle.hideturtle()
     
def tabuleiro(posx,posy, lado,n,cor_1, cor_2):
    """Desenha um tabuleiro de xadrez."""
    for i in range(n):
        #desenha linha n
        # -- posiciona
        turtle.penup()
        turtle.goto(posx, i*lado)
        turtle.pendown()
        # --- escolhe cor
        if i % 2 == 0:
            primo = cor_1
            segundo = cor_2
        else:
            primo = cor_2
            segundo = cor_1
        # --- desenha
        for j in range(n):
            if j % 2 == 0:
                # desenha quadrado j
                quadrado(turtle.xcor(),turtle.ycor(),lado,primo)
            else:
                quadrado(turtle.xcor(),turtle.ycor(),lado,segundo)
            # posiciona
            turtle.penup()
            turtle.setx(turtle.xcor()+lado)
            turtle.pendown()
     
         
if __name__ == '__main__':
    tabuleiro(0,0,20,4, 'white','black')
    turtle.exitonclick()

E pronto. Agora até pode brincar usando um par de cores diversa. Mas não se esqueça da mensagem principal: se está com dificuldades em resolver o seu problema, tente resolver um semelhante mas mais simples. Depois vá melhorando a solução provisória até chegar à solução pretendida.

Altas rotações

Um dos problemas do livro (problema 6.8) é pedido um programa que permita rodar de 90 graus uma matriz representada por uma lista de listas: uma lista com as linhas sendo que estas são também elas listas com os elementos na respectiva coluna. Um aluno de IPRP resolveu, e bem, ser mais ambicioso e implementar um programa que permita rodar 90, 128 ou 270 graus. Enviou-me o programa que reproduzo.

import copy
def rodar(matriz, grau):
     
    nova_matriz = copy.deepcopy(matriz)
    for i in range(len(matriz)):
        for j in range(len(matriz[i])):
            if grau == 90:
                nova_matriz[j][len(matriz)-(i+1)] = matriz[i][j]
            elif grau == 180:    
                nova_matriz[len(matriz)-(i+1)][len(matriz)-(j+1)] = matriz[i][j]
            elif grau == 270:  
                nova_matriz[len(matriz) - (j+1)][i] = matriz[i][j]
    return nova_matriz
     
if __name__ == '__main__':
        print(rodar([[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20],[21,22,23,24,25]], 90))

Trata-se de um programa muito bom, denotando ter entendido bem onde estava a dificuldade maior. E a solução para o problema não era fácil de encontrar... Teve o cuidado de fazer uma cópia profunda, pois estamos a lidar com listas de listas, e calculou correctamente a relação entre as posições antigas e as novas. Mas no email que me mandou estava um pouco incomodado pois o programa só funcionava bem no caso das matrizes serem quadradas. Vamos então ajudá-lo a resolver este pequeno detalhe...

A chave para a solução consiste em perceber que o número de linhas e de colunas original pode mudar com a rotação. Por essa razão não podemos fabricar a nova matriz a partir da matriz inicial. Devemos criá-la de raíz. Uma possibilidade é criar a matriz com a nova estrutura e colocando no seu interior zeros. Com a estrutura depende do valor da rotação vamos começar por considerar o caso de uma rotação de 90º, na qual as linhas passam a colunas. Assim uma matriz mXn passa a nXm.

    nova_matriz = []
    for i in range(len(matriz[0])):
        nova_linha = []
        for j in range(len(matriz)):
            nova_linha.append(0)
        nova_matriz.append(nova_linha) 

Claro que já interiorizou o conceito de listas por compreensão pode chegar a uma solução mais curta:

1.nova_matriz = [[0 for j in range(len(matriz))] for i in range(len(matriz[0]))]

Estamos em condições de escrever um programa que faça rodar uma matriz de 90º.

def rodar_90(matriz):
    nova_matriz = [[0 for j in range(len(matriz))] for i in range(len(matriz[0]))]  # <<------ Aqui está o segredo :-)
    for linha in range(len(matriz)):
        for coluna in range(len(matriz[0])):
            nova_matriz[coluna][len(matriz) - 1 - linha] = matriz[linha][coluna]
    return nova_matriz

Mas ainda falta o resto, 180º e 270º. Vamos a isso. Como a nossa solução autonomizou as rotações, vamos ter um programa principal como este:

def rodar(matriz,grau):
    if grau == 90:
        return rodar_90(matriz)
    elif grau == 180:
        return rodar_180(matriz)
    elif grau == 270:
        return rodar_270(matriz)
    else:
        print('Oops, isso ainda não sei fazer...!')
        return -1

O resto da solução é trivial: rodar 180 é o mesmo que rodar duas vezes 90; rodar 270 é o mesmo que rodar três vezes 90 ou rodar uma vez 180 e outra 90. Certo?

def rodar_180(matriz):
    return rodar_90(rodar_90(matriz))
 
def rodar_270(matriz):
    return rodar_90(rodar_180(matriz))

Moral da história. Partimos de uma boa solução mas que resolve apenas um caso especial do problema (matrizes quadradas), e identificámos onde estava o problema; resolvemos para um caso (90) e usamos essa solução para o resto (180, 270); pelo caminho ainda deparámos com o problema causado pela mutabilidade e partilha de memória (modo como criámos a nova matriz); e ainda apresentámos uma solução baseada em listas por compreensão. Mas o essencial da mensagem é: perante um problema difícil, tente resolver uma versão mais simples, decomponha esse problema em sub-problemas e depois generalize a solução para chegar ao resultado pretendido.

segunda-feira, 11 de novembro de 2013

Ai, é tão parecido com...(III)

Regressemos às nossas pirâmides. Recordo aqui o programa para desenhar uma pirâmide de quadrados.

import turtle
 
def pir_quadrados(n,posx, posy,lado):
    for i in range(1,n+1):
        # desenha linha i
        # posiciona
        turtle.penup()
        turtle.setx(posx+(n-i)*lado/2)
        turtle.pendown()      
        # desenha
        for j in range(1,i+1):
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.setx(turtle.xcor()+lado)
        # muda de linha
        turtle.penup()
        turtle.goto(posx,turtle.ycor()-lado)
        turtle.pendown()
    turtle.hideturtle()
     
def quadrado(posx, posy,lado):
    turtle.showturtle()
    # posicioan
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    # desenha
    for i in range(4):
        turtle.forward(lado)
        turtle.left(90)
    turtle.hideturtle()

Quando executado para um pirâmide de tamanho 4, com 20 pixeis de lado obtemos:

Admitamos que o problema agora é semelhante com a diferença da pirâmide dever aparecer... invertida.

Como fazer? olhando para o código acima percebemos que ele está feito para que na linha 1 seja desenhado 1 quadrado, na linha 2, 2 quadrados e, de um modo geral, na linha i sejam desenhados i quadrados. Este procedimento é controlado pelos dois ciclos for. O mais externo identifica a linha i e o mais interno garante que são desenhados i quadrados. Mas agora o que pretendemos é que na linha 1 sejam desenhados n, na 2 (n-1), ..., e na n apenas 1. Se não queremos mexer muito no código basta o ciclo exterior comece por identificar a linha n, depois a (n-1) , etc. Com esta única alteração o problema fica resolvido!

def pir_quadrados_inv(n,posx, posy,lado):
    for i in range(n,0,-1): # <-- só alterámos aqui!!
        # desenha linha i
        # posiciona
        turtle.penup()
        turtle.setx(posx+ (n-i)*lado/2)
        turtle.pendown()      
        # desenha
        for j in range(1,i+1):
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.setx(turtle.xcor()+lado)
        # muda de linha
        turtle.penup()
        turtle.goto(posx,turtle.ycor()-lado)
        turtle.pendown()
    turtle.hideturtle() 

Fantástico não é? Mas suponhamos que alguém tem algo contra quadrados e prefere triângulos?? Bem, temos que ser capazes de desenhar triângulos, certo? Vamos a isso.

def triangulo(posx, posy, lado):
    turtle.showturtle()
    # posicioan
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    # desenha
    for i in range(3):
        turtle.forward(lado)
        turtle.left(120)
    turtle.hideturtle()

E agora? Será que substituir o uso da definição quadrado pela definição de triângulo resolve a questão?

def pir_triangulos_inv(n,posx, posy,lado):
    for i in range(n,0,-1):
        # desenha linha i
        # posiciona
        turtle.penup()
        turtle.setx(posx+ (n-i)*lado/2)
        turtle.pendown()      
        # desenha
        for j in range(1,i+1):
            triangulo(turtle.xcor(),turtle.ycor(), lado) # <-- única mudança!!
            turtle.setx(turtle.xcor()+lado)
        # muda de linha
        turtle.penup()
        turtle.goto(posx,turtle.ycor()-lado)
        turtle.pendown()
    turtle.hideturtle() 

Então e não é que resolve?

Mas porque funciona? É facil de perceber que a estrutura global é a mesma. Por outro lado, o posicionamento de cada triângulo obedece à mesma regra do caso dos quadrados. Entusiasmados, passamos a hexágonos:

def pir_hexagonos_inv(n,posx, posy,lado):
    for i in range(n,0,-1):
        # desenha linha i
        # posiciona
        turtle.penup()
        turtle.setx(posx+ (n-i)*lado/2)
        turtle.pendown()      
        # desenha
        for j in range(1,i+1):
            hexagono(turtle.xcor(),turtle.ycor(), lado) # <-- única mudança!
            turtle.setx(turtle.xcor()+lado)
        # muda de linha
        turtle.penup()
        turtle.goto(posx,turtle.ycor()-lado)
        turtle.pendown()
    turtle.hideturtle() 

Quando executamos o código, a surpresa. Não funciona:

A razão está no modo como vamos avançando os hexágonos em cada linha e na forma como baixamos de linha. Então quais os valores certos? olhemos para a figura:

Ela diz-nos que dentro de cada linha temos que avançar x do valor do lado mais duas vezes o valor de B. Quando mudamos de linha temos que alterar y de um valor igual a A. Mas o que são A e B? Um pouco de geometria diz-nos que A = 2* coseno(30) e B = coseno(60). Feitas as contas, chegamos a A= 1.732* lado e B = 0.5 * lado. Daí a nossa solução final: def pir_hexagonos(n,posx, posy,lado): for i in range(n,0,-1): # desenha linha i # posiciona turtle.penup() turtle.setx(posx+(n-i)*lado) turtle.pendown() # desenha for j in range(1,i+1): hexagono(turtle.xcor(),turtle.ycor(), lado) turtle.penup() turtle.setx(turtle.xcor()+2*lado) # <-- Novidade! turtle.pendown() # muda de linha turtle.penup() turtle.goto(posx,turtle.ycor()-1.732*lado) # <-- Novidade! turtle.pendown() turtle.hideturtle() Ver para crer:

Moral da história. Existem padrões de programação. Para uma dada classe de problemas semelhantes as soluções também elas são semelhantes. De qualquer modo temos que ter cuidado com generalizações apressadas e identificar bem o que faz a essência de uma solução. Neste caso o modo como se posiciona a tartaruga para uma linha e dentro de uma dada linha.

Agora, pode tentar com ... pentágonos??

domingo, 10 de novembro de 2013

Sequências de Langford: padrões e analogias

Considere uma sequência de tamanho 2*n formada por duas cópias dos inteiros de 1 a n. Dito de outro modo, considere uma permutação dos números {1,1,2,2,3,3,..., n,n}. A sequência diz-se de Langford, de ordem n, designada por L(n), se as ocorrências de cada par do número k tiver a separá-los exactamente k inteiros. Por exemplo, (2,3,1,2,1,3) é uma sequência de Langford de ordem 3, (4,1,3,1,2,4,3,2) é uma sequência de Langford de ordem 4, (1, 2, 1, 6, 2, 8, 11, 9, 10, 3, 6, 4, 7, 3, 8, 5, 4, 9, 11, 10, 7, 5) é uma sequência de ordem 11. São várias as questões que se podem colocar sobre estas sequências :

existência: para todo o n existe pelo menos uma sequência de Langford?
construção: se existe L(n), como obtê-la?
enumeração: quantas sequências de ordem n existem?
geração: as sequências de ordem n podem ser geradas sistematicamente?
optimização: quais as soluções que maximizam (ou minimizam) f(L(n)) para uma dada função objectivo f?

O problema de Langford consiste em encontrar uma sequência de Langford para um dado n. Trata-se na realidade de um caso especial do problema combinatório mais geral conhecido por problema da cobertura exacta. Mas quem é que se pode interessar por isto? Bem, para além do prazer de brincar com a matemática, existem exemplos de aplicação concreta: resolver um problema do Sodoku é resolver um problema de cobertura exacta. O problema da cobertura exacta é um problema combinatório de elevada complexidade (*), sendo que para valores elevados de n não existe um computador suficientemente rápido, nem hoje nem amanhã, que o resolva em tempo útil. Mas nós não vamos discutir estas questões. Vamos começar por criar um programa simples que nos diz, para todo o n, se uma dada sequência é de Langford ou não. Vamos admitir que para um dado n a sequência tem comprimento de 2*n e cada inteiro entre 1 e n ocorre exactamente duas vezes. Vamos a isso.

Como resolver o problema? Vamos pensar num caso mais simples: como saber se um dado k tem k inteiros entre as suas duas ocorrências? Bem, basta encontrar as posições entre as duas ocorrências e contar as posições entre ambas. E para todos? Também não é difícil: repetir para todos inteiros no intervalo [1,n]. Asim vamos ter um ciclo repetido n vezes que faz a verificação da condição. Claro que se existir um número que não verifique a condição podemos logo abandonar o programa pois já sabemos a resposta.

def testa_langford(seq):
    """Verifica se seq é uma sequência de Langford."""
    ordem = len(seq)//2
    for k in range(1,ordem+1):
        indice_1 = seq.index(k)
        indice_2 = seq.index(k,indice_1+1,len(seq))
        if (indice_2 - indice_1 - 1) != k:
            return False
    return True

Nesta solução admitimos como foi dito que a sequência tem comprimento igual a 2*n e cada inteiro entre 1 e n ocorre exactamente duas vezes. Mas para ter a certeza disso não há como testar um sequência qualquer. Como fazer? Só temos que testar a existência de cada número k duas vezes, para o que recorremos ao método count para sequências:

def candidata(seq):
    “””Pode ser sequência de Langford?”””
    n = len(seq) // 2
    for k in range(1,n+1):
        if seq.count(k) != 2:
            return False
    return True

Olhando para este programa e para o anterior o que notamos? Seguem exactamente o mesmo padrão: um ciclo que gera os números de 1 a n de modo ordenado e um teste para verificar a condição que nos pode levar à rejeição da hipótese. Correndo o programa e ficamos todos satisfeitos... ou talvez não. Teste com o caso (1,2,1,2,3). Vai dizer-lhe que é uma candidata quando é óbvio que nunca pode ser: tem um comprimento ímpar! Nada que não se possa resolver de modo trivial:

def candidata(seq):
    “””Pode ser sequência de Langford?”””
    if len(seq) % 2 != 0:
        return False
 
    n = len(seq) // 2
    for k in range(1,n+1):
        if seq.count(k) != 2:
            return False
    return True

Para concluir vamos pensar num programa que nos indica qual a distância a que uma dada sequência se encontra de uma verdadeira sequência de Langford. O modo como pretendemos fazer isso consistirá em determinar quantos números, no intervalo de 1 a n, não satisfazem a sua condição. Informaticamente já sabemos que precisamos de um ciclo para percorrer todos os números e de um contador para contar os casos em que a condição não é satisfeita. Trata-se pois de mais um exemplo do padrão ciclo - acumulador, em que este último tem funções de contador. Pensando um pouco chegamos à conclusão que este problema é análogo ao primeiro. A diferença está em que não abandonamos o programa mal se saiba que não pode ser uma sequência de Langford, antes continuamos actualizado um contador.

def qualidade(seq):
    """Conta o número de números que satisfaz a condição e Langford."""
    ordem = len(seq)//2
    conta = 0
    for i in range(1,ordem+1):
        indice_1 = seq.index(i)
        indice_2 = seq.index(i,indice_1+1,len(seq))
        if (indice_2 - indice_1 - 1) != i:
            conta += 1
    return conta

Se ao correr o programa o resultado for 0, então sabemos que é uma sequência de Langford.

(*) Tecnicamente diz-se que é um problema NP-Completo.

sexta-feira, 8 de novembro de 2013

Aleatoriedades (I)

Cada vez mais tomamos consciência que muito dos acontecimentos que nos rodeiam têm uma natureza probabilística. Os valores possíveis para um evento aleatório dá origem a uma distribuição de probabilidades. Existem vários tipos de distribuições, e.g., normal, uniforme, poisson. Para podermos simular esses processos precisamos de ser capazes amostrar essas distribuições. Em Python o módulo random ajuda-nos nessa tarefa. Por exemplo, o método randint gera um inteiro dentro de um intervalo de acordo com uma distribuição uniforme. Já o método random (não confundir com o nome do módulo...) permite obter um real no intervalo [0,1), ainda de acordo com uma distribuição uniforme. Na realidade os números são pseudo-aleatórios mas isso é outra história. Vamos olhar para algumas aplicações muito simples.

Admitamos que nos pedem para gerar uma sequência com n números inteiros todos no intervalo [a,b]. Em função do que sabemos, o mais natural é gerar os números um a um e ir guardando o resultado no único contentor que já conhecemos (em breve, tomaremos conhecimento com outros...). Claramente, do que foi dito estamos perante um padrão de programação do tipo ciclo - acumulador. Daí o código:

def gera_tuplos_n(n,a,b):
    """Gera um tuplo com n inteiros entre a e b."""
    res = () # <-- o acumulador
    for i in range(n): # <-- o ciclo
        # gera número
        num = random.randint(a,b)
        # guarda número
        res += (num,)
    return res

Admitamos que o enunciado é ligeiramente alterado impondo que os números devem ser todos distintos. Aparentemente a solução é fácil e envolve mudar ligeiramente o código anterior por forma que dentro do ciclo, depois de gerar um elemento, se teste se ele já pertence ou não à nossa sequência, só o introduzindo no caso de não pertencer.

def gera_tuplos_n(n,a,b):
    """Gera um tuplo com n inteiros distintos entre a e b."""
    res = ()
    for i in range(n):
        num = random.randint(a,b)
        if num not in res:
             res += (num,)
    return res

Mas se executarmos o código temos uma surpresa: o tuplo tem em geral menos elementos do que os pedidos. Um minuto de reflexão permite identificar o problema: quer o elemento seja introduzido ou não no tuplo, o contador interno do ciclo for é sempre incrementado. Solução? Simples: passar para um ciclo while que é executado enquanto não tivermos os n elementos desejados:

def gera_tuplos_n_diff(n,a,b):
    """Gera um tuplo com n inteiros entre a e b, todos diferentes"""
    res = ()
    i = 0
    while i < n:
        num = random.randint(a,b)
        if num not in res:
            res += (num,)
            i += 1
    return res

E já está. Mesmo sendo um programa muito simples ainda há lugar a pequenas melhorias. Como dissemos o ciclo é executado enquanto não tivermos n elementos no tuplo. então porque não usar o comprimento do tuplo como critério de saída???

def gera_tuplos_n_diff(n,a,b):
    """Gera um tuplo com n inteiros entre a e b, todos diferentes"""
    res = ()
    while len(res) < n:
        num = random.randint(a,b)
        if num not in res:
            res += (num,)
    return res

Agora sim, estamos satisfeitos. Vamos experimentar, por exemplo com:

1.print(gera_tuplos_n_diff(10, 5,10))

Mas algo de estranho acontece: o programa não apresenta nenhum resultado! Pensando de novo, lá encontramos a razão: queremos dez números distintos quando no intervalo entre 5 e 10 só existem 6!! Nada que não se possa precaver por recurso a uma asserção:

def gera_tuplos_n_diff_b(n,a,b):
    """Gera um tuplo com n inteiros entre a e b, todos diferentes"""
    assert n <= (b-a+1),'Um...números a menos para o tamanho do tuplo.'
    res = ()
    while len(res) < n:
        num = random.randint(a,b)
        if num not in res:
            res += (num,)
    return res

Já estou a ouvir alguns de vocês: mas porque é tanta trabalheira, não bastava.... Sim claro, temos um método que nos permite gerar os n números distintos só com uma instrução:

def gera_tuplos_n_diff(n, a,b):
    """Gera um tuplo com n inteiros entre a e b, todos diferentes"""
    assert n <= (b-a+1),'Um...números a menos para o tamanho do tuplo.'
    return random.sample(range(a,b+1),n)

Mas se executar o programa verá que o contentor usado não é um tuplo, mas sim uma lista de que ainda não falámos. Fica a informação...

Já agora: se em vez de inteiros fossem números reais então os métodos a usar seriam o random, para o intervalo [0,1), ou o uniform, para o intervalo [a,b]. Mas o resto não se alterava.

E agora sim, deste já nos livrámos.

Vamos passar para outro tipo de problema. E se em vez de números nos pedem para fabricar aleatoriamente uma sequência de ADN. Como sabemos este tipo de sequência pode ser representado por uma cadeia de caracteres em que os valores possíveis para cada posição é uma de entre as quatro bases, ‘A, ‘T’, ‘C’, e ‘G’. Mas tirando esse aspecto o problema do ponto de vista informático segue o mesmo padrão do problema anterior: ciclo + acumulador. A única questão a resolver prende-se com a geração das bases. Mas para isso temos o método choice!

def gera_adn(n):
    """Gera uma cadeia de ADN de comprimento n."""
    adn = ''
    for i in range(n):
        base = random.choice('ATCG')
        adn += base
    return adn

Simples, não é? E se nos disserem que a probabilidade da Adenina (‘A’) é dupla das restantes bases? Não tem problema: incluímos duas ocorrências de ‘A’ na cadeia que o método choice vai usar para a escolha:

def gera_adn(n):
    """Gera uma cadeia de ADN de comprimento n."""
    adn = ''
    for i in range(n):
        base = random.choice('AATCG') <-- dois As!!
        adn += base
    return adn

Por fim pensemos numa tartaruga muito libertária que adora passear ao acaso, podendo deslocar-se apenas para norte (‘N’), sul (‘S’), este (‘E’) ou oeste (‘O’). Como gerar um percurso que a tartaruga tem que percorrer? Bom, não me diga que ainda tem dúvidas... ciclo + acumulador!

def gera_tarta(n):
    """Gera uma sequência de n movimentos aleatórios de uma tartaruga."""
    tarta = ''
    for i in range(n):
        passo = random.choice('NSEO')
        tarta += passo
    return tarta

E já agora vamos passear!

def passeio_tarta(posx, posy, tam_passo,cor,caminho):
    """Simula o caminha da tartaruga num espaço reticulado."""
    # inicializa
    turtle.showturtle()
    turtle.pencolor(cor)
    turtle.fillcolor(cor)
    turtle.shape('turtle')
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    # passeia
    for comando in caminho:
        if comando == 'N':
            turtle.setheading(90)
            turtle.forward(tam_passo)
        elif comando == 'S':
            turtle.setheading(270)
            turtle.forward(tam_passo) 
        elif comando == 'E':
            turtle.setheading(0)
            turtle.forward(tam_passo) 
        elif comando == 'O':
            turtle.setheading(180)
            turtle.forward(tam_passo)
        else:
            # Ignorar
            continue
    turtle.hideturtle()
     
def main_tarta(n, posx,posy,tam_passo,cor):
    caminho = gera_tarta(n)
    passeio_tarta(posx,posy,tam_passo,cor,caminho)

O nosso programa main decompõe o problema em dois sub-problemas. Primeiro gera o caminho e depois é que simula o passeio. Simular o passeio envolve simplesmente um ciclo que interpreta cada letra do caminho como um comando a executar.

Podemos agora brincar um pouco. Por exemplo, admitir que a nossa tartaruga privilegia ir para oeste e para norte:

def gera_tarta(n):
    """Gera uma sequência de n movimentos aleatórios de uma tartaruga."""
    tarta = ''
    for i in range(n):
        passo = random.choice('NNNSEOOO')
        tarta += passo
    return tarta

Ou então que o comprimento do passo é maior para norte e para este e menor para sul e para oeste.

def passeio_tarta(posx, posy, tam_passo,cor,caminho):
    """Simula o caminha da tartaruga num espaço reticulado."""
    # inicializa
    turtle.showturtle()
    turtle.pencolor(cor)
    turtle.fillcolor(cor)
    turtle.shape('turtle')
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    # passeia
    for comando in caminho:
        if comando == 'N':
            turtle.setheading(90)
            turtle.forward(tam_passo)
        elif comando == 'S':
            turtle.setheading(270)
            turtle.forward(0.5*tam_passo) 
        elif comando == 'E':
            turtle.setheading(0)
            turtle.forward(tam_passo) 
        elif comando == 'O':
            turtle.setheading(180)
            turtle.forward(0.5*tam_passo)
        else:
            # Ignorar
            continue
    turtle.hideturtle()

Ou ainda podemos colorir o passo em função da orientação e admitir comandos inválidos (no caso 'X').

def gera_tarta(n):
    """Gera uma sequência de n movimentos aleatórios de uma tartaruga."""
    tarta = ''
    for i in range(n):
        passo = random.choice('NNNSXEOOO') # <-- um X
        tarta += passo
    return tarta
 
def passeio_tarta(posx, posy, tam_passo,cor,caminho):
    """Simula o caminha da tartaruga num espaço reticulado."""
    # inicializa
    turtle.showturtle()
    turtle.fillcolor(cor)
    turtle.shape('turtle')
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    # passeia
    for comando in caminho:
        if comando == 'N':
            turtle.pencolor('red')
            turtle.setheading(90)
            turtle.forward(tam_passo)
        elif comando == 'S':
            turtle.pencolor('green')
            turtle.setheading(270)
            turtle.forward(tam_passo) 
        elif comando == 'E':
            turtle.pencolor('blue')
            turtle.setheading(0)
            turtle.forward(tam_passo) 
        elif comando == 'O':
            turtle.pencolor('yellow')
            turtle.setheading(180)
            turtle.forward(tam_passo)
        else:
            # Ignorar
            turtle.pencolor('black')
            turtle.dot(6)
            continue
    turtle.hideturtle()

E mais todas as variantes que quiser imaginar...

quarta-feira, 6 de novembro de 2013

Ai, que é tão parecido com... (II)

Este blogue dá suporte à disciplina de IPRP e, naturalmente, preocupa-se com discutir questões de programação, a um nível introdutório, e com métodos de resolução de problemas. Este último aspecto tem contornos gerais (já discutidos num post anterior de Outubro de 2009, intitulado “Resolução de Problemas”), mas devemos procurar saber como é que os princípios genéricos de resolução de problemas se pode aplicar à programação. Neste post vou discorrer um pouco sobre como programar por analogia. Para tal vou socorrer-me do problema da pirâmide de números já abordado, cujo programa aqui retomo.

def piramide(n):
    for i in range(1, n+1):
        # posiciona
        print(4*(n-i)* ' ', end= ' ')
        # desenha descendente
        for j in range(i,0,-1):
            print('%3d' % j , end = ' ')
            # desenha ascendente
        for j in range(2,i+1):
            print('%3d' % j, end=' ')
        # muda de linha
        print()

Quando executado para n igual a 4 obtemos uma bela pirâmide:

Vamos supor agora que me pedem um outro tipo de pirâmide:

A pergunta a que temos que responder, uma vez recordados de já ter visto um problema parecido é: qual a diferença? Olhando para as suas imagens torna-se óbvio que não há diferença na forma mas apenas no conteúdo: os números são diferentes e para além disso temos uma sequência ascendente primeiro e depois uma descendente. Vejamos esta última questão primeiro. Invertemos a ordem dos dois ciclos interiores e adaptamos o range à nova situação.

def piramide_2(n):
    for i in range(1, n+1):
        # posiciona
        print(4*(n-i)* ' ', end= ' ')
        # desenha ascendente
        for j in range(1,i+1):
            print('%3d' % j, end=' ')        
        # desenha descendente
        for j in range(i-1,0,-1):
            print('%3d' % j , end = ' ')
        # muda de linha
        print()

Correndo o programa, de novo para n igual a 4, obtemos:

Já não está muito mal. Falta apenas a questão dos números. Se notarmos que a sequência envolve potências de 2, chegamos facilmente à solução por alteração do que é impresso.

def piramide_2(n):
    for i in range(1, n+1):
        # posiciona
        print(4*(n-i)* ' ', end= ' ')
        # desenha ascendente
        for j in range(1,i+1):
            print('%3d' % 2**(j-1), end=' ')        
        # desenha descendente
        for j in range(i-1,0,-1):
            print('%3d' %  2**(j-1) , end = ' ')
        # muda de linha
        print()

Não foi difícil passar de uma solução a outra pois o domínio era o mesmo. Mas admitamos que nos pedem para desenhar outro tipo de pirâmide: uma pirâmide de quadrados como a da figura (mas podendo ter qualquer altura,....):

Uma vez mais a pergunta: que diferença para os casos anteriores? Também aqui a forma é a mesma, alterando-se apenas o conteúdo. Agora cada linha é formada por uma sequência de quadrados idênticos. Não há valores que sobem e descem de acordo com uma regra, não, é tudo igual. Daqui resulta a mesma estrutura de solução, formada por um ciclo for e em que no seu interior temos que desenhar uma linha seguido de uma mudança de linha. O desenho da linha tem dois aspectos: ir para a posição inicial e desenhar a linha. Neste caso há apenas um ciclo for interior.

def pir_quadrados(n,posx, posy,lado):
    for i in range(1, n+1):
        # desenha linha i
        # -- (1) posiciona              
        # -- (2) desenha
        for j in range(1,i+1):
     pass
        # muda de linha
    turtle.hideturtle()

Este esqueleto de solução já tem alguns elementos que derivam da opção por turtle para desenhar os quadrados e também que os parâmetros formais da definição envolvem para além do número de linhas também a posição de referência para o desenho da pirâmide e o tamanho do lado do quadrado. Deixemos de lado por agora na questão da posição e da mudança de linha e fixemo-nos na questão do desenho. Na linha i temos que desenhar i quadrados. Não precisamos de muito tempo para perceber que depois de desenhar um quadrado temos que avançar uma distância igual ao comprimento do lado para desenhar o quadrado seguinte. Logo.

def pir_quadrados(n,posx, posy,lado):
    for i in range(1, n+1):
        # desenha linha i
        # posiciona
        # desenha
        for j in range(1,i+1):
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.setx(turtle.xcor()+lado)
        # muda de linha
    turtle.hideturtle()

O código depende de uma definição auxiliar para desenhar cada quadrado individualmente. É essa definição que usada o número de vezes ditado pela ordem da linha. É um código que já encontrámos por diversas vezes no passado:

def quadrado(posx, posy,lado):
    turtle.showturtle()
    # posicioan
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    # desenha
    for i in range(4):
        turtle.forward(lado)
        turtle.left(90)
    turtle.hideturtle()

E como mudamos de linha??? Bem, temos que nos posicionar “à esquerda”, na posição de referência para o eixo dos xx e baixar o valor no eixo dos yy de uma quantidade igual ao lado.

def pir_quadrados(n,posx, posy,lado):
    for i in range(1, n+1):
        # desenha linha i
        # posiciona
        # desenha
        for j in range(1,i+1):
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.setx(turtle.xcor()+lado)
        # muda de linha
        turtle.penup()
        turtle.goto(posx,turtle.ycor()-lado)
        turtle.pendown()
    turtle.hideturtle()

Notar que subtraímos no caso do y pois existe a vontade de fazer crescer a pirâmide para baixo. Vamos executar o programa.

Como era de prever não vemos nenhuma pirâmide pois não resolvemos o problema do posicionamento inicial em cada linha. Mas não é muito diferente do caso das pirâmides dos números, só que aqui temos que fazer avançar ao longo do eixo dos xx e do eixo dos yy. Mas quanto? No caso do y não é difícil: para a linha i temos ir para (n-i)*lado - posy. Se olharmos para a figura de novo vemos que numa dada linha o deslocamento ao longo do eixo dos xx em relação à anterior é de metade do lado. Daí o resultado final:

def pir_quadrados(n,posx, posy,lado):
    for i in range(1, n+1):
        # desenha linha i
        # posiciona
        turtle.penup()
        turtle.goto(posx+(n-i)*lado/2, (n-i)*lado - posy)
        turtle.pendown()      
        # desenha
        for j in range(1,i+1):
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.setx(turtle.xcor()+lado)
        # muda de linha
        turtle.penup()
        turtle.goto(posx,turtle.ycor()-lado)
        turtle.pendown()
    turtle.hideturtle()

Et voilá!

Mas, esperem. Quando eu mudo de linha o valor de y é actualizado, certo? Correcto. então porque é que no posicionamento me estou a preocupar em redefinir esse valor? Faz sentido!

def pir_quadrados_2(n,posx, posy,lado):
    for i in range(1,n+1):
        # desenha linha i
        # posiciona
        turtle.penup()
        turtle.setx(posx+(n-i)*lado/2)
        turtle.pendown()      
        # desenha
        for j in range(1,i+1):
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.setx(turtle.xcor()+lado)
        # muda de linha
        turtle.penup()
        turtle.goto(posx,turtle.ycor()-lado)
        turtle.pendown()
    turtle.hideturtle()

Basta passar de um goto para um setx. Uff!

Mas, se eu simplifico o posicionamento porque faço isso nsa mudança de linha... não podia fazer ao contrário, ou seja, manter a actualização de y no posicionamento e simplificar na mudança de linha? Tem lógica e está bem observado.

def pir_quadrados_3(n,posx, posy,lado):
    for i in range(1,n+1):
        # desenha linha i
        # posiciona
        turtle.penup()
        turtle.goto(posx+(n-i)*lado/2, (n-i)*lado - posy)
        turtle.pendown()      
        # desenha
        for j in range(1,i+1):
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.setx(turtle.xcor()+lado)
        # muda de linha
        turtle.penup()
        turtle.setx(posx)
        turtle.pendown()
    turtle.hideturtle()

Então afinal em que ficamos? Bom numa conclusão simples: os dois sub-problemas estão ligados entre si. Isso acontece com muita frequência e nessa altura temos que ver como é que jogam um com o outro. Bom. Agora sim, é tempo de encerrar este post. Ou talvez não... Lembrei-me agora de um outro problema que ocorre com frequência em jogos e simulações. Desenhar uma bela grelha colorida como a da figura.

Um... estamos a pensar todos o mesmo, não é verdade? Que diferença em relação aos problemas anteriores? Pensemos no óbvio, na pirâmide de quadrados. Não há problema de posicionamento diferenciado por linha e todas as linhas são iguais. Queremos adaptação mais simples???

def grelha(n,posx, posy,lado,cor):
    # inicialização
    turtle.pencolor(cor)
    for i in range(n):
        # desenha linha i    
        for j in range(n):
            quadrado(turtle.xcor(),turtle.ycor(), lado)
            turtle.setx(turtle.xcor()+lado)
        # muda de linha
        turtle.penup()
        turtle.goto(posx,turtle.ycor()-lado)
        turtle.pendown()
    turtle.hideturtle()

Bastou incluir o parâmetro formal para a cor, ter os dois ciclos executados o mesmo número de vezes, e não me preocupar com o posicionamento!!!

Elementar!

(Porque não pensar em variantes destes problemas, ou em usar a grelha final para colocar tartarugas a passear sobre a dita??? A imaginação é o limite.)

sexta-feira, 1 de novembro de 2013

Ai, é tão parecido com...

Programamos muito por adaptação de código já feito, por nós ou por outrem. Mais uma razão para que os programas sejam legíveis e modulares. Programamos pois por analogia. Vejamos um exemplo simples. Seja o programa para o cálculo dos inteiros positivos entre 1 e n.

def somatorio(n):
    """ Calcula a soma dos inteiros positivos de 1 até n."""
    soma = 0
    for i in range(1,n+1):
        soma += i
    return soma

Admitamos que nos pedem agora para um programa para o cálculo do número harmónico de ordem n, definido por:

Que semelhança com o problema anterior? Não consegue ver? E se der a definição do primeiro caso:

Parece agora evidente que são semelhantes. A única diferença está no termo a somar: i no primeiro caso, 1/i no segundo. Logo:

def harmonico(n):
    """ Calcula o número harmónico dde ordem n."""
    soma = 0
    for i in range(1,n+1):
        soma += 1/i
    return soma

Já está. E se for para calcular o número de Euler, base do logaritmo natural:

As diferenças estão nos limites do somatório e no termo a somar de cada vez. Mas não é substancialmente diferente, pois não? Na solução é evidente que temos que limitar o ... infinito!

import math
 
def expo(n):
    soma = 0
    for i in range(0,n+1):
        soma += 1/math.factorial(i)
    return soma

Estamos a usar a função factorial do módulo math. Mas também não é difícil escrever um programa para o cálculo do factorial. Por definição:

com o factorial de 0 igual a 1. Podemos usar a analogia com o caso do somatório, sendo que a única diferença é termos um produto em vez de uma soma.

def factorial(n):
    """ Calcula o factorial de um número."""
    fact = 1
    for i in range(1,n+1):
        fact *= i
    return fact

Notar como o caso de zero foi tratado à parte. Regressemos aos exemplos anteriores e pensemos no caso da aproximação do valor do seno (em radianos):

Como adaptar as soluções anteriores (em particular a do número de Euler? Trivial. Só o termo a somar é que é um pouco mais complexo.

import math
 
def seno(x,n):
    soma = 0
    for i in range(0,n+1):
        soma += (((-1)**i) * x**(2*i+1))/math.factorial(2*i+1)
    return soma

Aqui o que há a reter é que não se trata de uma constante mas sim de uma função de uma variável.
That's it!

Devagar se vai ao longe (II)

Neste post vamos regressar ao tema da complexidade inerente a desenvolver uma solução informática e ao melhor modo de a dominar. A ideia central é simples: dividir o problema em sub-problemas.
Comecemos com um dos problemas do livro, o problema 5.10. Lançamos dois dados, numerados de 1 a 6, um certo número de vezes, e queremos saber a percentagem das situações em que a soma dos dois números que saíram é par.
Perante o enunciado temos que ser capazes de perceber que o programa envolve a repetição dos lançamentos e a análise do resultado. Assim, podemos escrever um primeiro esboço de solução.

def dados_par(n):
    # inicialização
    for i in range(n):
        # lança dados
        # calcula soma
        # testa resultado e actualiza contagem
    return # resultado

Este esboço mostra os sub-problemas que identificámos e que descrevemos na forma de comentários. Como já não somos novatos em programação temos claro que vamos precisar de um contador para saber quantas vezes o resultado saiu par:

def dados_par(n):
    # inicialização
    conta = 0
    for i in range(n):
        # lança dados
        # calcula soma
        # testa resultado e actualiza contagem
    return 100 * conta/n

Vamos resolver agora o problema do lançamento dos dados. Recorremos ao módulo random e ao método randint.

import random
 
def dados_par(n):
    # inicialização
    conta = 0
    for i in range(n):
        # lança dados
        dado_1 = random.randint(1,6)
        dado_2 = random.randint(1,6)
        # calcula soma
        # testa resultado e actualiza contagem
    return 100 * conta/n

Falta agora tratar dos dois últimos problemas. Não nos levarão a mal se fizermos tudo de uma só vez.

import random
 
def dados_par(n):
    # inicialização
    conta = 0
    for i in range(n):
        # lança dados
        dado_1 = random.randint(1,6)
        dado_2 = random.randint(1,6)
        # calcula soma
        soma = dado_1 + dado_2
        # testa resultado e actualiza contagem
        if soma % 2 == 0:
            conta += 1
    return 100 * conta/n

Passemos à questão de imprimir uma pirâmide de números com o aspecto seguinte:

Claro que este é apenas um exemplo para o caso de queremos uma pirâmide com 5 linhas. A nossa solução terá que ser genérica. De qualquer dos modos, é claro que a solução passa por imprimir, uma a uma, as diferentes linhas.

def piramide_numeros(n):
    """Desenha uma pirâmide de números."""
    for i in range(1,n+1):
        # mostra linha i
        # linha seguinte
        print()

Avançámos pouco, certo? Como tratar cada linha? Da observação do resultado pretendido resulta claro que temos várias questões a resolver: onde começar a imprimir uma linha, como imprimir uma sequência que primeiro decresce e depois cresce. Ou seja o nosso problema de imprimir uma linha decompõe-se em três sub-problemas.

def piramide_numeros(n):
    """Desenha uma pirâmide de números."""
    for i in range(1,n+1):
        # mostra linha i
        # -- (1) posicionar
        # -- (2) imprime sequência decrescente
        # -- (3) imprime sequência crescente
        # linha seguinte
        print()

Posicionar parece ser a questão mais difícil, pelo que nos vamos preocupar com os outros. A sequência decrescente para uma dada linha i começa em i e vai até 1. Sabemos como fazer isso recorrendo ao iterável range com três argumentos e um ciclo for. Notar como o print da cada número não é seguido de mudança de linha graças aos terminador ser o espaço em branco (end = ‘ ‘). Notar ainda que o segundo argumento do range é 0, precisamente para que 1 seja o último a ser impresso. Finalmente, optámos por criar pirâmides em que os números podem ter um máximo de 3 dígitos (‘%3d’).

def piramide_numeros(n):
    """Desenha uma pirâmide de números."""
    for i in range(1,n+1):
        # mostra linha i
        # -- (1) posicionar
        # -- (2) imprime sequência decrescente
        for j in range(i,0,-1):
            print('%3d'% j, end = ' ')
        # -- (3) imprime sequência crescente
        # linha seguinte
        print()

O caso da sequências ascendente é semelhante só que o começo deve ser agora o número 2.

def piramide_numeros(n):
    """Desenha uma pirâmide de números."""
    for i in range(1,n+1):
        # mostra linha i
        # -- (1) posicionar
        # -- (2) imprime sequência decrescente
        for j in range(i,0,-1):
            print('%3d' % j, end = ' ')
        # -- (3) imprime sequência crescente
        for j in range(2,i+1):
            print('%3d' % j, end=' ')
        # linha seguinte
        print()

Vamos então ao posicionamento. Olhando para a figura verificamos que a última linha não obriga a nenhum posicionamento especial. A penúltima, terá que ser avançada do espaço máximo que um número pode ocupar (neste caso 3), a que se soma o espaço entre números (neste caso, 1). Na antepenúltima temos que avançar o dobro do espaço anterior. De um modo geral na linha i temos que avançar 4*(n-i) espaços! Estamos em condições de completar o nosso programa.

def piramide_numeros(n):
    """Desenha uma pirâmide de números."""
    for i in range(1,n+1):
        # mostra linha i
        # -- (1) posicionar
        print(4*(n-i) * ' ', end='')
        # -- (2) imprime sequência decrescente
        for j in range(i,0,-1):
            print('%3d'%j, end = ' ')
        # -- (3) imprime sequência crescente
        for j in range(2,i+1):
            print('%3d'%j, end=' ')
        # linha seguinte
        print()

Et voilá!

Programação com Python