Resolução de Problemas

Resolver problemas é uma arte ... com ciência. Muita gente se tem debruçado sobre a questão. Um matemático já desaparecido, George Polya , publicou um pequeno livro muito interessante, How to solve it, onde enunciou as quatro fases de resolução de problemas. Cada uma tem vários aspectos a considerar e é a tradução desses princípios que aqui deixamos.




1-COMPREENDER O PROBLEMA
- Qual é a incógnita? Quais são os dados? Qual é a condição?
- É possível satisfazer a condição? A condição é suficiente para determinar a incógnita? Ou é insuficiente? Ou redundante? Ou contraditória?
- Desenha uma figura. Introduz uma notação adequada.
- Separa as diversas partes da condição. É possível escrevê-las?
 
2-ESTABELECER UM PLANO
- Já viste este problema antes? Ou já viste o mesmo problema apresentado sob uma forma ligeiramente diferente?
- Conheces um problema relacionado? Conheces um teorema que lhe poderia ser útil?
- Olha bem para a incógnita! Pensa num problema familiar que tenha a mesma incógnita ou outra semelhante.
- Eis um problema relacionado com o teu e já antes resolvido. É possível utilizá-lo? É possível utilizar o seu resultado? É possível utilizar o seu método? Deve-se introduzir algum elemento auxiliar para tornar possível a sua utilização?
- É possível reformular o problema? É possível reformulá-lo ainda de outra maneira? Volta às
  definições.
 
3-EXECUTAR O PLANO
- Ao executares o teu plano de resolução, verifica cada passo.
- É possível verificar claramente que cada passo está correcto?
- É possível demonstrar que ele está correcto?
 
4-AVALIAR
- É possível verificar o resultado? É possível verificar o raciocínio?
- É possível chegar ao resultado por um caminho diferente? É possível perceber isto num relance?
- É possível utilizar o resultado, ou o método, para outro problema?

Entradas e Saídas

Um programa, qualquer programa, é um manipulador de objectos. Ao programador compete tomar várias decisões. A primeira, é determinar quais são e como vão ser comunicados ao programa, os objectos a manipular e, ainda, como é que este devolve o resultado. A segunda, claro está, é saber como transforma os dados no resultado.


Suponhamos o seguinte exemplo: desenvolva um programa que, dado o comprimento dos dois lados de um triângulo rectângulo que formam um ângulo de 90 graus (os catetos), determina o comprimento do terceiro lado, a hipotenusa. Neste exemplo, os objectos de entrada (os dados) são o comprimento dos dois lados e, o objecto à saída (o resultado) é o comprimento da hipotenusa. Em relação à primeira questão acima referida, em geral, nós temos três possibilidades para introduzir os dados e outras três para os por cá fora. A figura ilustra a situação.



Para a entrada temos as seguintes três hipóteses:

• através dos parâmetros de entrada: def hipotenusa(lado_1,lado_2): ...


• recorrendo à instrução de entrada no interior do programa: lado_1=input('lado 1 sff: ')


• ler, a partir do interior do programa, de um ficheiro externo:fich=open('lados.txt','r')

Para a saída, mais três hipóteses:

• através da instrução de fim do programa: return h


• recorrendo à instrução de impressão para o canal de saída: print h


• escrever, a partir do interior do programa, num ficheiro externo, que foi aberto para escrita:fich.write(h)

Todas estas possibilidades de entrada saída, podem ser combinadas entre si! A decisão sobre o que escolher depende da natureza do problema e dos dados, e do local onde estes podem ser obtidos. Esqueçamos por agora os ficheiros (a tratar em breve nas aulas teoricas), e concentre-mo-nos nas outras quatro alternativas. Do lado da entrada a opção deve ser guiada pela existência ou não de interactividade entre o programa e o utilizador. Do lado da saída, a decisão depende de saber quem vai precisar do resultado. Se tivermos liberdade nestas matérias a regra a seguir é a de optar pelo que caso mais geral e menos dependente do utilizador. Se o meu programa puder obter os dados de outro programa e se imprimir o resultado não for o objectivo, então o par parâmetros de entrada / return deve ser a nossa opção.

Em função do que foi dito o seu programa terá a seguinte assinatura:

def hipotenusa(lado_1,lado_2):
   --- código aqui
   return hipo

Passemos agora à segunda questão que foi mencionada no início: como transformar os dados no resultado. E isto é o domínio privilegiado da área de resolução de problemas. Neste caso simples é fácil identificar os dados, a incógnita e o modo como se relacionam através do Teorema de Pitágoras: o quadrado da hipotenusa é igual à soma do quadrado dos catetos.

h^2 = \sqrt{l_1^2 + l_2^2)

Logo a nossa solução é baseada nesse pressuposto. Mas antes de apresentarmos a solução pensemos mais um pouco na frase raiz quadrada da soma do quadrado dos catetos. Ela diz-nos que precisamos de operações auxiliares. Em programação, isso leva normalmente ao uso de operações pré-definidas na linguagem ou à utilização (ou definição) de programas auxiliares. Posto tudo isto, aqui vai então a nossa solução:

import math

def quadrado(n):
    return n**2

def soma(n1,n2):
    n = n1 + n2
    return n

def hipotenusa(x,y):
    hipo = math.sqrt(soma(quadrado(x), quadrado(y)))
    return hipo

def main():
    lado_1 = input('lado 1: ')
    lado_2 = input('lado 2: ')
    print 'Hipotenusa: ',hipotenusa(lado_1, lado_2)
    
if __name__ =='__main__':
    main()

Que comentários breves se nos oferece fazer? As definições explícitas para as operações quadrado e soma podem ser reutilizadas noutros contextos. No caso de devolverem o resultado por impressão e não por return, essa possibilidade seria perdida! Usamos o método pré-definido sqrt do módulo math, o que obriga à sua importação. Finalmente, construímos um programa principal, de nome main que isola e faz de interface com o potencial utilizador. É aqui que optamos, neste caso, por introduzir os dados e imprimir o resultado. Estamos assim perante um modelo de programação geral!

O que devemos evitar?

import math 

def hipotenusa():
    lado_1 = input('lado 1: ')
    lado_2 = input('lado 2: ')
    print math.sqrt(lado_1 **2 + lado_2 **2)
    
hipotenusa()

Nesta solução temos interactividade na entrada dos dados. Isso impede o nosso programa de receber as suas entradas de outro programa. Ao usarmos a instrução de impressão também não podemos auxiliar outros programas que precisam deste cálculo. Perdemos ainda modularidade ao não usar programas independentes para o cálculo da soma e do quadrado. Mas não ganhamos nada? Sim , ganhamos! Associámos um nome a três instruções. Assim, cada vez que for preciso basta usar o nome e não precisamos escrever as ditas instruções. Atenção no entanto. Isto é apenas um exemplo ilustrativo do conceito. Cada problema é um caso e deve ser ponderado sempre a melhor maneira de introduzir e devolver os objectos.

O que não devemos usar! De todo!

import math 

lado_1 = input('lado 1: ')
lado_2 = input('lado 2: ')
print math.sqrt(lado_1 **2 + lado_2 **2)

O que ganhamos nesta abordagem? Nada.

Errar é humano...

Todos nós erramos. E quando estamos a aprender uma nova linguagem de programação, ou mesmo a aprender a programar, os erros são frequentes. E muitas vezes ... básicos. Eis alguns exemplos.

1. Definir uma função e depois nada fazer, esperando que ela por milagre se lembre do que queremos resolver em concreto. É a dualidade definir/usar que nos escapa.

2. Importar um módulo com a instrução "import [nome do módulo]" para usar uma operação [nome da operação] e não qualificar a operação com o nome do módulo no momento do seu uso.

>>> import math
>>> sin(5)
Traceback (most recent call last):
  File "<string>", line 1, in <fragment>
NameError: name 'sin' is not defined
>>> math.sin(5)
-0.95892427466313845
>>> 

3. Não ter em atenção as consequência da mutabilidade de alguns objectos. Alguns dos métodos modificam o objecto mas não devolvem nenhum valor.

>>> a = [1,2,3]
>>> b = a.append(4)
>>> b    # -----> b = None!!
>>> a
[1, 2, 3, 4]
>>> b=a # ----> assim pode-se fazer!
>>> b
[1, 2, 3, 4]
>>> 

4. Não ter em atenção que o código deve estar correctamente alinhado.

# caso 1
def dobros(n):
    for i in range(n):
        d = 2 * i
        print d,
        
dobros(4)
>>> 0 2 4 6

# caso 2
def dobros(n):
    for i in range(n):
        d = 2 * i
    print d, # <----- Aqui
        
dobros(4)
>>>  6

5. Referir o nome de um objecto que não foi ainda criado.

Python 2.6.2 (r262:71600, Apr 16 2009, 09:17:39) 
[GCC 4.0.1 (Apple Computer, Inc. build 5250)]
Type "help", "copyright", "credits" or "license" for more information.
>>> a
Traceback (most recent call last):
  File "<string>", line 1, in <fragment>
NameError: name 'a' is not defined
>>>

6. Tentar fazer operações impossíveis.

>>> 5 + 'a'
Traceback (most recent call last):
  File "<string>", line 1, in <fragment>
