Programação com Python: outubro 2011

segunda-feira, 31 de outubro de 2011

Problema 5.6

Para resolver o problema de deslizar n posições para a esquerda ou para a direita vamos abordar a questão por etapas. Admitindo que sabemos deslizar isoladamente n elementos para a direita ou para a esquerda a solução gloabla é fácil de escrever.

def desliza_n_d_e(n, lista):
    """Desliza n posições para a direita ou esquerda,de modo circular, os elementos de uma lista."""
    if n > 0:
 return desliza_d_n(n,lista)
    else:
        return desliza_e_n(abs(n), lista)

Temos agora que resolver cada um dos dois sub-problemas quer introduzimos. Eles são muito semelhantes. Comecemos pelo deslizar para a direita. A silução consiste em dividir a lista em dois pedaços, em função do valor de n. Guardamos a parte final numa variável auxiliar e depois acrescentamos à sua frente a parte inicial da lista de que partimos. A figura ilustra a estratégia.

O programa tem apenas que ter o cuidado de testar se a lista é vazia ou não.

def desliza_d_n(n, lista):
    """Desliza n posições para a direita,de modo circular, os elementos de uma lista."""
    if lista == []:
        return lista
    else:
        aux = lista[-n:]
        aux.extend(lista[:len(lista) - n])
        return aux

Para o deslizar pata a esquerda usamos o mesmo mecanismo.

def desliza_e_n(n, lista):
    """Desliza n posições para a esquerda,de modo circular, os elementos de uma lista."""
    if lista == []:
        return lista
    else:
        aux = lista[n:]
        aux.extend(lista[:n])
        return aux

Como é lógico podíamos ter resolvido o problema só com uma função, cobrindo os dois casos. Fica para o leitor resolver.

Problema 5.2

Estes problemas são muito elementares e a sua função é apenas obrigar a conhecer as operações que podemos fazer sobre listas. Vamos apenas apresentar a solução para o problema de calcular e devolver a soma de todos os valores (números) contidos numa lista. Permite-nos ilustrar os diferentes modos de iterar com listas e, ainda, o que podemos fazer quando conhecemos melhor a linguagem.

Pecorrer por índice

def idades_4a(lista):
 soma=0
 for indice in range(len(lista)):
  soma = soma + lista[indice]
 return soma

Perocorrer pelo conteúdo

def idades_4b(lista):
 soma = 0
 for elem in lista:
  soma = soma + elem
 return soma

Recurso à função sum

1.def idades_4c(lista):

2. return sum(lista)

Problema 5.1

Implementar os métodos referidos pode ser feito de várias maneiras. Aqui apenas apresento a maneira mais básica. Como tempo aprenderão a fazer de outro modo recorrendo a outras construções da linguagem.

Contagem

def my_count(item, lista):
    """ Número de ocorrências do item na lista."""
    conta = 0
    for elem in lista:
        if elem == item:
            conta = conta + 1
    return conta

Inversão

def my_reverse(lista):
    """Inverte os elementos de uma lista. Cria uma cópia."""
    return lista[::-1]
 
# - variante
def my_reverse_b(lista):
    """Inverte os elementos de uma lista. Cria uma cópia."""
    aux = []
    for elem in lista:
 aux = [elem] + aux
    return aux

Procura

def my_find(item,lista):
    for i in range(len(lista)):
        if lista[i] == item:
            return i
    return -1
 
# Variante
def my_find_b(item,lista):
    for ind, elem in enumerate(lista):
        if elem == item:
            return ind
    return -1

Insere

def my_insert(elem, pos,lista):
    """ Insere o elem na posição. Assume posição correcta."""
    return lista[:pos] + [elem] + lista[pos:]

domingo, 30 de outubro de 2011

Problema 4.7

O facto de este ser o último problema da folha não significa que seja o mais difícil. com efeito, e até em função do que já vimos no problema 4.6 a solução apenas depende do correcto uso do módulo random e de saber como ir retirando caracteres ao alfabeto de modo aleatório.

