sexta-feira, 11 de outubro de 2013

Programar é ... recordar!

Depois de muitos anos a programar todos nós temos um conjunto de soluções para diferentes problemas. quando se nos depara um novo problema um reflexo natural é perguntar: já resolvi este problema? Já resolvi um problema parecido? Já resolvi um problema que não sendo parecido me pode inspirar no modo de resolver o problema novo? Para tornar as coisas mais concretas olhemos para a figura seguinte:
Cinco quadrados concêntricos, coloridos. O problema é o de desenvolver um programa que crie este desenho. Depois de pensar um pouco, recordo-me do problema do logotipo dos jogos olímpicos:
Qual é analogia? O mesmo objecto repetido cinco vezes, mas com cores, posição e dimensão diferentes. Então é tentador seguir a mesma abordagem que neste caso: primeiro um programa que desenha um quadrado colorido, numa dada posição e com um dado comprimento para o lado. Como no caso anterior podia resolver este problema por partes: primeiro, um quadrado com um dado lado, depois numa dada posição e, finalmente com uma dada cor. Acho que não me levarão a mal se eu colocar já a versão final. Afinal, é o que nos vai acontecer à medida que estamos à vontade com a programação!
def quadrado_cor(posx,posy,lado, cor):
    # Posiciona
    turtle.penup()
    turtle.goto(posx,posy)
    turtle.pendown()
    # Define cor
    turtle.pencolor(cor)
    # Desenha
    for i in range(4):
        turtle.forward(lado)
        turtle.left(90)
    turtle.hideturtle()
Agora a segunda parte: desenhar cinco, variando a posição, o lado e a cor. Vamos fazer um desenho para nos ajudar, desenho esse que mostre a relação entre dois quadrados em função da diferença de tamanho dos respectivos lados (que designamos por incremento):
A partir do desenho não é difícil o que temos que mudar na posição e no tamanho. Na posição, e tomando como referência o canto inferior esquerdo a posição do quadrado externo relativamente ao interno será:

posx_ext = posx_int - incremento / 2
posy_ext = posy_int - incremento / 2

Quanto ao tamanho:
lado_ext = lado_int + incremento
Resolvida esta questão vamos então resolver o que falta.
def quadrados_concentricos(posx, posy,lado,incremento):
    quadrado_cor(posx,posy,lado,'red')
    quadrado_cor(posx - incremento/2,posy - incremento/2,lado + incremento,'green')
    quadrado_cor(posx - incremento,posy -incremento,lado + 2*incremento,'blue')
    quadrado_cor(posx - 3*incremento/2,posy-3*incremento/2,lado + 3*incremento,'black')
    quadrado_cor(posx - 2 * incremento,posy- 2*incremento,lado + 4*incremento,'orange')
    
        
        
if __name__ == '__main__':
    quadrados_concentricos(0,0,50,20)
    turtle.exitonclick()
Antes de ir fazer outra coisa volte ao código do logotipo dos jogos olímpicos e veja as semelhanças...

Olhar ... e ver

Dominar a complexidade é uma das questões mais importantes na resolução informática de problemas. Existem diferentes maneiras de o fazer, isto é, de reduzir a dificuldade em resolver um problema, como por exemplo começar por resolver uma versão mais simples do problema, esquecendo alguns detalhes da especificação e depois completar a solução adicionando o que falta, ou decompondo o problema em sub-problemas mais simples que são resolvidos separadamente, ficando para uma segunda fase agrupar as soluções parciais na solução desejada. Vamos exemplificar retomando o exemplo do desenho do logotipo dos jogos olímpicos.
Olhando para o desenho o que vemos? Cinco circunferências, com o mesmo raio, a mesma espessura do traço, mas cores e posições diferentes. A pergunta que devemos fazer é: se eu souber desenhar uma circunferência com um dado raio, espessura, cor e posição tenho a vida facilitada para desenhar as cinco? Claramente. Vamos então meter mãos à obra, resolvendo o problema de um modo geral para podermos posteriormente usar para as cinco situações diferentes. Podemos começar por esquecer vários dos atributos que devemos considerar e pensar apenas em desenhar uma circunferência com um dado raio. Simples, certo?
def circunferência(raio):
 turtle.circle(raio)