TypeError: unsupported operand type(s) for +: 'int' and 'str'
>>> 5 / 0 
Traceback (most recent call last):
  File "<string>", line 1, in <fragment>
ZeroDivisionError: integer division or modulo by zero
>>>

Nalgumas situações o Python avisa-nos do erro. Nestes casos deve ler com atenção a mensagem de erro. E por hoje é tudo.
Há muitos mais erros! Quer contribuir com o seu erro preferido?? É só mandar para o blogue!

Problema 4.16

Por definição os netos são os filhos dos filhos. Usando o princípio da programação descendente, por camadas de abstracção, admitamos que sabemos com determinar os filhos de alguém. então uma solução para o nosso problema pode ser facilmente equacionada:

def netos(dicio,progenitor):
    """ Lista netos."""
    desc1 = filhos(dicio,progenitor)
    if desc1:
        net = []
        for elem in desc1:
            desc2 = filhos(dicio,elem)
            if desc2:
                net = net + desc2
    else:
        return []
    return net

Na linha 3, calculamos os filhos. Como o faremos em concreto depois se verá. Para ter netos é preciso que o progenitor tenha ... filhos (teste na linha 4)! Caso tenha, usamos o padrão acumulador para determinar os filhos de cada filho e juntar tudo numa lista chamada net (linhas 5 a 9). Passemos então ao problema de saber quem são os filhos de alguém. Questão fácil dada a organização do dicionário.

def filhos(dicio,progenitor):
    """ lista dos filhos."""
    res= dicio.get(progenitor,None)
    return res

Resolvido o problema pensemos um pouco mais. Não seria interessante uma solução que seguisse de perto a definição? Claro que sim. Algo como:

def netos(dicio ,progenitor):
    """ Lista dos netos."""
    netos = filhos(dicio,filhos(dicio,progenitor))
    return netos

Mas não funcionaria. Porquê? Bem, um olhar atento diz-nos porquê: a função filhos recebe uma cadeia de caracteres (um nome) e devolve uma lista (a lista dos filhos). Assim, na segunda vez que se utilizasse filhos daria erro pois estava a ser tentado executar a definição com um argumento lista em vez de uma cadeia de caracteres. A solução passa por fazer com que a definição filhos funcione com listas de cadeias de caracteres. Este é um exemplo de outro mecanismo importante para resolver problemas: generalização!

def filhos(dicio,lista_progenitores):
    lista_filhos = []
    for filho in lista_progenitores:
        lista_filhos.extend(dicio.get(filho,[]))
    return lista_filhos

Notar o uso do método extend, pois agora vamos acumular numa lista elementos que, também eles aparecem em listas. Notar também a necessidade de usar a lista vazia como default do get. O leitor atento dirá: mas agora deixa de funcionar a definição de netos pois no início só há um progenitor!! Mas isso resolve-se facilmente: a primeira chamada de filhos, dentro da chamada de netos tem como segundo argumento uma lista com um elemento: o progenitor. E chegamos à versão completa.

def netos(dicio ,progenitor):
    """ Lista dos netos."""
    netos = filhos(dicio,filhos(dicio,[progenitor]))
    return netos

def filhos(dicio,lista_progenitores):
    lista_filhos = []
    for filho in lista_progenitores:
        lista_filhos.extend(dicio.get(filho,[]))
    return lista_filhos

Problema 4.15

Estes problemas sobre árvores genealógicas baseiam-se numa organização simples em dicionário: a chave é um nome, o valor a lista dos descendentes. Neste problema, o nosso objectivo é determinar de duas pessoas são irmãs. Por definição, sê-lo-ão se tiverem o mesmo progenitor. Com a organização definida, encontrar o progenitor de uma pessoa corresponde a encontrar a chave associada a um elemento da lista correspondente ao valor. Não é o modo natural de procurar num dicionário e, por isso, é preciso alguma ginástica.

def progenitor(dic, nome):
  """ Devolve o progenitor do nome."""
  for chave, valor in dic.items():
      if nome in valor:
          return chave
  return None

A solução encontrada mostra como percorremos os itens do dicionário na procura da chave. Como necessitamos das duas componentes do par, a procura faz-se recorrendo a dic.items(). Obtemos assim um par (chave, valor). É por este último facto que podemos colocar dois nomes entre o for e o in! Deste modo, se em cada etapa do ciclo se aceder a um par, por exemplo, ('jorge', ['luis','ana','vasco']), chave fica associada ao primeiro elemento, neste exemplo a 'jorge', e o valor ao segundo, neste caso ['luis','ana','vasco']. Depois é só fazer o teste (linha 4) e devolver o resultado mal este seja encontrado (linha 5). Relembro que mal é encontrada uma instrução de return o programa termina devolvendo o valor associado.

Com este programa auxiliar, é agora trivial resolver a nossa questão inicial.

def irmaos(dic,nome1,nome2):
  """ Têm o mesmo progenitor?"""
  prog1 = progenitor(dic, nome1)
  prog2 = progenitor (dic,nome2)
  return prog1 == prog2

Este exemplo simples serve para ilustrar um princípio básico da programação: a abstracção. Posso começar pela definição e construir a minha solução abstracta que pressupõe, neste caso, que tenho o comando progenitor. Implemento depois o comando, caso ele não exista. Esta forma de programar, do topo para a base, por recurso a camadas de abstracção, recebeu o nome de Programação Descendente.

Ver ... para crer

Python é uma linguagem facilmente expansível por recurso à importação de módulos. Um desses módulos que permite fazer simulações 3D chama-se visual ( descarregar aqui ). O módulo faz parte da distribuição VPython. Lá encontrará muita informação adicional.

O exemplo que mostramos é retirado do tutorial e mostra como podemos colocar uma bola aos saltos num mundo um pouco idealizado mas com uma gravidade igual à da terra.

import visual

def bola_saltitante():
   """Demostra o uso do módulo visual."""
   soalho = visual.box(pos=(0,0,0),length= 4,height=0.5,width=4, color= visual.color.blue)
   bola = visual.sphere(pos=(0,4,0),radius=1,color=visual.color.red)
   bola.velocity= visual.vector(0,-1,0)
   dt = 0.01
  
   while True:
       visual.rate(100)
       bola.pos = bola.pos + bola.velocity * dt
       if bola.y < bola.radius:
           bola.velocity.y = -bola.velocity.y
       else:
           bola.velocity.y = bola.velocity.y - 9.8 * dt

if __name__ =='__main__':
   bola_saltitante()

O exemplo mostra como se definem dois objectos: o soalho e a bola. A bola cai paralelamente ao eixo dos Ys. Quando atinge o soalho inverte o sentido do deslocamento.

Em baixo um pequeno vídeo caseiro, feito a horas impróprias sem grandes preocupações. Espero que apreciem a música de fundo!

Tipos... com Classe!

Já nos aconteceu a todos ter que preencher formulários, electronicamente ou não. Por exemplo, a declaração de IRS. Esses formulários têm vários campos que devem ser preenchidos. Uns são obrigatórios (nome, número de contribuinte), outros não (deduções fiscais). Pode acontecer que em parte o formulário já venha preenchido, por exemplo, com base em informação retirada do nosso computador. Depois de ser por nós preenchido, os formulários são tratados por um diligente funcionário, podendo eventualmente ser corrigidos, ou seja alterados. Temos assim que um mesmo padrão (o formulário) dá origem a várias instanciações (os formulários parcialmente preenchidos), que por sua vez são completadas por cada um de nós de forma diversa. Finalmente podem, posteriormente, ser objecto de modificações. Mas o que é que tudo isto tem a ver com computadores e com programação? Bem, de um modo directo, muito pouco. Mas como metáfora a ideia de formulário,o seu preenchimento e manipulação pode ser interessante.

Já sabemos que os objectos em programação têm atributos. Por exemplo, identidade, valor e tipo. Assim, 5 e 7 são dois objectos numéricos, de valor 5 e 7, respectivamente, com uma identidade própria (a zona da memória onde estão guardados), e um tipo (inteiro neste caso). Em relação aos tipos também já conhecemos vários: inteiros, inteiros longos, vírgula flutuante, complexos, booleanos, cadeias de caracteres, listas, tuplos e dicionários. A consideração do tipo de um objecto condiciona o valor que ele pode ter ( e o modo como fica armazenado também). O tipo funciona como um formulário vazio. Ao criar um objecto de um determinado tipo estamos a concretizar o modelo, ou formulário, definido pelo tipo. Quando manipulamos o objecto é como se estivéssemos a completar ou modificar o nosso formulário. A forma de o fazer é através do recurso a funções, que por serem específicas dos objectos do tipo, recebem o nome de métodos. Em Python os tipos são implementados recorrendo a classes. Um conceito que por agora iremos deixar por definir. Fique-se apenas com a ideia de que um tipo = classe = modelo. A instanciação da classe dá origem a objectos. Essa instanciação, ou criação de um objecto do tipo, ocorre graças ao recurso a um método especial que, por tal motivo, se designa por construtor. A listagem que apresentamos de seguida ilustra estes factos.