def cria_chave():
    """Devolve uma chave para encriptar mensagens. Constrói uma permutação."""
    alfabeto = 'abcdefghijklmnopqrstuvwxyz '
    chave = ''
    while alfabeto:
        # escolhe próximo caracter
        indice = random.randint(0,len(alfabeto)-1)
        car = alfabeto[indice]
        # actualiza chave
        chave = chave + car
        # actualiza alfabeto
        alfabeto = alfabeto.replace(car,'')
    return chave

Problema 4.6

Este problema obriga a alguns cuidados. Mas também é um pretexto para percebermos como podemos construir um programa por aproximações sucessivas, não tentando resolver tudo de uma só vez.

De acordo com o algoritmo dado no enunciado uma solução possível para o nosso problema poderá ser:

def cria_chave(palavra_chave):
    """Gera uma chave a partir de uma palavra de passe."""
    alfabeto = 'abcdefghijklmnopqrstuvwxyz '
    # retira duplicações da palavra chave
    palavra_chave = retira_dup(palavra_chave)
    # divide em duas partes
    ultimo_car = palavra_chave[-1]
    indice = alfabeto.find(ultimo_car)
    antes = alfabeto[:indice]
    depois = alfabeto[indice+1:]
    # retira caracteres da palavra chave
    antes = retira_car(palavra_chave, antes)
    depois = retira_car(palavra_chave, depois)
    # junta tudo
    chave = palavra_chave + depois + antes
    return chave

Se olharmos para os comentários torna-se claro que o algoritmo foi correctamente implementado. Claro, que isto só é verdade se as duas funções auxiliares, retira_dup e retira_car, funcionarem bem. É disso que vamos agora tratar. Comecemos pelo problema de retirar os duplicados.

def retira_dup(cadeia):
    """Retira caracteres duplicados na cadeia."""
    nova_cadeia = ''
    for car in cadeia:
        if car not in nova_cadeia:
            nova_cadeia = nova_cadeia + car
    return nova_cadeia

Esta solução, constrói uma nova cadeia, percorrendo os elementos da cadeia antiga uma a um, e só introduzindo os caracteres caso não provoquem uma duplicação.

Uma alternativa é o programa seguinte.

def retira_dup_2(cadeia):
    """Retira caracteres duplicados na cadeia."""
    nova_cadeia = ''
    for ind, car in enumerate(cadeia):
        if car not in cadeia[ind+1:]:
            nova_cadeia = nova_cadeia + car
    return nova_cadeia

Aqui fazemos uso da função enumerate que nos permite percorrer a cadeia simultaneamente pela índices e pelo conteúdo. Veja-se como no teste dentro do if determinamos se um caractere é ou não repetido.

Agora a parte de retirar carateres de um texto.

def retira_car(caracteres, texto):
    """retira do texto os caracteres."""
    novo_texto = ''
    for car in texto:
        if car not in caracteres:
            novo_texto = novo_texto + car
    return novo_texto

Ainda e sempre a mesma ideia: percorrer o texto (ciclo), e sempre que o caractere em análise não pertencer aos caracteres proibidos ele é adicionado (acumulador). A contagem é implícita.

A lição que podemos tirar deste exemplo é a de que vale a pena usar mecanismos de abstracção (neste caso as duas funções auxiliares) para melhor dominar a complexidade da busca da solução para o nosso problema.

Problema 4.2

O problema do cálculo do valor numérico associado a um nome formado por uma única palavra não levanta dificuldades de maior. O padrão habitual -- ciclo, contador e acumulador, chega para resolver a questão. Devido à natureza do problema vamos percorrer a cadeia de caracteres pelo seu conteúdo, pelo que a contagem é implícita. Atente-se no modo como conseguimos estabelecer a relação entre cada caractere e o seu valor numérico. Só precisamos saber o que faz a função ord e não qual o valor no código ASCII associado a cada caractere.

def valor_numerico(nome):
   """ Calcula o valor numérico de um nome. 'a' = 1, ..., 'z' = 26."""
   valor = 0
   for car in nome:
       valor = valor + (ord(car) - ord('a') + 1)
   return valor

