Programação com Python: 2013

domingo, 22 de dezembro de 2013

Bonecada

Acabámos de ver como podemos usar o módulo turtle para resolver um problema de visualização de um gráfico de barras. Notámos várias dificuldades que procurámos resolver de modo mais ou menos satisfatório. Do exercício resulta a ideia de gráficos em Python são um tormento. Nada de mais errado. O que precisamos é usar a ferramenta certa. É o que vamos fazer agora mostrando como podemos resolver o mesmo problema usando o módulo matplotlib.

Comecemos pelo exemplo básico.

import random
import matplotlib.pyplot as plt
 
 
def gera(n):
    return [random.randint(1,6) + random.randint(1,6) for i in range(n)]
 
def histograma(dados):
    plt.hist(dados,11)
    plt.show()    
     
if __name__ == '__main__':
    dados = gera(5000)
    histograma(dados)

Correndo o programa aparece-nos a bela imagem seguinte.

Fantástico, não é. Mas ainda podemos introduzir um pouco de cosmética...

def histograma(dados):
    plt.title('Dados = ' + str(len(dados)))
    plt.xlabel('Resultado')
    plt.ylabel('Frequência')
    plt.hist(dados,11,color='red')
    plt.show()  

... para obter um resultado diferente!

E a Lei dos Grandes Números? ainda se lembra?

Usar o matplotlib é mais simples ... e bem mais rápido! Claro que também o podemos usar para outro tipo de gráficos. Por exempo, o gráfico de uma função y=f(x).

def grafico(x,y):
    plt.title('y=f(x)')
    plt.xlabel('x')
    plt.ylabel('y')
    plt.plot(x,y,'go-')
    plt.show()

E obtemos com esta configuração o resultado:

As possibilidades do matplotlib são imensas. O manual recente do módulo pode ser obtido em Manual

Divirta-se.

Barras paralelas

Numa das últimas aulas estivemos a preparar o último teste. Um dos exemplos procurava passar por alguns dos aspectos essenciais: dicionários e ficheiros. O problema consistia em escrever um programa que realizasse quatro tarefas:

1- simular o lançamento de dois dados guardando o resultado da sua soma numa lista,

2- guardar os resultados num ficheiro, com um resultado por linha;

3- construir um dicionário de frequências em que as chaves fossem os números e os valores o número de vezes que ocorreram;

5- apresentar um gráfico de barras com o histograma das frequências. O gráfico seria feito com a ajuda do módulo turtle.

Os três primeiros sub-problemas eram revisitações de algo que já tínhamos feito. A nossa ideia era consolidar os conceitos e aproveitar para mais um exemplo de decomposição de problemas em sub-problemas e das quesdtões que se levantam.

Cada um deles podia ser resolvido de modo simples. Comecemos pelo problema da geração.

import random
 
def gera_1(n):
    lista = list()
    for i in range(n):
        lista.append(random.randint(1,6)+random.randint(1,6))
    return lista
 
def gera_2(n):
    return [random.randint(1,6) + random.randint(1,6) for i in range(n)]
 
def dado():
    return random.randint(1,6)
 
def gera_3(n):
    return [dado()+dado() for i in range(n)]

A primeira solução é a mais básica. A outras duas usam listas por compreensão, sendo que a última abstrai o problema de lançar o dado. Guardar os dados gerados num ficheiro também é trivial.

def guarda(ficheiro,dados):
    with open(ficheiro,'w') as f_out:
        for dado in dados:
            f_out.write(str(dado)+'\n')

Aqui usámos o gestor de contexto with. Finalmente ir buscar os dados ao ficheiro e construir um dicionário de frequências.

def freq(ficheiro):
    with open(ficheiro) as f_in:
        dados_str = f_in.read().split()
        dados_num = [eval(dado) for dado in dados_str]
        # dicio frequências
        dicio = dict()
        for dado in dados_num:
            dicio[dado] = dicio.get(dado,0) + 1
    return dicio

Estas três soluções têm que ser integradas num único programa. Só precisamos ter em atenção a interface.

def main(n, ficheiro):
    # gerar
    dados = gera_2(n)
    # guardar
    guarda(ficheiro, dados)
    # frequência
    frequencia = freq(ficheiro)

Agora fica a questão das barras e do uso do turtle. Admitamos que queremos fazer um gráfico como o da figura:

Vamos tentar decompor tudo em sub-problemas mais simples: os eixos, as barras e os valores. Vamos começar pelas barras e fazer algo como no caso do lançamento dos dados: começar pela questão de visualizar uma barra.

import turtle
 
def barra(pos,altura,cor, espessura):
    # posiciona
    turtle.penup()
    turtle.goto(pos)
    turtle.pendown()
    turtle.setheading(90)
    # atributos
    turtle.color(cor)
    turtle.width(espessura)
    # Desenha
    turtle.forward(altura)