>>> i = int()
>>> i
0
>>> l = long()
>>> l
0L
>>> f = float()
>>> f
0.0
>>> c = complex()
>>> c
0j
>>> b = bool()
>>> b
False
>>> c = str()
>>> c
''
>>> s = str()
>>> s
''
>>> c = complex()
>>> l = list()
>>> l
[]
>>> t = tuple()
>>> t
()
>>> d = dict()
>>> d
{}
>>> type(i)
<type 'int'>
>>> type(b)
<type 'bool'>
>>> type(c)
<type 'complex'>
>>> type(l)
<type 'long'>
>>> type(d)
<type 'dict'>
>>> type(l)
<type 'list'>
>>> type(t)
<type 'tuple'>
>>>

Desde logo uma observação: o nome do construtor é igual ao nome do tipo. Claro que podemos chamar o construtor com um objecto, como no nosso formulário parcialmente preenchido. Eis alguns exemplos.

>>> i = int(5)
>>> i
5
>>> l = list((1,2,3))
>>> l
[1, 2, 3]
>>> d = dict(((1,'a'),(2,'b')))
>>> d
{1: 'a', 2: 'b'}

Não deixam de ser situações curiosas. Estamos mais habituados a fazer simplesmente:

>>> i = 5
>>> i
5
>>> l = [1,2,3]
>>> l
[1, 2, 3]
>>> d = {1:'a',2:'b'}
>>> d
{1: 'a', 2: 'b'}

Mas isto é apenas uma comodidade de notação que a linguagem nos oferece. Como há outras. Veja-se o exemplo:

>>> (5).__add__(3)
8
>>> 5 + 3
8
>>>

Este exemplo mostra que 5 é um objecto, instância da classe (= tipo) int, e que podemos por isso aplicar-lhe o método __add__ que foi definido na classe.

Um outro aspecto é a conversão entre tipos. Essa conversão pode ser feita automaticamente pelo sistema ou, expressamente por nós.

>>> 1/2
0
>>> 1.0/ 2
0.5
>>> 4.3 / (4 + 5j)
(0.41951219512195126-0.52439024390243905j)
>>> i = 3
>>> f = 4.5
>>> c = complex(3,4)
>>> l = [1,2,3]
>>> ccar = 'ernesto costa'
>>> lcar = ['abc','123']
>>> int(f)
4
>>> float(i)
3.0
>>> ccar.split()
['ernesto', 'costa']
>>> '--'.join(lcar)
'abc--123'
>>> complex(i)
(3+0j)
>>> complex(f)
(4.5+0j)
>>> list(ccar)
['e', 'r', 'n', 'e', 's', 't', 'o', ' ', 'c', 'o', 's', 't', 'a']
>>> str(i)
'3'
>>>

As 6 primeiras linhas mostram conversões automáticas pelo sistema. Essas conversões ocorrem quando temos operações com objectos de tipos diferentes. Sempre que possível o de nível mais baixo é convertido no de nível mais elevado. Nas restantes somos nós que forçamos a conversão. Notar como os métodos split e join permitem passar de cadeias de caracteres a listas e vice versa. O leitor interessado pode aprofundar estas questões no manual da linguagem.

Termino referindo uma função (isinstance) que nos permite testar o tipo de um objecto. Isto aplica-se aos objectos pré-definidos bem como a todos os que os novos tipos definidos pelo utilizador como uma classe.

>>> isinstance(i,int)
True
>>> isinstance(c,complex)
True
>>> isinstance(l,list)
True
>>> isinstance(lcar,str)
False
>>>

Veja-se como o nome do tipo não tem plicas!

Problema 4.14

Os dicionários não têm ordem. No entanto, muitas vezes, interessa-nos ver ou apresentar os seus elementos por ordem. O caso mais complexo, é quando a ordem é pelos valores. Comecemos por mostrar a solução clássica.

import operator

def ordena_valor(d):
 """
 Apresenta um dicionario ordenado pelo valor. Retorna o resultado sob a 
 forma de lista
 """
 items = d.items()
 ordenado =sorted(items,key=operator.itemgetter(1))
 return ordenado

Como se pode ver, embora o código seja pequeno, aparecem muitas coisas novas. Desde logo, o módulo operator, essencial para resolver a questão. Esse módulo permite-nos usar o método itemgetter que vai a uma estrutura buscar um dos seus componentes. Como sabemos que os items de um dicionário são tuplos com duas componentes (a chave e o valor), temos que extrair a sua segunda componente (posição 1). Na linha está o essencial da solução. O método sorted, que actua sobre listas, recebe a lista dos pares (chave:valor) e como critério de ordenamento o segundo argumento do par (o valor) (key=operator.itemgetter(1)). E assim se vê como um problema complexo pode ser resolvido de modo rápido e claro ... quando se conhecem bem as operações facultadas pela linguagem e pelos seus módulos.

Problema 4.12

Vamos inverter um dicionário, trocando as chaves pelos valores e vice versa. Que questão bizarra podemos ter que resolver? O facto de chaves diferentes poderem ter valores iguais no dicionário inicial! Vejamos como o problema foi ultrapassado.

def inverte(dicio):
 """inverte um dicionario, i.e., as chaves passa a ser os valores e os 
 valores as chaves
 """
 aux = {}                           
 for key,value in dicio.items():
  if not aux.has_key(value):
   aux[value] = []            
  aux[value].append(key)
 return aux

Como se pode ver, cá reaparece o velho padrão: varrer o dicionários pelos seus elementos, e ir adicionando por etapas os elementos relevantes a um acumulador (aux). Como podemos ter agora diferentes valores para uma mesma chave, esse facto resolve-se colocando no campo valor uma lista. O teste if serve para distinguir os casos em que não existe ainda nenhum valor, das situações em que já há algo.

Problema 4.11

Pretende-se transformar uma cadeia de caracteres no seu equivalente em Código Morse. Eis a solução.

def string_morse(s):
 """ Converte uma cadeia de caracteres para Morse."""
 d={"A":".-", "B":"-...","C":"-.-.","D":"-..","E":".",
    "F":"..-.","G":"--.","H":"....","I":"..","J":".---","K":"-.-","L":".-..",
    "M":"--","N":"-.","O":"---","P":".--.",
    "Q":"--.-","R":".-.","S":"...","T":"-","U":"..-",
    "V":"...-","W":".--","X":"-..-","Y":"-.--","Z":"--.."}
 l= list(s.upper().replace('\n',''))
 lf=[]
 for char in l:
  lf.append(d[char])
 sf=''.join(lf)
 return sf

O que se pode dizer da solução? Em primeiro lugar, usamos um dicionário para estabelecer a correspondência entre cada caracter e o correspondente código (linha 3). De seguida, na linha 3, normalizamos a cadeia para maiúsculas, retiramos o caracter correspondente à mudança de linha e convertemos tudo numa lista de caracteres. O programa propriamente dito conjuga duas ideias já muito trabalhadas. A primeira, é o modo de varrer uma estrutura através de um ciclo. Neste caso, como se pretende substituir os caracteres é natural que a travessia se faça pelo conteúdo da lista e não pelos índices. A segunda, é o recurso a uma variável que funciona como acumulador, neste caso da solução, solução essa que vai sendo construída de modo progressivo em cada etapa do ciclo. É inicializada na linha 9, e actualizada na linha 11. Finalmente (linha 12), reconstruímos a cadeia de caracteres Morse.

Mini Teste # 1

As questões do mini teste #1 tinham um graus de dificuldade baixo. Aqui vai um esboço de solução.

Questão 1.

As cadeias de caracteres e as listas são tipos de objectos. Identifique de forma clara e sintética as suas semelhanças e as suas diferenças.

Resposta:

As cadeias de caracteres e as listas são colecções ordenadas de objectos. As listas são heterogéneas e mutáveis. As cadeias de caracteres são homogéneas e imutáveis.

Questão 2.

Explique o que acontece de modo claro, sintético e rigoroso, quando executa o comando: a= 5.

Resposta:

O nome "a" caso não exista é criado e passa a pertencer ao espaço de nomes corrente. Este nome fica associado ao objecto 5 através da identidade deste.

Questão 3.

O programa da listagem abaixo pretende criar e devolver a cópia de uma dada lista. No entanto não funciona na esmagadora maioria dos casos, podendo mesmo dar erro na sua execução}. Identifique o tipo do erro que o sistema comunica e explique a sua razão.

def minha_copia(lista):
 """
 Fabrica a cópia da lista "lista".
 """
 copia = []
 for i in range(len(lista)):
     copia = copia.append(lista[i])
 return copia

Resposta:

O método append devolve como valor o objecto "None". Assim, depois da primeira execução dentro do ciclo "copia" fica com o valor "None", pelo que na segunda iteração dá erro: na segunda pasagem o nome cópia estado associado ao objecto None, que não tem o método "append" definido. Para corrigir basta retirar a atribuição dentro do ciclo.

Questão 4.

Desenvolva um programa que dada uma lista de números devolva a soma dos seus números pares e a soma dos seus números ímpares. A listagem abaixo ilustra o que se pretende.

>>> lst = [1,4,7,9,3,2,8,5,6]
>>> # ---> Aqui o seu programa de nome pares_impares.
>>> pares_impares(lst)
(20, 25)
>>>

Resposta:

def pares_impares(lista):
 """
 Devolve o valor da soma dos números pares e o valor da soma
 dos números ímpares.
 """
 pares = 0
 impares = 0
 for i in range(len(lista)):
     if lista[i] % 2 == 0:
         pares = pares + lista[i]
     else:
         impares = impares + lista[i]
 return pares,impares

Problema 3.12

Queremos rodar uma imagem 90 graus no sentido dos ponteiros do relógio. Atendendo à representação matricial, o que sabemos é que a coluna 1 passa linha 1, a coluna 2 a linha 2, e assim sucessivamente. É essa questão que o problema seguinte resolve.

def roda_90(imagem):
imagem_aux = list()
# transpõe
for coluna in range(len(imagem[0])):
 nova_linha = list()
 for linha in imagem:
  nova_linha.append(linha[coluna])
 imagem_aux.append(nova_linha)
# inverte dentro das linhas
for linha in range(len(imagem_aux)):
 imagem_aux[linha] = imagem_aux[linha][::-1]

return imagem_aux

A estratégia utilizada consistiu em dois passos: primeiro, transpusemos a matriz (linhas 4 a 8), de seguida invertemos os elementos em cada linha (linhas 10 e 11). Transpor uma matriz significa que o elemento na posição (i,j) passa para a posição (j,i).

Problema 3.11

Esta questão envolve imagens a preto e branco representadas por listas de listas. Os valores podem ser 0 (branco) e 1 (preto). Na lista inicial cada um dos seus elementos (uma lista!) representa uma linha. Em cada linha os elementos representam os pixeis (preto ou branco). Criar um negativo obriga a transformar os pixeis brancos em pretos e vice-versa. Como são todos temos que percorrer, por certa ordem, todas as posições (pixeis) da imagem. Na realidade, uma lista de listas pode representar qualquer matriz e a nossa questão mais complexa é: como percorrer uma matriz? A resposta não é difícil: usar dois ciclos imbricados. É isso que o programa documenta.

import copy

def negativo(imagem):
copia = copy.deepcopy(imagem)
for linha in range(len(imagem)):
 for coluna in range(len(imagem[0])):
  if imagem[linha][coluna] == 0:
   copia[linha][coluna] = 1
  else:
   copia[linha][coluna] = 0
return copia

Notar que por razões de segurança (não queremos a imagem original estragada) trabalhamos sobre uma cópia. Para termos garantia absoluta de que a imagem original não é afectada usamos o módulo copy e, dentro deste, a função deepcopy. Não chega fazer apenas copia = lista[:]. Isto porque essa cópia seria apenas ao primeiro nível da lista original (shallow copy). Assim, se tivermos elementos mutáveis a esse nível podemos ter problemas. Como isso acontece no nosso caso (os elementos do primeiro nível são listas) e vamos alterá-los, então teríamos garantidamente problemas caso não se usasse uma cópia profunda (deepcopy) que copia a todos os níveis. Atente~se ainda como se faz a indexação. Neste caso, como é uma lista de listas (uma matriz), precisamos de dois índices. O primeiro, dá-nos a linha, o segundo, a coluna (dentro da linha escolhida). A notação copia[linha,coluna] daria erro.

Mas será esta a única maneira de proceder? Não. Podíamos por exemplo, não usar um if dentro dos dois ciclos.

import copy

def negativo_b(imagem):
copia = imagem[:] # just in case...
for linha in range(len(imagem)):
 for coluna in range(len(imagem[0])):
  copia[linha][coluna] = (imagem[linha][coluna] +1) %  2
return copia

Notar o código da linha 7.

Problema 3.9

O problema pede-nos para lançar dois dados numerados de 1 a 6, um certo número de vezes, reportando a percentagem de ocorrência de somas pares. Espero que se comece a perceber que há neste problema uma padrão simples: executar uma acção um certo número de vezes, número esse fixo, filtrar uma ocorrência (somas pares) e contar. Daí o programa:

import random

def lanca_dados(numero):
 """
 Lança dois dados um numero de vezes. Determina
 a percentagem de somas pares.
 """
 conta = 0
 for i in range(numero):
  primo = random.randint(1,6)
  secundo = random.randint(1,6)
  if ((primo + secundo) % 2) == 0:
   conta = conta + 1
 return float(conta)/ numero

Notar como foi feito o teste de número par: um número é par se o resto da sua divisão por 2 for 0.

Suponhamos agora que quero contar e mostrar. Preciso de um novo acumulador para guardar os resultados parciais que vão sendo gerados. É para isso que servem as listas!

import random

def lanca_dados(numero):
 """
 lança dois dados um numero de vezes. guarda resultados e determina
 a percentagem de somas pares.
 """
 resultados = list()
 conta = 0
 for i in range(numero):
  primo = random.randint(1,6)
  secundo = random.randint(1,6)
  resultados.append([primo,secundo])
  if ((primo + secundo) % 2) == 0:
   conta = conta + 1
 return float(conta)/ numero, resultados

A inicialização da lista é feita usando o construtor da lista list(). Podia-se ter feito resultados = []. É devolvido um tuplo com o par (percentagem, lista_resultados).

Problema 3.7

Continuemos com a nossa tartaruga mas agora para fazer um desenho por junção de pontos gerados aleatoriamente.

import cTurtle
import random

def gera_coordenadas(numero):
 """
       Gera aleatoriamente um numero de coordenadas.
 Cada coordenada será um par ordenado representado por um tuplo.
 """
 lista = []
 for indice in range(numero):
  x = random.randint(-100,100)
  y = random.randint(-100,100)
  lista.append((x,y))
 return lista

def figura(lista_coordenadas):
 """
 Desenha uma figura unindo as coordenadas da lista.
 """
 tartaruga = cTurtle.Turtle()
 tartaruga.up()
 ponto_inicial = lista_coordenadas[0]
 tartaruga.goto(ponto_inicial)
 tartaruga.down()
  
 for i in range(1,len(lista_coordenadas)):
  tartaruga.goto(lista_coordenadas[i])
 tartaruga.goto(ponto_inicial) # -- fecha desenho
  
 tartaruga.ht()

Alguns comentários. Em primeiro lugar usámos um programa para gerar pontos de modo aleatório. No desenho da figura, criámos um objecto do tipo tartaruga (linha 20). Este modo de criar um objecto pode ser usado com outros tipos de objectos. Por exemplo podemos usar algo como minha_lista = list(). Tipicamente usamos uma definição com o nome do tipo e sem argumentos. quando falarem de programação orientada aos objectos ficarão a saber que se trata de usar o construtor de uma classe. De seguida posicionamos a tartaruga e preparamos a caneta (linhas 21 a 24). Finalmente desenhamos, sem esquecer de fechar a figura (linha 28). Eis uma hipótese de figura.

Problema 3.6

O módulo cTurtle permite controlar uma tartaruga e a sua caneta que se movimentam numa tela.Em relação à caneta podemos levantá-la (up()) ou baixá-la (down()). Em relação à tartaruga podemos fazer várias coisas: torná-la visível (showturtle()) ou invisível (hideturtle()), controlar a sua orientação (setheading(angulo)), posicioná-la na tela (goto(pos)), entre outras coisas. Podemos ainda fazê-la caminhar para a frente (fiorward(valor)) ou para trás (backward(valor)), rodar para a direita (right(valor)) ou para a esquerda (left(valor)). Para conhecer tudo deve-se importar o módulo e inspeccionar o seu conteúdo com os comandos dir(cTurtle) e com help(cTurtle.nome_do_comando) .

Com comandos tão simples é possível fazer muitos desenhos e animações. Vejamos como se desenha uma espiral semelhante à da figura.

Para isso vamos definir uma função que desenha um quadrado com o canto inferior esquerdo numa dada posição, com uma orientação inicial bem definida e com um certo comprimento para o lado. uma vez isso concretizado, é fácil desenhar a espiral desenhando sucessivos quadrados em que o lado vai aumentando e o mesmo se passando com a orientação inicial.

import cTurtle

def quadrado(lado,pos, angulo):
"""
Desenha um quadrado com o comprimento de lado, o vértice inferior
esquerdo em pos e  direção inicial angulo.
"""
# Preparação
cTurtle.up()
cTurtle.goto(pos)
cTurtle.setheading(angulo)
cTurtle.down()

# desenha quadrado
for conta in range(4):
 cTurtle.forward(lado)
 cTurtle.right(90)
cTurtle.hideturtle()

def espiral(num_quad, lado_inic, incr_lado, pos, angulo_inic, incr_angulo):
"""
Desenha uma espiral de quadrados.
"""
lado = lado_inic
angulo = angulo_inic
for i in range(num_quad):
 quadrado(lado, pos, angulo)
 lado = lado + incr_lado
 angulo = angulo + incr_angulo

 cTurtle.mainloop()

Descubra o modo como se alterou a cor. Pode também alterar, por exemplo, a forma da tartaruga, a velocidade a que o desenho é feito, e muitas mais coisas.

Problema 3.1

Este é um problema muito fácil em todas as suas alíneas. Chama a atenção para a necessidade de sabermos o que existe, de básico, na linguagem Python sobre listas, para assim evitarmos alguns incómodos. Comecemos pela alinea 5. em que nos é pedido para determinar o menor e o maior elemento existente numa lista. Admitamos que se trata de números. A solução trivial é:

def idades_5c(lista):
   return max(lista), min(lista)

Mas,e se não soubermos que essas operações primitivas existem? Programamos nós a solução!

def idades_5d(lista):
   menor = lista[0]
   maior = lista[0]

  for indice in range(1,len(lista)):
    if lista[indice] < menor :
         menor = lista[indice]
         if lista[i] > maior:
            maior = lista[indice]
   return maior,menor

O código acima começa por ter um pressuposto: alista tem pelo menos um elemento. Altere por forma a que essa limitação desapareça. Começamos por aceitar que o maior e o menor coincidem com o primeiro elemento. Depois, percorremos todos os elementos, de modo sequencial, da esquerda para a direita e comparamos com os nossos maior e menor. Actualizamos de acordo. A alínea 6. (cálculo da soma dos valores na lista) é ainda mais fácil.

def idades_6a(lista):
return sum(lista)

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

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

A primeira solução (6a), é directa e emprega a operação sum. A segunda (6b), usa um acumulador, a variável soma. Começa por ser zero e em cada etapa do ciclo é actualizada com o acréscimo de mais um elemento. A terceira solução (6c), é equivalente à anterior, mas em vez de percorrer a lista pelos índices, vai buscar directamente os elementos, pois as listas são objectos iteráveis. A questão 7. pretende determinar quantos e quais os elementos inferiores a um outro elemento dado como referência. Uma vez mais temos uma questão com um ciclo e, no seu interior, um filtro, o if.

def idades_7(lista,ref):
      quantos=0
      quais  = []
      for elem in lista:
           if elem < ref:
                quantos= quantos + 1
                quais=quais + [elem]
      return quantos,quais
 

A mesma ideia. Um ciclo e um filtro. Dois acumuladores: um para a contagem, e outro para guardar os elementos que satisfazem a condição. Finalmente, a questão 8.: existe um elemento com 17 anos?

def idades_8a(lista):
    return 17 in lista

def idades_8b(lista, idade):
     return idade in lista

def idades_8c(lista, idade):
   tem_idade = False
   for elemento in lista:
   if elemento == idade:
      tem_idade = True
  return tem_idade

A primeira solução é a trivial: usa o que existe. A segunda, é semelhante só que generaliza. Notar que tal se traduziu pela incorporação de mais um parâmetro. A última (8c), responde à necessidade de substituir o teste in. Como nas outras situações, usámos um ciclo, percorremos toda a lista, fazemos um teste que, se for positivo, nos leva a alterar o valor de uma variável que serve de bandaeira (flag).

Como se pode ver todos estes exemplos seguem um padrão semelhante!!

De que massa são feitos os programas

Programar é uma actividade que nos obriga a usar mecanismos de abstracção. Deste modo produzimos código modular, reutilizável e capaz de resolver problemas mais gerais. Um dos mecanismos fundamentais de abstracção em programação são as definições. Têm a forma geral:

def [nome]([lista de parâmetros]):
   [corpo]

É pois preciso usar a palavra reservada def seguida do nome que demos ao programa, seguido de um parênteses de abertura, seguido da lista dos parâmetros- eventualmente vazia, separados por vírgulas, seguida do parênteses de fecho, seguida de dois pontos. Uff!! Isto constitui o chamado cabeçalho da definição. Na linha seguinte, e avançado uma posições para a direita, vem o corpo do programa. Sem isto a definição está mal feita e dará erro de sintaxe. Ao criarmos uma definição, internamente é feita a associação do nome do programa com um objecto que representa a definição. É pois semelhante ao que se passa quando usamos a instrução de atribuição. A listagem que se segue ilustra esse facto.

>>> def dobro(numero):
...  """ Calcula o dobro do múmero. """
...  return 2 * numero
...
>>> dobro
<function dobro at 0xccf870>
>>> id(dobro)
13432944
>>> type(dobro)
<type 'function'>
>>>

Uma definição é um objecto!

Mas não basta definir é preciso usar!!! Isso faz-se chamando o programa pelo seu nome (a definição neste caso) e associando aos parâmetros os argumentos (este últimos, colocados de forma ordenada e separados por vírgulas, entre parênteses e a seguir ao nome da definição). Os argumentos podem ser objectos ou nomes associados a objectos:

>>> dobro(5)
10
>>> x=7
>>> dobro(7)
14
>>>

Também aqui o processo de ligação dos objectos aos parâmetros, ou dos nomes de objectos aos parâmetros, é feito por associação entre identidades. No caso de eu fazer dobro(5) é o objecto 5 que fica associado localmente na definição, ao nome numero; no caso da chamada dobro(x) é na mesma a identidade do objecto, que está associado ao nome x, que é comunicada (associada) ao parâmetro numero.

Mas repetimos à exaustão: é preciso definir e usar as definições. Senão nada se passará (definir sem usar) ou teremos um erro (usar sem estar definido).

Mas regressemos ao corpo dos programas. São formados essencialmente por instruções que vão, durante a execução, alterando o estado da computação. Podem ser divididas em dois grandes grupos: as que alteram a memória e as instruções de controlo. As instruções que alteram a memória são de três tipos: a atribuição, entrada e saída. As de controlo subdividem-se em instruções sequenciais, condicionais e de repetição.

A instrução de atribuição já é uma velha conhecida. O mesmo se passa com a instrução de entrada input() e o comando de saída print. No caso das instruções de controlo, a sequência, em Python é dada implicitamente pelo alinhamento das instruções. Assim duas instruções alinhadas e consecutivas no código são executadas em sequência. Já as instruções condicionais têm três variedades: uma via, duas vias ou vias múltiplas. A listagem ilustra as três alternativas.

# uma via
if [condição]:
   [corpo-sim]

# duas vias
if [condição]:
   [corpo-sim]
else:
   [corpo-não]

# vias múltiplas  
if [condição]:
   [corpo-1]
elif [condição]:
   [corpo-2]  
...
elif [condição]:
   [corpo-n]
else:
   [corpo-final]

No primeiro caso, é executado as instruções do [corpo-sim] apenas se a [condição] for verdadeira. No segundo caso, é executado um dos corpos de acordo com o valor lógico da [condição]. Finalmente, no terceiro caso, é executado o corpo correspondente à primeira (pela ordem de escrita) condição que é verdadeira. Se nenhuma for verdadeira é executada incondicionalmente a [condição-final].

Terminemos com as repetições que podem ser de dois tipos: fixas ou variáveis.

# fixo
for [nome] in [objecto-iterável]:
   [corpo]
# variável   
while [condição]:
   [corpo]

As repetições fixas são executadas em geral um número fixo de vezes. Na repetição de ordem n o [nome] fica associado ao objecto de ordem n do [objecto-iterável]. Cadeias de caracteres, listas, dicionários, tuplos e ficheiros são exemplos de tipos de objectos iteráveis. No caso dos ciclos variáveis, em geral, o [corpo] só é executado de forma repetida enquanto a [condição] for verdadeira. Exemplos triviais:

# fixo
for i in [0,1,2]:
   print i
# variável   
j = 3
while j <5
    print j
    j = j + 1

Notar que na repetição variável algo tem que modificar a situação da condição, sob pena de podermos ter um ciclo eterno.

Porque dizemos acima em geral? Porque em Python, existem algumas instruções que quebram a ordem natural de execução. Por exemplo, é possível abandonar um ciclo for antes de ele completar o número de repetições previsto. Mas isso fica para outra altura...

Tuplos

Temos vindo a falar de vários tipos de objectos. Por exemplo, em tempos recentes, falámos de dicionários. Se eu tiver um dicionário posso perguntar pelos seus itens, isto é, pelos seus pares (chave, valor). A listagem seguinte ilustra essa possibilidade.

>>> dicio_idades ={'Ernesto': 56,'Ana':36,'Pedro':20}
>>> dicio_idades.items()
[('Pedro', 20), ('Ernesto', 56), ('Ana', 36)]
>>>

Mas o que está dentro da lista? Os pares (chave,valor) numa notação diferente do visto até aqui. Esses novos objectos chamam-se tuplos. Os tuplos são colecções ordenadas de referências para objectos. São ainda, heterogéneas e imutáveis. São semelhantes às cadeias de caracteres, embora heterogéneas, e são semelhantes às listas, embora imutáveis. A tabela seguinte mostra as características dos objectos já referidos.

Perante estas características é natural que encontremos muitas das operações que já nos são familiares. Vejamos isso através de uma sessão simples.

>>> t1 = (1,'eu',50.3,'ah!ah!')
>>> t1
(1, 'eu', 50.299999999999997, 'ah!ah!')
>>> type(t1)
>>> t2 = tuple()
>>> t2
()
>>> t3 = (4,)
>>> t3
(4,)
>>> t4 = (4)
>>> t4
4
>>> 4 * t3
(4, 4, 4, 4)
>>> 4 * t4
16
>>> t1[2]
50.299999999999997
>>> t1[1:3]
('eu', 50.299999999999997)
>>> t5 = (1, (2,3), 4)
>>> t5[1][1]
3
>>> len(t1)
4
>>> t1 + t3
(1, 'eu', 50.299999999999997, 'ah!ah!', 4)
>>> 'eu' in t1
True
>>> t1.index('eu')
1
>>> t1.count('eu')
1
>>> l1 = [1,2,3]
>>> l2 = ['a','b','c']
>>> zip(l1,l2)
[(1, 'a'), (2, 'b'), (3, 'c')]
>>> tuple (zip(l1,l2))
((1, 'a'), (2, 'b'), (3, 'c'))
>>> t6 = (23,13,44,7,22,3)
>>> sorted(t6)
[3, 7, 13, 22, 23, 44]
>>> t6
(23, 13, 44, 7, 22, 3)
>>> tuple(sorted(t6))
(3, 7, 13, 22, 23, 44)
>>> t6
(23, 13, 44, 7, 22, 3)
>>>