segunda-feira, 24 de outubro de 2011

Este problema é muito semelhante ao 3.7. Agora trata-se de desenhar quadrados concêntricos. Ao contrário do exemplo anterior, agora o que muda é a posição inicial já que a orientação se mantém a mesma. É preciso saber no início o incremento do lado a cada repetição.

def quad_concent(n,lado,d):
    """Desenha n quadrados concêntricos.
     
    """
    x0 = xcor()
    y0 = ycor()
    for i in range(n):
 quad(lado+i*2*d, x0-i*d, y0+i*d, 0)

A solução apresentada não é a única. O leitor é convidado a encontrar a sua abordagem e a compará-la com a apresentada.

Problema 3.7

Neste exemplo é-nos pedido para fazer um desenho como o da figura.

Este problema permite mostrar como se pode dominar a complexidade de um problema reutilizando código. Com efeito o que nos é pedido não é mais do que desenhar sucessivos quadrados em que o que vai mudando é o comprimento do lado e a orientação. Assim, usaremos o programa já anteriormente definido que permite desenhar um quadrado, conhecidos o comprimento do lado, a posição inicial e a orientação.

def quad(lado,xcor,ycor,orient):
    """Desenha um quadrado em que o lado, a posição inicial e a orientação inicial podem variar.
     
    """
    penup()
    goto(xcor,ycor)
    setheading(orient)
    pendown()
    for i in range(4):
 forward(lado)
 right(90)
    hideturtle()

Com este programa a funcionar como auxiliar tudo se torna mais simples.

def nautilus(n, lado, xcor,ycor, angulo):
    """Desenha n quadrados com lados e orientações variáveis.
    Desenha uma forma semelhante a um Nautilus.
     
    """
    reset()
    for conta in range(n):
 quad(lado,xcor,ycor,angulo)
 lado = lado + 10
 angulo = angulo + 15
    hideturtle()

Problema 3.6

Este programa mostra como se pode pôr a tartaruga a fazer um passeio aleatório (random walk).

from random import randint
 
def alea(num_lados):
    """Desenha num_lados aleatoriamente.
     
    """
    for conta in range(num_lados):
 novo_x = randint(-100,100)
 novo_y = randint(-100,100)
 goto(novo_x,novo_y)
    hideturtle()
 
def alea_cor(num_lados):
    """Desenha num_lados aleatoriamente.
     
    """
    colormode(255)
    for conta in range(num_lados):
 novo_x = randint(-200,200)
 novo_y = randint(-200,200)
 r = randint(0,255)
 g = randint(0,255)
 b = randint(0,255)
 color((r,g,b))
 goto(novo_x,novo_y)
    hideturtle()

O primeiro programa determina as coordenadas entre dois valores fixos. No segundo exemplo, introduzimos a possibilidade de os traços serem coloridos (também aqui de modo aleatório.).

Problema 3.4

O módulo turtle permite controlar tartarugas que fazem desenhos num tela. Durante as aulas colocámos vários problemas com um grau de dificuldade pequeno. Por exemplo, efectuar desenhos de polígonos regulares. Têm uma estrutura muito semelhante. A listagem que se segue ilustra como se pode fazer de dois modos distintos o desenho de um quadrado, conhecido apenas o lado.

def quadrado_2(lado):
    """Desenha um quadrado de lado  lado.
     
    """
    conta = 0
    while conta < 4:
        forward(lado)
        right(90)
        conta = conta + 1
         
def quadrado_3(lado):
    """Desenha um quadrado de lado lado.
     
    """
    for i in range(4):
        forward(lado)
        right(90)

Aqui o importante a reter é que é mais adequado usar o ciclo for: conhecemos quantas vezes vamos ter que executar o ciclo.

Mas podemos querer uma solução em que a posição e a orientação iniciais também possam ser variáveis. Esta questão resolve-se considerando esses elementos como parâmetros.