Acrescentemos agora a posição.
def circunferência(posx, posy,raio):
 # Posição
    turtle.penup()
     turtle.goto(posx, posy)
     turtle.pendown()
 # Desenha
 turtle.circle(raio)
Procedendo de igual modo para os outros atributos chegamos à versão final completa.
def circunferencia(posx, posy, cor, raio, espessura):
    # Define atributos
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    turtle.pencolor(cor)
    turtle.width(espessura)
    # Desenha e Esconde tartaruga
    turtle.circle(raio)
    turtle.hideturtle()
Este programa permite desenhar uma circunferência podendo ser controladas a posição, o raio, a cor e a espessura. Fica por fazer dispor cinco circunferências em posições precisas. A figura que se segue ajuda-nos nos cálculos.
Assim se a posição da circunferência central da linha de cima for (x,y) as coordenadas das restantes são:

cima, à direita: (x+ 2*raio + delta, y)
cima, à esquerda: (x - 2*raio - delta,y)
baixo, à direita: (x + raio + delta/2, y - raio)
baixo, à esquerda: (x - raio - delta/2, y - raio)

Daí a parte que falta para a solução:
def olimpo(x,y,raio, espessura, delta):
    circunferencia(x,y, 'black', raio, espessura)
    circunferencia(x+2*raio+ delta, y, 'red', raio, espessura)
    circunferencia(x-2*raio-delta, y, 'blue', raio, espessura)
    circunferencia(x+raio+(delta/2), y-raio, 'green', raio, espessura)
    circunferencia(x-raio-delta/2, y-raio, 'yellow', raio, espessura)
    
   
if __name__ == '__main__':
    aneis(0,0,50, 3, 5)
    turtle.exitonclick()

quinta-feira, 10 de outubro de 2013

Do que falamos quando falamos de ....

Todos nos lembramos dos tempos idos da infância em que aprendemos a tabuada cantando-a. Hoje fazemos contas usando a tabuada mecanicamente sem grande esforço.  Claro que sabermos que contas temos de fazer continua a ser um desafio.

Aprender a programar envolve também um lado de repetição até interiorizarmos algo que passamos depois a usar de modo imediato. Também aqui fica muito por fazer, seguramente o mais difícil, mas já é um avanço ter algumas partes resolvidas.

Toda esta conversa vem a propósito da aula de hoje em que verifiquei a grande dificuldade conceptual em arrancar com a proposta de solução. Vamos então à mecanização. Sempre que vos aparecer um enunciado que diz: “Escreva/desenvolva um programa que dado isto devolve aquilo” devem ser capazes de saber que o código será algo como:
def isto_em_aquilo(isto):
 # transforma isto em aquilo
 return aquilo
ou uma sua variante, como por exemplo:
def isto_em_aquilo():
 isto = input(‘O que é isto?’)
 # Transforma isto em aquilo
 print(aquilo)
Claro que se quiser pode cantar enquanto escreve o código!

sexta-feira, 4 de outubro de 2013

Tartarugas e Geometria

Durante as aulas vimos como podíamos usar o módulo turtle para desenhar polígonos regulares. Em particular partimos das soluções para triângulos, quadrados e pentágonos:
import turtle

def  quadrado(lado):
    """ Desenha um quadrado de lado."""
    for i in range(4):
        turtle.forward(lado)
        turtle.left(90)
        
        
def  triangulo(lado):
    """ Desenha um triangulo de lado."""
    for i in range(3):
        turtle.forward(lado)
        turtle.left(120)
        
def  pentagono(lado):
    """ Desenha um pentagono de lado."""
    for i in range(5):
        turtle.forward(lado)
        turtle.left(72)
e ao analisar o código para cada caso verificamos que todos têm em comum o facto de o produto do número de lados pelo ângulo de viragem ser sempre igual a 360. E terá que ser sempre assim para um polígono regular! Então podemos generalizar a nossa solução:

def  poligono(lado, num_lados):
    """ Desenha um poligono de num_lados ."""
    for i in range(num_lados):
        turtle.forward(lado)
        turtle.left(360/num_lados)



 Com este programa podemos desenhar qualquer polígono regular. Podemos pensar agora em alterar a solução geral desfazendo a relação entre o número de lados, o ângulo de viragem e 360 graus. Isso envolve considerar o ângulo como um parâmetro adicional da definição:

def  formas(lado, num_lados, angulo):
    """ Desenha sequências de segmentos eventualmente produzindo formas fechadas."""
    for i in range(num_lados):
        turtle.forward(lado)
        turtle.left(angulo)

Testando diferentes configurações verificamos que para algumas de novo obtemos formas fechadas. Alguns exemplos.
formas(100,5,144)
formas(100,8,135)
formas(100,10,108)






A razão para obtermos estas formas é simples: o produto do número de lados pelo ângulo de viragem é um múltiplo de 360!
Pode-se provar um teorema geral para qualquer forma fechada, seja polígono ou não: a soma dos ângulos de viragem ao longo da forma é sempre um múltiplo de 360. Será que o inverso é verdadeiro, ou seja, se a soma do ângulo de viragem for múltiplo de 360 graus então a forma é fechada? De um modo geral isto não é verdadeiro, embora seja verdadeiro para o caso das formas geradas pelo nosso programa formas.

Regresso ao Futuro

Depois de um ano sem dar aulas, eis-me de volta a este blogue de suporte da disciplina Introdução à Programação e Resolução de Problemas, do primeiro ano da Licenciatura em Engenharia Informática,  da Universidade de Coimbra. Vou procurar continuar a colocar aqui soluções de exemplos das aulas/testes/exames e responder às questões que queiram colocar.

O blogue será tanto mais activo quanto mais receber questões do vosso lado...

quarta-feira, 25 de janeiro de 2012

Exame Época Normal

Pergunta 2

Solução: Uma solução possível, a mais natural, seria:


for i in range(20,-1,-2):
print "i= ",i

Notar como tudo se resolve usando range com três argumentos. Note-se que os valores têm que ser impressos por ordem decrescente, incluindo o zero. Como o último argumento não conta temos que deixar ir até -1.

Pergunta 3
Enunciado: Suponha que participa numa competição em que lhe são atribuídos pontos (um número inteiro) por cada jogo que faz. Admita também que a sua pon- tuação final é a média dos pontos que obteve nos jogos, depois de serem retirados o seu melhor e o pior resultados. Escreva um programa que dados os resultados dos vários jogos, devolve a sua pontuação.

Solução: Sabemos que as pontuaçõeds estão guardadas numa lista e que temos que primeiro retirar o valor menor e o valor maior. Podemos para tal, usar as funções max e min. Mas vamos fazer de outro modo, começando por ordenar a lista. Depois disso, basta fazer uma cópia sem o primeiro (o mais pequeno) e o último (o maior) elementos. O cálculo da média depois é trivial, havendo apenas o cuidado de garantir que a divisão envolve floats. Atente-se ainda o modo como podemos somar os elementos de uma lista com a função sum.


def pontos(valores):
valores.sort()
contam = valores[1:-1]
res = sum(contam)/float(len(contam))
return res

Pergunta 4


Enunciado: Suponha um ficheiro formado por várias linhas e em que cada linha contém um certo número de números. A quantidade de números por linha não é necessariamente a mesma. Um exemplo de ficheiro possível ( mas é apenas um exemplo!):

12 15 30 26
100 34 13
34
58 39 9 22

Pretendemos um programa que dado um ficheiro com estas caracterís- ticas, determina o valor mais alto em cada linha, e calcula a média desses valores. Se olharmos para o exemplo acima o resultado devia ser calculado a como (30 + 100 + 34 + 58)/4, ou seja, 55.5.

Solução: Uma vez mais procuraremos uma solução simples. Precisamos de ler e guardar os dados. Fazemos isso, construindo uma lista de cadeias de caracteres (readlines()). Mas o que queremos é manipular números. por isso, a seguir, obtemos os dados na forma de lista de listas, em que cada elemento é uma listqa com os números de uma dada linha. Para isso, recorremos a listas por compreensão, embora também possa ser feito de modo mais convencional com um ciclo for. Vamos depois identificar os maiores valores em cada linha, recorrendo à função max e a listas por compreensão. Obtido estes valores o cálculo da média é trivial.