Vemos que existem tuplos vazios (linhas 6 e 7). Um tuplo só com um elemento obriga a colocar uma vírgula par não se confundir com uma expressão (linhas 8 a 17). As operações usuais de fatiamento são ilustradas nas linhas 18 a 24. Temos também o comprimento (linha 25), concatenação (linha 27) e teste de pertença (linha 29). As linhas 31 e 33 ilustram duas operações simples, na realidade métodos, que não alteram o objecto. A linha 37 mostra uma operação de zip: transformar duas listas de igual comprimento numa lista de pares ordenados. A operação tuplo(objecto) permite transformar certos objectos em tuplos. Podemos ordená-los (sorted), embora o objecto, porque imutável se mantenha inalterado. Caso queiramos que fique com a nova ordem temos que criar um novo objecto associando-o a um nome (eventualmente o mesmo!) (linha 42).

Podemos perguntar do porquê da existência de tuplos. Afinal eles podem ser substituídos por listas. Uma razão simples deriva do facto do criador da linguagem Guido Van Rossum ser um matemático de formação e por isso, para ele, um tuplo é uma associação de objectos enquanto uma lista é uma estrutura de dados. Mas há razões mais fortes para usar tuplos. A principal é que os tuplos sendo imutáveis não nos causam as preocupações das listas quando se trata modificações não desejadas. Acresce que podem ser usados como chaves de dicionários.

Problema 2.18 (REVISITAÇÃO)

A programação tem coisas curiosas. Muitas vezes, a nossa dificuldade em resolver o problema em mãos usando um programa, está na própria dificuldade de entendimento do enunciado. Noutras não: é o caso do problema da eliminação dos espaços em branco a mais numa cadeia de caracteres. Sabemos que queremos fazer um filtro, mas como ter a certeza de que a nossa solução contempla todos os casos?? O nosso problema/dificuldade é informático! É nestas situações que aprendemos a dar valor ao uso de processos e mecanismos conhecidos da programação.

Depois de ler alguns dos comentários vossos aqui no blogue à solução que apresentei e olhar para as variantes propostas (que têm alguns problemas), resolvi responder com outra variante. Nela usamos uma técnica frequente: em vez de analisar apenas um elemento, vamos controlar dois caracteres consecutivos. Isto porque, afinal, só dois (ou mais) espaços em branco é que são significativos para o filtro ser activado. Usamos ainda o já nosso conhecido padrão acumulador. Finalmente, recorremos a um paradigma fundamental da metodologia da programação: a indução.

Eis a nova solução:

def um_espaco(cad):
"""
Separa as palavras na cadeia deixando-as só com um espaço a separar.
Implementado por recurso a dois ponteiros.
Se quisermos retirar todos os espaços no fim
fazer primeiro cad = string.rstrip(cad)
"""
#cad = string.rstrip(cad)
anterior=" "
cad_aux=""
for  i in range(len(cad)):
 if not ((cad[i]==" ") and (anterior==" ")):
     cad_aux = cad_aux + cad[i]
 anterior = cad[i]
return cad_aux

Passemos aos comentários. Com esta solução só temos que explicitamente retirar os espaços em branco no final. No início a nossa solução retira-os (ver razão mais a baixo). Usamos um nome cad_aux para receber progressivamente os caracteres da sequência final filtrada. A inicialização é feita na linha 11 e a actualização na linha 14. Assim, começamos sem nada (cadeia vazia) e percorremos a cadeia original caracter a caracter (linha 12). Usamos um nome, anterior como memória do caracter imediatamente anterior ao que está a ser analisado. Se ambos forem o caracter branco (linha 13), então não fazemos nada. Caso contrário, passamos essa caracter para a cadeia final (linha 14). Note, que tanto pode ser um caracter normal, como o primeiro caracter branco! No fim do teste, e independentemente da acção tomada, avançamos no texto e actualizamos a memória (linha 15). É o facto de se iniciar a memória com o caracter branco que permite retirar todos os espaços à esquerda da cadeia.

Onde é que entra o pensamento indutivo nisto tudo? Repare-se na imagem seguinte.

Admitamos que numa dada etapa do nosso processo repetitivo temos a cadeia final parcial de acordo com a especificação. Anterior guarda o seu último valor. Tentamos aumentar essa cadeia de um elemento por análise do elemento seguinte na cadeia ainda por filtrar (posição i). E actuamos em conformidade. Se tudo correu bem no interior do ciclo, voltamos a ter a situação de que partimos, mas agora com mais um elemento da cadeia considerado (ver figura abaixo).

Dizemos que partimos de uma situação que o ciclo preserva. Daí , essa condição receber o nome de invariante de ciclo. Mas, se ainda se lembram, nós dissemos admita que... Para estabelecer inicialmente esta condição, isto é, antes do ciclo, basta fazer anterior = ' ', já que temos no início do ciclo i=0. Chama-se a esta técnica programação por indução por semelhança com as provas de proposições por indução matemática : prova-se para o caso de base, assume-se uma hipótese (indutiva) e prova-se que é verdade por o caso seguinte. Mas, as provas por indução matemática ficam para estudar na cadeira de Estruturas Discretas!

Problema 2.23

Trata-se do problema inverso do problema 2.22. Temos então a cadeia codificada de maneira que na primeira metade estão os caracteres das posições pares na cadeia original, e na segunda metade estão os caracteres das posições ímpares da cadeia original. Então tudo se resume a descobrir o meio da cadeia separar em duas partes e depois fazer a fusão de modo que a ordem par/ímpar seja preservada. Só que ... onde é o meio da cadeia? Se o número de caracteres for par não há problema. Mas se for ímpar? Bom ,neste caso na cadeia original os pares são mais um do que os ímpares. Com base nisso, chegamos à solução:

def descodifica_a(cad):
    """
    Descodifica uma cadeia codificada pelo método da separação em pares e
    impares.
    """
    cadeia = ''
    par = (len(cad) % 2) == 0 # número par ou ímpar de caracteres?
    if par:
        meio = len(cad) / 2
        inf = cad[:meio]
        sup = cad[meio:]
        for i in range(len(sup)):
            cadeia = cadeia + inf[i] + sup[i] # fusão
    else:
        meio = (len(cad) / 2) + 1 
        inf = cad[:meio]
        sup = cad[meio:]
        for i in range(len(sup)):
            cadeia = cadeia + inf[i] + sup[i]
        cadeia = cadeia + inf[-1]
    return cadeia

Et voilá! Dúvidas?

Problema 2.22

Este problema, embora marcado como difícil nas folhas, não é muito complexo. A ideia é simples. Pegar na cadeia, separar os caracteres pares para um lado (linha 6), e os ímpares para outro (linha 7), e depois juntar as duas cadeias (linha 9). Daí, sem mais o programa:

def codifica(cad):
    """
    Codifica a cadeia. Concatena a sequência dos caracteres nas posições pares
    com os caracteres na posições ímpares.
    """
    pares = cad[::2]
    impares = cad[1::2]
    return pares + impares

Problema 2.18

Antes de apresentar uma solução possível para este problema preciso fazer um passeio por algo conhecido por autómatos finitos de que irão ouvir falar na cadeira de Teoria da Computação I. De modo simples um autómato finito (AF) é uma máquina de estados. Quando se encontra num dado estado recebe um comando e reage a ele transitando de estado e, eventualmente, realizando alguma acção. Um exemplo concreto, embora redutor, é o caso de um interruptor. Tem associado dois estados de uma lâmpada, acesa e apagada . A transição de estado é comandada pela manipulação do interruptor. Se estiver acesa e eu carregar no interruptor passa para o estado apagada e apaga-se a luz. E inversamente, se estiver no estado apagada e se manipular o interruptor passa para o estado acesa e a luz acende-se. Claro que se estiver acesa e eu der o comando de acender, tudo se mantém nas mesma. E o mesmo para o caso de apagada. Normalmente visualizam-se os autómatos do modo ilustrado pela figura abaixo.

O que é que o nosso problema de pegar numa cadeia formada por palavras separadas por espaços de dimensão arbitrária, que queremos reduzir a apenas um, tem a ver com autómatos finitos?? Bom, se repararmos bem nós temos uma cadeia de caracteres. Podemos partir dela e criar uma outra, semelhante, na qual os espaços a mais foram retirados. É como se colocasse um filtro entre as duas cadeias. O filtro, analisa um caracter da primeira cadeia e decide se o deixa passar ou não. Isso depende de ter visto um caracter e, imediatamente a seguir, um outro. Tal facto é um sinal para se efectuar a filtragem. É como se tivéssemos um autómato finito com dois estados: num, não filtra, no outro filtra. A figura que mostramos a seguir pretende ilustrar a situação.