A ideia desta solução é trivial: posicionar a tartaruga, colocá-la a apontar para norte e avançar um valor igual à altura da barra.

Desenhar um gráfico de barras pode ser agora feito chamando repetidas vezes a função barra.

def grafico_barras(pos_inicial,lista_barras, cor, espessura,delta):
    pos = pos_inicial
    for altura in lista_barras:
        barra(pos,altura,cor, espessura)
        # posiciona)
        pos = (turtle.xcor()+ delta,0)
    turtle.hideturtle()

O parâmetro delta controla o afastamento entre as barras. Passemos aos eixos. Pode ser feito de diferentes maneiras. Um exemplo:

def eixos(pos_x, pos_y, tam_x, tam_y):
    # posiciona 
    turtle.penup()
    turtle.goto(pos_x, pos_y)
    turtle.pendown()
    # eixo x
    turtle.forward(tam_x)
    turtle.write('X', font=('Arial',8,'bold'))
    # posiciona
    turtle.penup()
    turtle.goto(pos_x, pos_y)
    turtle.pendown()
    # eixo y
    turtle.setheading(90)
    turtle.forward(tam_y)
   
    turtle.write('Y', font=('Arial',8,'bold'))
    turtle.hideturtle()

Usamos a função write para escrever o nome dos eixos. Notar como se controla a escrita. É evidente que podemos ter o desenho dos eixos e das barras tudo junto:

def grafico_barras_eixos(pos_inicial,lista_barras, cor, espessura,delta):
    eixos(pos_inicial[0] -delta, pos_inicial[1], len(lista_barras) * (espessura + delta), max(lista_barras) + delta)
    pos = pos_inicial
    for altura in lista_barras:
        barra(pos,altura,cor, espessura)
        # posiciona)
        pos = (turtle.xcor()+ delta,0)
    turtle.hideturtle()

Notar como se controla a dimensão dos eixos! Falta acrescentar os números. Mas isso pode ser feito com uma pequena alteração no programa que desenha as barras.

def grafico_barras_eixos(pos_inicial,lista_barras, cor, espessura,delta):
    eixos(pos_inicial[0] -delta, pos_inicial[1], len(lista_barras) * (espessura + delta), max(lista_barras) + delta)
    pos = pos_inicial
    for altura in lista_barras:
        barra(pos,altura,cor, espessura)
        turtle.pencolor('black')
        turtle.write(altura, font=('Arial',8,'bold'))
        # posiciona)
        pos = (turtle.xcor()+ delta,0)
    turtle.hideturtle()

Podemos juntar esta solução ao resto do programa, definindo um novo main.

def main(n, ficheiro):
    # gerar
    dados = gera_2(n)
    print(dados)
    # guardar
    guarda(ficheiro, dados)
    # frequência
    frequencia = freq(ficheiro)
    print(frequencia)
    # gráfico
    valores = [frequencia.get(chave,0) for chave in range(1,13)]
    grafico_barras_eixos((0,0),valores,'red',5,15)

Se executarmos o programa, no entanto, o resultado não é muito famoso. O problema está no facto de os valores serem muito pequenos. Uma solução simples é definir um factor de escala que dependerá do número de lançamentos de dados. Interessa-nos uma alteração que aumente muito os valores pequenos de n e pouco os valores grandes. Uma função candidata a tal é a função logaritmo!

def main(n, ficheiro):
    # gerar
    dados = gera_2(n)
    print(dados)
    # guardar
    guarda(ficheiro, dados)
    # frequência
    frequencia = freq(ficheiro)
    print(frequencia)
    # gráfico
    escala = int(math.log(n,10)) # <--- 
    valores = [escala * frequencia.get(chave,0) for chave in range(1,13)]
    grafico_barras_eixos((0,0),valores,'red',5,15)
    turtle.exitonclick()

Mas podemos promover outra pequena alteração para poder colocar a identificação dos números ao longo dos eixos dos XX.

A mudança principal envolve a função barra.

def barra(pos,altura,cor, espessura,num):
    if altura:
        # posiciona
        turtle.penup()
        turtle.goto(pos[0],pos[1]-20)
        turtle.write(num)
        turtle.goto(pos)
        turtle.pendown()
        turtle.setheading(90)
        # atributos
        turtle.color(cor)
        turtle.width(espessura)       
        # Desenha
        turtle.forward(altura)
        turtle.pencolor('black')
        turtle.write(altura, font=('Arial',8,'bold'))  

Notar que passámos a fazer aqui toda a parte que interssa saber da barra: valor de x, de y e o desenho.

Para quem gosta de tudo muito direitinho aqui fica o programa final completo.

import random
import operator
import math
 