def media(ficheiro):
# ler dados
f_in = open(ficheiro,'r')
dados = f_in.readlines()
f_in.close()
# passa a lista de lista de números
for i in range(len(dados)):
dados[i] = [float(elem) for elem in dados[i][:-1].split()]
# identifica os máximos
maximos = [max(elem) for elem in dados]
# calcula média
media = sum(maximos) / float(len(maximos))
return media

Pergunta 5

Enunciado: Uma matriz de inteiros pode ser representada em Python por uma lista de listas. Assim, por exemplo, a matriz:

5 0 0
9 0 8
0 0 33

pode ser representada por:
[[5,0,0], [9,0,8],[0,0,33]]
Quando uma matriz tem muitos valores iguais a zero, uma forma mais conveniente de representar essa matriz usando apenas os valores não nulos. Uma forma de fazer isso em Python é através de um dicionário, em que cada elemento da matriz aij = k, k ̸= 0 é representada pelo par (chave:valor) ( (i, j):k). No caso anterior teríamos:
{ (1,1):5, (2,1):9, (2,3): 8, (3,3):33}

Escreva um programa que dada uma matriz representada por uma lista de listas, devolva a matriz equivalente representada por um dicionário.

Solução: Precisamos converter os dados da matriz, inicialmente organizados como uma lista de listas, para um dicionário, onde apenas colocamos os elementos diferentes de zero. A ideia da solução mais abaixo é percorrer a matriz elemento a elemento e testar se o valor é diferente de zero. Se for guardamos no dicionário.



def esparsa(matriz):
res = {}
for linha in range(len(matriz)):
for coluna in range(len(matriz[0])):
if matriz[linha][coluna] != 0:
res[(linha+1,coluna+1)] = matriz[linha][coluna]
return res

sábado, 10 de dezembro de 2011

Problema Complementar 1.4

Um dos problemas complementares que vos foi proposto consistia em usar o módulo turtle para fazer um gráfico de barras. Vamos ilustrar como podemos resolver o problema.

O problema vai ser dividido em dois: primeiro desenvolvemos um programa para desenhar uma barra, a partir de uma dada posição e com um certo tamanho. Podemos também controlar a cor e a espessura da barra; depois, usamos este programa como auxiliar a ser usado pelo programa que desenha todas as barras contidas numa lista.

Vamos então ao primeiro sub-problema.

Também este pode ser dividido em três faes: posiciona a tartaruga; define os parâmetros (cor, espessura, etc.) e desenha.


def barra(pos,tamanho, cor,width):
""" Desenha uma barra na posição pos de altura tamanho."""
# posiciona
turtle.up()
turtle.goto(pos)
turtle.setheading(90)
# parâmetros
turtle.colormode(255)
turtle.pencolor(cor)
turtle.width(width)
# desenha
turtle.down()
turtle.forward(tamanho)
turtle.hideturtle()

Simples não é?

Agora o mais complicado. Ou será que não é assim tão difícil? Se analisar o código abaixo verá que não é assim tão complexo. Temos que inicialmente desenhar o eixo horizontal e defginir os parâmetros para esse eixo (cor, espessura,...) e desenhar o eixo. Como a tartaruga fica fora do local inicial temos a seguir de a reposicionar e preparar para desenhar. Finalmente um ciclo que se serve da nossa função auxiliar para desenhar de modo iterativo cada uma das barras.



def plot_barras(lista):
# Define o eixo dos Xs
numero = len(lista)
largura = 10
tamanho_recta = numero * largura
# Define parâmetros do eixo dos Xs
turtle.width(5)
turtle.pencolor('blue')
turtle.setheading(0)
turtle.goto((-tamanho_recta/2, 0))
# desenha eixo
turtle.down()
turtle.forward(tamanho_recta)
# reposiciona a tartaruga
turtle.up()
turtle.goto((-tamanho_recta/2,0))
turtle.hideturtle()
# Prepara para desenhar
turtle.down()
turtle.setheading(90)
pos = (-tamanho_recta/2) + largura/2
# desenha as barras
for indice in range(numero):
barra((pos,0), lista[indice], 'red',5)
pos = pos + largura

Falta testar e ver o efeito.

if __name__ == '__main__':
plot_barras([50,30,20,40,32,7,5,77,67])
turtle.exitonclick()




Moral da história: quando um problema aparenta ser complexo o melhor é pensar primeiro como o podemos dividir em sub-problemas mais simples!