def quad(lado,xcor,ycor,orient):
    """Desenha um quadrado em que o lado, a posição inicial e a orientação inicial podem variar.
     
    """
    penup()
    goto(xcor,ycor)
    setheading(orient)
    pendown()
    for i in range(4):
 forward(lado)
 right(90)
    hideturtle()

Podemos generalizar o programa do quadrado para o caso de um polígono regular, desenhado a partir do conhecimento do número de lados e do seu comprimento.

def poligono(num_lados,tam_lado):
    """Desenha um polígono regular.
     
    """
    angulo = 360.0 / num_lados
    for i in range(num_lados):
 forward(tam_lado)
 right(angulo)
    hideturtle()

Uma vez mais se pode ver como se trata a questão de ter mais elementos variáveis: são acrescentados como parâmetros. Este programa pode ajudar-nos a desenhar uma circunferência, conhecido o seu raio. A localização inicial pode ser fixa ou variável.

def circunf(raio):
    """Desenha uma circunferência conhecido o raio.
     
    """
    perimetro = 2 * math.pi * raio
    tam_lado = int(perimetro / 360.0)
    poligono(360,tam_lado)
    hideturtle()
  
     
def circunf_centro(raio, xcor_centro,ycor_centro):
    """Desenha uma circunferência conhecido o raio e a posição do centro.
     
    """
    perimetro = 2 * math.pi * raio
    tam_lado = int(perimetro / 360.0)
    penup()
    goto(xcor_centro, ycor_centro)
    pendown()
    poligono(360,tam_lado)
    hideturtle()  

quinta-feira, 13 de outubro de 2011

Calcular o valor aproximado de PI

Pi é um número irracional e, por isso, o melhor a que podemos aspirar é calcular o seu valor aproximado. Ao longo dos séculos foram aparecendo várias formas de o fazer. Uma delas foi proposta por Leibniz:

$\dpi{120} \bg_white \frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \dots$

Outra por Wallis:

$\dpi{120} \bg_white \frac{\pi}{2} = 2 \times \frac{2}{3} \times \frac{4}{3} \times \frac{4}{5} \times \frac{6}{5} \times \frac{6}{7} \ldots$

Se as fórmulas são distintas do ponto de vista informático são muito semelhantes, uma vez que remetem para um mesmo padrão de programação, baseado no recurso a um ciclo, uma variável de contagem e outra variável de acumulação.

A ideia da solução consiste em ir acrescentando ao longo do ciclo um termo (caso de Leibniz) ou um factor (caso de Wallis) ao resultado parcial.

Comecemos com o caso da abordagem de Leibniz:

def leibniz_pi_1(num_termos):
    """ Calcula valor de pi segundo fórmula de Leibniz.
    """
    conta = 0
    acum = 0.0
    den = 1
    while conta < num_termos:
        acum = acum + (1.0/den) * (-1)**conta
        den = den +2
        conta = conta + 1
    return 4 * acum

Nesta solução é claro que conta faz o papel de contador, e acum o de acumulador. Notar o modo como geramos o termo de ordem i, com o auxílio da variável den. Esta solução pode ser simplificada se tornarmos o contador implícito recorrendo a um ciclo for.

def leibniz_pi_2(num_termos):
    """ Calcula valor de pi segundo fórmula de Leibniz.
    """
    acum = 0.0
    den = 1
    for i in range(num_termos):
        acum = acum + (1.0/den) * (-1)**i
        den = den +2
    return 4 * acum

Mas a fórmula de Leibniz também pode ser apresentada na sua forma compacta:

$\dpi{120} \bg_white \frac{\pi}{4} = \sum_{i=1}^\infty (-1)^i \frac{1 }{(2\times i) + 1}$

Se a usarmos directamente chegamos ao programa:

def leibniz_pi_3(num_termos):
    """ Calcula valor de pi segundo fórmula de Leibniz.
    """
    acum = 0.0
    for i in range(num_termos):
        acum = acum + ((-1)**i) * (1.0/(2 * i + 1))  
    return 4 * acum

Passemos agora para o caso da aproximação pela fórmula de Wallis:

def wallis_1(num_fact):
    """
    Calcula o valor de pi usando a fórmula de Wallis.
    """
    acum = 1.0
    for i in range(2, num_fact,2):
        esquerda = i / float((i-1))
        direita = i /float((i+1))
        acum = acum * esquerda * direita
    return 2 * acum

Este modo de resolver já tem o contador implícito e baseia-se no facto de podermos agrupar os factores aos pares, pois.

$\dpi{120} \bg_white \frac{\pi}{2} =(\frac{2}{1} \times \frac{2}{3}) \times (\frac{4}{3} \times \frac{4}{5}) \times (\frac{6}{5} \times \frac{6}{7}) \ldots$

Assim, em cada passagem pelo ciclo, calculamos dois factores.

Mas podemos também fazer uso da forma compacta:

$\dpi{120} \bg_white \frac{\pi}{2} = \prod_{i=1}^\infty \frac{(2\times i)^2 }{(2\times i)^2 - 1}$

Daqui decorre a nova versão do programa:

def wallis_2(num_fact):
    """
    Calcula o valor de pi usando a fórmula de Wallis.
    """
    acum = 1.0
    for i in range(1, num_fact/2):
        factor = float((2 * i) ** 2) / ((2 * i) ** 2 - 1)
        acum = acum * factor
    return 2 * acum

Se compararmos esta versão com a última versão de Leibniz, fica claro o que queremos dizer quando falamos de semelhanças.

sexta-feira, 7 de outubro de 2011

Problema 2.8

Retirar as vogais de uma cadeia de caracteres e substituir as vogais por um espaço em branco. Para resolver esta questão percebemos que vamos ter que repetir para todos os caracteres um teste para saber se é ou não uma vogal, substituindo no caso afirmativo por um espaço em branco. A solução vai assim ter que combinar um ciclo (for é a nossa opção e esperamos que perceba porquê), com um filtro implementado graças a uma instrução if de duas vias (alternativas).

def tira_vogais(cadeia):
    """Retira as vogais e substitui por um espaÃ§o em branco.
    """
    vogais ='aeiou'
    nova_cadeia =''
    for conta in range(len(cadeia)):
        if cadeia[conta] in vogais:
            nova_cadeia = nova_cadeia + ' '
        else:    
            nova_cadeia = nova_cadeia + cadeia[conta]
    return nova_cadeia

Notar, na solução acima, como conseguimos evitar testes complexos com todos os caracteres, substituindo esses teste por uma única instrução de pertença.

Ainda se pode melhorar o programa introduzindo uma ideia nova: podemos percorrer a cadeia de caracteres pelos valores em vez de ser pelos índices! Durante o curso aprofundaremos esta ideia.

def tira_vogais_b(cadeia):
    """Retira as vogais e substitui por um espaÃÂ§o em branco.
    """
    vogais ='aeiou'
    nova_cadeia =''
    for car in cadeia:
        if car in vogais:
            nova_cadeia = nova_cadeia + ' '
        else:    
            nova_cadeia = nova_cadeia + car
    return nova_cadeia  

Problema 2.3

O problema de obter todas as sub-cadeias de um dado comprimento depende da nossa compreensão da operação de fatiamento e do conceito de repetição (e da sua implementação através de um ciclo). Como as repetições são em número fixo e o seu valor pode ser determinado antes da execução do código, vamos optar pela instrução for. A ideia da solução abaixo apresentada é a de ir percorrendo a cadeia posição a posição, retirando em cada momento uma fatia de tamanho n. Temos que ter ainda em atenção o facto de que devemos terminar o programa mal não seja possível ter maias cadeias de tamanho n.

def sub_cadeias(pal, n):
   """
   Todas as subcadeias de comprimento n.
   """
   for i in range(len(pal) - n + 1):
       print pal[i:i + n]

Problema 2.2