def gera_2(n):
    return [random.randint(1,6) + random.randint(1,6) for i in range(n)]
 
# Guardar
def guarda(ficheiro,dados):
    with open(ficheiro,'w') as f_out:
        for dado in dados:
            f_out.write(str(dado)+'\n')
     
# Frequência
def freq(ficheiro):
    with open(ficheiro) as f_in:
        dados_str = f_in.read().split()
        dados_num = [eval(dado) for dado in dados_str]
        # dicio frequências
        dicio = dict()
        for dado in dados_num:
            dicio[dado] = dicio.get(dado,0) + 1
    return dicio
 
# Ver
import turtle
 
def barra(pos,altura,cor, espessura,num):
    if altura:
        # posiciona
        turtle.penup()
        turtle.goto(pos[0],pos[1]-20)
        turtle.write(num)
        turtle.goto(pos)
        turtle.pendown()
        turtle.setheading(90)
        # atributos
        turtle.color(cor)
        turtle.width(espessura)       
        # Desenha
        turtle.forward(altura)
        turtle.pencolor('black')
        turtle.write(altura, font=('Arial',8,'bold'))        
 
def grafico_barras_eixos(pos_inicial,lista_barras, cor, espessura,delta):
    eixos(pos_inicial[0] - delta, pos_inicial[1], len(lista_barras) * (espessura + delta), max(lista_barras) + delta)
    pos = pos_inicial
    for num,altura in enumerate(lista_barras):
        barra(pos,altura,cor, espessura,num)
        # posiciona
        pos = (turtle.xcor()+ delta,pos_inicial[1])
    turtle.hideturtle()
 
def eixos(pos_x, pos_y, tam_x, tam_y):
    # posiciona 
    turtle.penup()
    turtle.goto(pos_x, pos_y)
    turtle.pendown()
    # eixo x
    turtle.forward(tam_x)
    turtle.write('X', font=('Arial',8,'bold'))
    # posiciona
    turtle.penup()
    turtle.goto(pos_x, pos_y)
    turtle.pendown()
    # eixo y
    turtle.setheading(90)
    turtle.forward(tam_y)
    turtle.write('Y', font=('Arial',8,'bold'))
    turtle.hideturtle()
     
# MAIN ----------------
def main(n, ficheiro):
    # gerar
    dados = gera_2(n)
    print(dados)
    # guardar
    guarda(ficheiro, dados)
    # frequência
    frequencia = freq(ficheiro)
    # gráfico
    escala = int(math.log(n,10)) # <-- 
    valores = [escala * frequencia.get(chave,0) for chave in range(1,13)]
    grafico_barras_eixos((0,0),valores,'red',5,15)
    turtle.exitonclick()
     
     
     
 
if __name__ == '__main__':
    main(1000,'/Users/ernestojfcosta/tmp/tudo.txt')

Para quem gosta de experiências, tente executar o programa para diferentes valores crescentes de n. Os gráficos de barras que são desenhados vão convergir para uma forma de distribuição conhecida em probabilidades: a distribuição normal. é uma boa altura para revisitar a Lei dos Grandes Números.

Boas Festas!

sábado, 21 de dezembro de 2013

Teste #3 - TP9

Pergunta 1

Explique o que vai aparecer no lugar dos pontos de interrogação (linhas 7 e 11).

>>> def toto(n):
... res = n.append(4)
... return res
...
>>> n = (5,6,7)
>>> print(toto(n))
Traceback (most recent call last): # Explicação: Erro porque append não é método de tuplos!
...
builtins.AttributeError: 'tuple' object has no attribute 'append'
>>> n
(5, 6, 7) # Explicação: n é imutável não sendo afectado pela chamada de toto(n).

Pergunta 2

Admita que tem guardado no dicionário informação relativa ao desempenho das equipas envolvidas num campeonato desportivo. A cada jornada pares de equipas jogam entre si. O dicionário está organizado de modo que as chaves são os nomes dos clubes, e os valores uma lista com o número de vitórias, de empates e de derrotas, por esta ordem, obtidos nos diferentes jogos em que a equipa esteve envolvida. Escreva um programa que dado o dicionário com a informação referida me devolva uma lista das equipas que obtiveram o maior número de vitórias.

Solução

Existem várias alternativas. Aqui optou-se por ir buscar toda a informação ao dicionário e passá-la para uma lista. De seguida os pares (clube, vitórias) é inspeccionado na procura do(s) de maior vitórias. Dentro do ciclo for fazemos o teste. Se encontramos algum clube com um novo máximo recomeçamos o processo com uma lista com esse clube apenas. Cada vez que encontramos um clube com o um valor igual ao máximo, acrescentamos o clube à lista dos clubes com número máximo de vitórias.