Foi com base nesta ideia que escrevemos o seguinte programa:

def um_espaco(cad):
 """
 Separa as palavras na cadeia deixando-as só com um espaço a separar.
 Implementado como um autómato de dois estados.
 Se quisermos retirar todos os espaços no início e no fim
 fazer primeiro cad = string.strip(cad)
 """
cadeia = " # cadeia vazia
estado = 1
for i in range(len(cad)):
    if estado == 1:
        if cad[i] == ' ': # espaço em branco!
            cadeia = cadeia + ' ' # espaço em branco!
            estado = 2
        else:
            cadeia = cadeia + cad[i]
    else: # estado igual a 2
        if cad[i] != ' ': # espaço em branco!
            cadeia = cadeia + cad[i]
            estado = 1
return cadeia

Analisemos o código. Partimos da cadeia cad e vamos construindo progressivamente a cadeia resultado em cadeia, que assim funciona como acumulador. Temos um nome, estado para identificar o estado em que nos encontramos: filtrar ou não. Partimos do estado de não filtrar (linha 9). Com o ciclo for (linha 10) vamos testar todos os caracteres. Depois: se estivermos no estado 1 e lermos um caracter branco , acrescentamos (é o primeiro!!) e transitamos para o estado 2 para continuar a observar (linhas (11 a 14). Se no estado 1 nos aparecer um caracter normal, fazemos uma cópia para a cadeia e continuamos no estado 1 (linha 16); se estivermos no estado 2 (eliminar espaços a mais) e nos aparece um caracter normal, copiamos essa caracter e regressamos ao estado 1 (linhas 18 a 20), caso contrário não fazemos nada. E pronto!

Problema 2.17

Qual a Distância de Hamming entre duas cadeias de caracteres, isto é, em quantas posições divergem? Se as cadeias tiveram o mesmo comprimento é fáciul:

def hamming_b(cad1,cad2): # Começar com esta solução...
    """
    Determina a distância de Hamming entre duas cadeias.
    Para o mesmo tamanho!!!
    """
    conta = 0
    for i in range(len(cad1)):
        if cad1[i] != cad2[i]: # erro corrigido!
            conta = conta + 1
    return conta

Limitamo-nos a usar o padrão acumulador, percorrendo as cadeias posição a posição e testando a igualdade (linha 8). Mas, e se tiverem comprimento diferente? Bom ,só é preciso um pequeno ajuste.

def hamming_a(cad1,cad2):
    """
    Determina a distância de Hamming entre duas cadeias.
    """
    conta = 0
    comp_min = min(len(cad1),len(cad2))
    comp_max = max(len(cad1),len(cad2))
    for i in range(comp_min):
        if cad1[i] != cad2[i]:
            conta = conta + 1
    conta = conta + (comp_max - comp_min)
    return conta

Testamos as sub-cadeias de igual comprimento, como anteriormente, e depois consideramos que os caracteres em excesso devem todos ser contabilizados para a distância de Hamming.

Problema 2.16

Pretende-se um programa que determine se uma dada cadeia de caracteres é, ou não, uma capicua. São capicuas as cadeias que são idênticas lidas da esquerda para a direita, e da direita para a esquerda. Exemplo: madam.

def capicua_a(cad):
    """
    Determina se a cadeia é uma capicua.
    """
    cap_p = True
    while cap_p and (len(cad) >= 2):
        cap_p = cap_p and (cad[0] == cad[-1])
        cad = cad[1:-1]
    return cap_p

Qual a lógica do programa? Comparar os caracteres a igual distância das extremidades (linha 7) e determinar se o resultado é verdadeiro ou falso. Se for falso, cap_p, que no início é True, passa a False provocando o abandono do ciclo while (linha 6). Se o cilco while terminar porque foram analisados todos os pares caracteres então cap_p será True (nunca é alterada) e esse valor é devolvido (linha 9). A variável cap_p funciona como uma bandeira que sinaliza uma condição(flag).

Problema 2.13

Pretende-se um programa que dada uma cadeia de caracteres substitua todas as ocorrências de vogais por espaços em branco.

import string
def retira_vogais(cad):
    """
    Retira as vogais numa cadeia, substituindo-as por espaços em branco.
    """
    vogais = 'aeiou'
    for ch in vogais:
        cad = string.replace(cad,ch,' ') 
    return cad

Programa que usa o método definido para cadeias replace. A estratégia é simples: um ciclo em que ch vai sendo sucessivamente associado a uma vogal. Em cada passagem pelo ciclo for são retiradas as ocorrências da vogal (linha 8).

Coisas práticas: instalar novos módulos

A linguagem Python pode crescer de acordo com os nossos desejos. Precisamos apenas acrescentar novos módulos. Para isso é preciso obter e instalar os módulos. Para saber onde os obter podemos googlar usando python como palavras chave, ou dar um passeio pelos sítios habituais de python de que http://www.python.org é sempre o primeiro a considerar. Devemos, finalmente, ter sempre em atenção qual a versão de python instalada, e escolher a versão do módulo compatível com essa versão e com a versão do sistema operativo (Windows, Mac OS ou Linix) ! Quando arranca com o python, directamente ou via um ambiente integrado de desenvolvimento, ele dá a informação sobre a versão instalada.

Agora os módulos. Se existir um instalador do módulo para o seu sistema operativo e para a versão de python instalada, use-o e não se preocupe mais. Se não existir e tiver apenas o ficheiro .py deve colocar o módulo na pasta site-packages localizada em:

Windows: C:\Python26\Lib\site-packages


Linux: /usr/local/lib/python2.6/site-packages


Mac OS X (versão pré-instalada 2.5): /usr/local/lib/python2.5/site-packages

Mac OS X (versão instalada por si): /Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages

As coisas podem ser um pouco mais complexas, caso o módulo não tenha instalador e a distribuição da fonte tenha sido feito usando o distutils. Neste caso o módulo vem comprimido, com mais outros ficheiros. Deve descomprimir o módulo com o aplicativo/comando adequado. É, em geral, criada uma pasta com o nome do módulo seguido da versão do módulo. Lá dentro encontrará, entre outras coisas, um ficheiro README que contém as instruções de instalação, que deve seguir. Normalmente resume-se a abrir uma janela de terminal/consola, mudar-se para a directoria onde está o módulo com um comando cd e emitir o comando python setup.py install.

Pode obter informações mais detalhadas, incluindo variantes à instalação básica, aqui

Pi: ver para crer!

No post anterior mostrei como se pode calcular o valor de Pi usando o Método de Monte Carlo. Também já falei no módulo cTurtle que permite colocar tartarugas a fazer desenhos numa tela. Vamos juntar as duas coisas e fornecer uma solução ao cálculo do vaslor de Pi com animação! Para já o código.

import random
import math
import cTurtle


def monte_carlo_animado(num_dardos):
    """
    Valor de pi pelo método de monte Carlo.
    Versão gráfica.
    """
    # prepara a visualização
    janela = cTurtle.Turtle()
    janela.setWorldCoordinates(-2,-2,2,2)
    janela.hideturtle()
    
    janela.up()
    janela.goto(-1,0)
    janela.down()
    janela.goto(1,0)
    
    janela.up()
    janela.goto(0,1)
    janela.down()
    janela.goto(0,-1)   
    
    # vamos aos cálculos
    conta_dardos_in = 0
    janela.up()
    
    for i in range(num_dardos):
        x = random.random()
        y = random.random()
        
        d = math.sqrt(x**2 + y**2)
        janela.goto(x,y)
        
        if d <= 1:
            conta_dardos_in = conta_dardos_in + 1
            janela.color("blue")
        else:
            janela.color("red")
        
        janela.dot()
    
    janela.exitOnClick() 
    
    res = 4 * (conta_dardos_in / float(num_dardos))
    
    return res
    
    
if __name__ == '__main__':
    print monte_carlo_animado(1500)

A parte da cálculo propriamente dito já foi explicado. Tratemos pois à animação. As linhas 11,12 e 13 criam a tartaruga e definem a dimensão da tela. Das linhas 15 à 22 desenhamos os eixos. Na linha 33 colocamos a tartaruga no sítio certo.Os dardos dentro do círculo serão azuis (linha 37) e ou outros vermelhos (linha 39). São desenhados como pontos (linha 41). Se clicarmos dentro da tela o programa termina (linha 43). Executando o programa para 1500 dardos obtemos a linda figura:

.

Pi revisitado

Já aqui falámos do número Pi, um número irracional que só pode ser calculado por aproximação. Existe um método interessante baseado em ideias probabilísticas. Por essa razão, essas técnicas são conhecidas pelo nome genérico de Método de Monte Carlo. Em que consiste? Suponhamos uma circunferência de raio 1 inscrita num quadrado de lado 2 como mostra a figura.

Sabemos que a área é dada por:

\pi \times R^2

Com o raio R igual a um então a área da circunferência é igual a Pi. Fixemo-nos agora no canto superior direito da figura.

Claramente a área do quarto de círculo é igual à quarta parte de Pi. É aqui que entra o nosso método. Admitamos que a figura acima está afixada numa parede e que nós atiramos dardos em sua direcção. Admitamos também, que todos os dardos acertam na figura e que todos os pontos do quadrado têm a mesma probabilidade de serem atingidos (tecnicamente dizemos que estamos a extrair os pontos de uma distribuição uniforme). Então, ao fim de muitos dardos disparados o número de dardos que caem dentro do quarto de círculo é proporcional à área, ou seja, a Pi/4.

Com base nesta ideia tão simples chegamos ao programa seguinte:

import math
import random

def monte_carlo_pi(num_dardos):
    """
    Calcula o valor de pi pelo método de monte Carlo.
    """
    # define e inicializa acumulador
    conta_dardos_in = 0.0
    for i in range(num_dardos):
        # gera posição dardo i
        x= random.random()
        y= random.random()
        # calcula distância à origem
        d = math.sqrt(x**2 + y**2)
        if d <= 1:
            conta_dardos_in = conta_dardos_in + 1
    res_pi = 4 * (conta_dardos_in/float(num_dardos))
    return res_pi

Analisemos o código. Nas linhas 1 e 2 importamos os módulos math e random. O primeiro porque vamos precisar de calcular uma raiz quadrada, o segundo, porque precisamos gerar as coordenadas onde os dardos vão chegar. Em relação ao programa em si saliente-se que temos de resolver duas questões. A primeira, consiste em saber como geramos as coordenadas do dardo; a segunda, liga-se à questão da contagem do número de dardos que caem dentro do círculo. Para a primeira questão, usamos um gerador de números aleatórios que nos fornece números reais no intervalo [0,1] (linhas 12 e 13). Para a segunda questão, basta pensar que, dada a construção (o raio vale 1), todos os pontos a uma distância da origem menor ou igual a 1 caem sobre ou no interior da zona de interesse. A distância (euclidiana) à origem é calculada na linha 15. Na linha 17 contamos os que acertam no quarto de círculo. No final basta multiplicar a percentagem dos que caem dentro por quatro para obter o valor aproximado de Pi (linha 18). Uma nota final para referir que usámos o padrão de programação conhecido por acumulador: neste caso o nome conta_dardos cumpre o papel de contador, com as duas fases de inicialização (linha 9) e actualização (linha 17).

Testemos o programa.

>>> monte_carlo_pi(1000)
3.096
>>> monte_carlo_pi(100000)
3.13612
>>>

Não está mal!

Espirais

Num post recente falei do módulo cTurtle. De um modo simples era possível desenhar polígonos regulares. Mais um exemplo, muito simples, para desenhar espirais.

Vou construir a dita de modo aproximado recorrendo a segmentos de recta que vão rodando. Neste caso é evidente que precisamos definir várias coisas:
- o comprimento do segmento inicial
- o comprimento do segmento final
- o ângulo de viragem
- se roda no sentido dos ponteiros do relógio ou não
- se a mudança de comprimento é crescente ou decrescente.

Vejamos o código.

import cTurtle

def espiral(comp_min, comp_max, passo, angulo):
    """
    Desenho de espirais por justaposição de segmentos de recta que 
    vão rodando de um certo ângulo. Assumo sentido crescente e rotação
    idêntica à dos ponteiros do rrelógio.
    """
    cTurtle.down()
    for segmento in range(comp_min, comp_max, passo):
        cTurtle.forward(segmento)
        cTurtle.right(angulo)
    cTurtle.up()
    cTurtle.hideturtle()
    

Com a chamada espiral(10,150,5,90) obtemos a figura:





Mas se usarmos outros valores, como espiral(5,50,2,33), o desenho será outro:



.

Divirta-se!

Python Wiki

Para os que gostam de Wikis é dar uma olhada em Python Wiki. Lá encontrará muita informação sobre a linguagem, aplicações e projectos que usam Python.

Visões

A linguagem Python tem um conjunto de módulos adicionais que permitem aumentar muito o seu poder expressivo. Hoje quero falar-vos de um bastante pequeno mas que permite brincar com coisas sérias. Baseia-se na ideia de uma tartaruga que se passeia sob nosso controlo, podendo deixar um rasto visível. Para isso tem uma caneta. Sempre que a caneta está em baixo e a tartaruga caminha, lá aparece o rasto. Existem por isso comandos para baixar a caneta, levantar a caneta, rodar para a esquerda ou para a direita, etc.


Existem variantes deste módulo. Quando instala o Python fica com a possibilidade de importar de imediato o módulo turtle. Outras possibilidades são o xturtle ou a sua versão mais completa cTurtle . É este último que iremos explorar.

Comecemos com um exemplo simples que nos permite desenhar um quadrado.

import cTurtle

def quadrado(lado):
    """
    Desenha um quadrado.
    """
    cTurtle.showturtle()
    #-----------
    cTurtle.fd(lado)
    cTurtle.rt(90)
    cTurtle.fd(lado)
    cTurtle.rt(90)    
    cTurtle.fd(lado)
    cTurtle.rt(90)
    cTurtle.fd(lado)
    cTurtle.rt(90)
    #----------
    cTurtle.hideturtle()

    
quadrado(100)

Executando este código obtém-se o desenho:





O código acima não é brilhante! Basta ver que repetimos 4 vezes o mesmo par de instruções. É por isso que existem estruturas de controlo repetitivas em todas as linguagens de alto nível. Para este caso em que o número de repetições é fixo e conhecido previamente vamos usar um ciclo for.

import cTurtle

def quadrado(lado):
    """
    Desenha um quadrado.
    """
    cTurtle.showturtle()
    #-----------
    for i in range(4):
        cTurtle.fd(lado)
        cTurtle.rt(90)
    
    #----------
    cTurtle.hideturtle()

    
quadrado(100)

Alguns comentários. Em primeiro lugar, usamos a notação normal para o uso de funções que estão definidas num módulo que foi importato com import módulo. Em segundo lugar, o mesmo comando pode ter mais do que um nome. Assim, por exemplo,podemos abreviar forward por fd.Em terceiro lugar, existem neste programa quatro comandos, cujos nomes em inglês são claros.


Continuemos esta breve exploração. Agora vamos desenhar um pentágono, um polígono regular de 5 lados. Com pouco esforço chegamos ao seguinte código:

import cTurtle
def pentagono(lado):
    """
    Desenha um pentágono.
    """
    cTurtle.showturtle()
    #-----------
    for i in range(5):
        cTurtle.fd(lado)
        cTurtle.rt(72)
    
    #----------
    cTurtle.hideturtle()

    
pentagono(100)

Executado o código obtemos agora a figura:





Fixemo-nos nos dois programas. Quais são as suas únicas diferenças? Claro: o valor do número de lados (repetições) e o ângulo. Mas há alguma relação entre eles? Claro que sim, uma vez mais. Num polígono regular o produto entre o número de lados e o ângulo interno dá sempre 360 graus. Com base nisso podemos generalizar o código, escrevendo um programa que dá para qualquer polígono regular.

import cTurtle
def poligono_regular(comp_lado,num_lados):
    """
    Desenha um polígono.
    """
    cTurtle.showturtle()
    angulo_viragem = 360 /num_lados
    #-----------
    for i in range(num_lados):
        cTurtle.forward(comp_lado)
        cTurtle.right(angulo_viragem)

    #----------
    cTurtle.hideturtle()     
    
poligono_regular(50,8)

Pode experimentar.

Mas será que só dá para isto? Claro que não. Isto é apenas um começo. Quando dominar o módulo vai ser capaz de desenhar um linda árvore inclinada para a esquerda devido ao vento.

Problema 1.20

Neste problema é-nos pedido um programa que teste se um dado inteiro é primo. Um número diz-se primo se os únicos divisores são ele próprio e o número 1. Este exemplo dá-nos a oportunidade de mostrar como as definições nos permitem usar a abstracção e estruturar o código. Na nossa abordagem começamos com a definição:

def primo(n):
    conta = divisores_c(n)
    if conta == 2:
        return True
    else:
        return False

Como se vê pela solução apresentada (linha 2) delegamos noutra definição, divisores_c(n), a contagem dos divisores. Se esse número for 2 será primo, caso contrário não será. Claro que o programa estará correcto apenas se forem incluídos 1 e o próprio número na contagem, como na solução seguinte.

def divisores_c(n):
    """
    Conta os divisores de um número.
    """
    conta = 0
    for i in range(1, n+1):
        if (n % i) == 0:
            conta = conta + 1
    return conta

Esta solução baseia-se no uso do padrão acumulador. O acumulador do resultado conta é inicializado na linha 5 e actualizado na linha 8. Visualmente temos a seguinte dependência entre as duas definições:





Mas admitamos que queremos optimizar o programa que conta os divisores deixando de fora o caso óbvio dos divisores próprios. Podemos então optar por:

def divisores_c(n):
    """
    Conta os divisores de um número.
    """
    conta = 0
    for i in range(2, n/2 + 1):
        if (n % i) == 0:
            conta = conta + 1
    return conta

Só precisámos mexer na linha 6 do código! Agora necessitamos alterar o nosso programa principal.

def primo(n):
    conta = divisores_c(n)
    if conta == 0:
        return True
    else:
        return False

E já está!