Neste problema é-nos pedido para apresentar todos os prefixos de uma cadeia de caracteres, um por linha. Podemos apresentar o de comprimento 1 primeiro, o de comprimento 2 a seguir, e assim sucessivamente. Temos pois uma acção repetitiva, o que indica que necessitamos de recorrer a um ciclo. Em cada etapa do ciclo é preciso saber onde termina o prefixo, visto sabermos que o início é sempre na primeira posição. Existem duas questões então a resolver: a contagem do número de vezes que vamos andar a repetir e, outra questão, controlar a cada momento o fim do prefixo. Acontece que estas duas questões se podem resolver de modo articulado. Olhemos então para uma solução possível.

def prefixos(cadeia):
   """Determina todos os prefixos de uma cadeia de caracteres.
   """
   conta = 0
   while conta < len(cadeia):         
        print cadeia[:conta+1]         
        conta = conta + 1 

Este padrão de contagem é tão comum que pode ser substituído de modo muito simples recorrendo à instrução de controlo for.

def pref(cadeia):
   for conta in range(len(cadeia)):
       print cadeia[:len(cadeia) - conta]

Mas também podemos apresentar os prefixos por ordem decrescente do seu tamanho.

Podemos, finalmente, mudar o problema, porv forma a que o resultado sejam os sufixos

def sufixos(cadeia):
   for conta in range(len(cadeia)):
       print cadeia[- (conta + 1):]

O problema original é muito simples. Vamos por isso acrescentar apenas o requisito de o podermos usar para diferentes valores do lado do quarado e do raio da circunferência.

import math
 
def hamburger(lado, raio):
"""Que forma de hamburger tem a área maior?.
"""
area_quad = lado ** 2
area_circ = math.pi * raio ** 2
if area_quad > area_circ:
   print 'quadrado'
elif area_quad < area_circ:       
   print 'redondo'  
else:       
   print 'indiferente'

Notar o modo como usámos a condicional if e a necessidade de importar o módulo math para ter acesso ao valor de pi.

Problema 1.1

Trata-se de uma questão trivial. Repare que a solução para o problema depende de um número de constantes pelo que não é preciso estar a usar definições.

1.print 2.9e6 * (9.459 * 10 ** 12)

Note que usamos de propósito dois modos de representar números muito grandes.

Se quisermos resolver um problema mais geral de determinar a distância em quilómetros para qualquer corpo celeste então temos que definir uma função em que o argumento é o valor em anos-luz.

def dist_quilo(anos_luz):
   """Calcula a distância equivalente em quilómetros.
   """
   return anos_luz * 9.459E12

Bug no WingIDE

O WindIDE é um ambiente integrado de desenvolvimento muito interessante. Acresce que existe uma versão gratuita! Mas todos sabemos que nada é perfeito... Então qual é o problema?

Quando carregamos numa tecla geramos um código interno. No passado esse código dava pelo nome de código ASCII (para American Standard Code for Information Interchange). Graças à uniformização que decorre de todos usarem o mesmo código, o que se escreve numa máquina (aplicação) é entendido por outra máquina qualquer (aplicação). O código ASCII permite representar os dígitos, as letras do alfabeto (maiúsculas e minúsculas) e alguns sinais (maior, menor, espaço,...). Não admira que fossem apenas estes. Afinal isto foi inventado para a língua inglesa que não sabe o que é, por exemplo, um til ou um c com cedilha. Para que outras línguas possam ser usadas plenamente foram desenvolvidos outros standards. O utf-8 é um deles de uso cada vez mais generalizado.\\

Por defeito o WingIDE salva os ficheiros de código em utf-8 e, por isso, estamos à vontade com a língua portuguesa. Precisamos no entanto indicar no início do ficheiro que estamos a usar essa codificação. O modo de o fazer é usar:

#-*- encoding: utf-8 -*-

Acontece porém que, devido a um erro lamentável no IDE se colocarmos esta linha, quando mandamos correr o programa obtemos uma mensagem de erro! A solução passa por retirar a dita linha. Mas atenção!!! Se estiver a importar o ficheiro sem a linha ... dá erro. E terá que acrescentar a dita. Bizarro, não?

Enquanto não tiverem resolvido o problema teremos que saber se colocamos ou não a indicação expressa da codificação em função do modo como vamos usar o ficheiro: correr (não) ou importar (sim).

Programação com Python