def mais_vict(campeonato):
    res = list(campeonato.items())
    max_v = 0
    clubes = []
    for c,r in res:
        if r[0] > max_v:
            max_v = r[0]
            clubes = [c]
        elif r[0] == max_v:
            clubes.append(c)
    return (clubes, max_v)

Pergunta 3 Suponha que tem guardado em disco um ficheiro de texto. Pretende analisar o conteúdo do texto para determinar a lista das palavras que nele ocorrem com uma frequência superior a um dado valor. Escreva um programa que dado um ficheiro e o valor de referência determina a lista das palavras que ocorrem um número de vezes superior a esse valor.

Solução

O que vamos fazer é começar por construir um dicionário de frequências para as palavras do ficheiro. Depois percorremos o dicionário identificando as palavras que ocorrem um número de vezes superior ao valor de referência (limiar).

def lista_freq(ficheiro,limiar):
    f_ent = open(ficheiro, 'r', enconding='utf8')
    palavras = f_ent.read().replace('\n',' ').split()
    dicio = {}
    for pal in palavras:
        dicio[pal] = dicio.get(pal,0) + 1
    lista = []
    for pal,num_ocor in dicio.items():
        if num_ocor > limiar:
            lista.append(pal)
    return lista

Teste #3 - TP 3

Pergunta 1
Explicar o que aparece nos pontos de interrogação (linhas 6 e 8).

>>> def titi(n):
... n.append([4])
...
>>> x = [1,2,3]
>>> print(titi(x))
None # Explicação: Porque a definição titi não tem return! Todavia n é alterado
>>> x
[1, 2, 3, [4]] #Explicação:  x é um objecto mutável pelo que a operação append sobre n também afecta x

Pergunta 2
Admita que tem guardado no dicionário informação relativa ao desempenho das equipas envolvidas num campeonato desportivo. A cada jornada pares de equipas jogam entre si. O dicionário está organizado de modo que as chaves são os nomes dos clubes, e os valores uma lista com o número de vitórias, de empates e de derrotas, por esta ordem, obtidos nos diferentes jogos em que a equipa esteve envolvida. Escreva um programa que dado o dicionário com a informação referida me devolva uma lista das equipas e sua pontuação, ordenada de modo que as mais pontuadas apareçam primeiro. Admita que uma vitória vale 3 pontos, um empate 1 ponto e uma derrota 0 pontos.

Solução

Vamos resolver este problema por decomposição em três sub-problemas. Num criamos uma estrutura, uma lista, onde colocamos pares (pontuação, nome_clube). Depois ordenamos a lista de modo decrescente pela pontuação. Finalmente, reconstruímos a lista no formato desejado. Esta última tarefa resulta do facto de termos construído os pares com a ordem “trocada” para nos facilitar o ordenamento.

def classif(campeonato):
    final = []
    for clube, result in campeonato.items():
        pontos = 3 * result[0] + result[1]
        final.append([pontos,clube])
    final.sort(reverse=True)
    lista = [[elem[1], elem[0]] for elem in final]
    return lista

Claro que existem outras formas de resolver esta questão. Por exemplo, para os que aprenderam nas aulas que existe um módulo em Python, chamado operator, que disponibiliza um método, itemgetter, para ordenar uma lista cujos elementos são eles próprios listas ou tuplos, uma alternativa era:

import operator   
 
def classif(campeonato):
    final = []
    for clube, result in campeonato.items():
        pontos = 3 * result[0] + result[1]
        final.append((clube, pontos))
    final.sort(key=operator.itemgetter(1), reverse=True)
    return final

Pergunta 3

Suponha que tem guardado em disco um ficheiro de texto. Pretende analisar o conteúdo do texto para determinar se ele é suspeito ou não. Um texto é suspeito se nele constarem pelo menos metade das palavras de uma lista de palavras proibidas. Escreva um programa que dado um ficheiro e uma lista de palavras proibidas determina se ele é ou não suspeito.

Solução

A solução mais simples consiste em extrair a informação do ficheiro na forma de uma lista das suas palavras, fazer a contagem do número de palavras proibidas que ocorrem no texto, e depois fazer a comparação.

def suspeito(ficheiro,palavras):
    f_ent = open(ficheiro, 'r', enconding='utf8')
    pal_ficheiro = f_ent.read().replace('\n',' ').split()
    f_ent.close()
    conta = 0
    for pal in palavras:
        if pal in pal_ficheiro:
            conta += 1
    if conta >= len(palavras)//2:
        return True
    else:
        return False

Optámos for fazer a contagem num ciclo controlado pelas palavras proibidas. Podíamos fazer semelhante mas agora com o ciclo a ser controlado pelas palavras do texto. Será interessante analisar qual das duas soluções é melhor. Isso depende to tamanho relativo das duas listas e do custo de procurar uma palavra num texto (instrução if pal in palavras).

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!

Programação com Python