Caçar com gato

O exercício 5.8 pede-nos que baralhemos uma cadeia de caracteres. Usámos o método shuffle do módulo random. Mas e se não soubermos da sua existência? Caçamos com gato ... Este não é um problema fácil. Existem várias soluções, umas mais elegantes e eficientes do que outras. Como ainda não se falou de recursividade vamos mesmo ter que caçar com um gato muito ... rafeiro: a iteração. Eis uma solução para o problema de gerar permutações de elementos guardados numa lista.

def permuta_it(lista):
    """
    Devolve as permutações de uma lista de elementos.
    """
    resultado = [[]]
    for i in range(len(lista)):
        aux_1 = []
        for elem in resultado:
            aux_2 =[]
            for j in range(len(elem) + 1):
                aux_2.append(elem[:j] + [lista[i]] + elem[j:])
            aux_1.extend(aux_2)
        resultado = aux_1[:]
    return resultado

Para chegarmos a esta solução baseámo-nos na ideia da construção indutiva da solução, método já referido em post anterior. A solução é construída etapa a etapa, de baixo para cima. Começando com uma lista vazia (linha 5), Entramos num ciclo (linhas 6 a 13), que será repetido tantas vezes quantos os elementos da nossa lista original. Dentro do ciclo, na primeira etapa, construímos todas as permutações de comprimento 1, com o primeiro elemento da lista original. Só há uma permutação! Depois, na etapa 2 do ciclo, pegamos nessa permutação e fabricamos todas as de comprimento 2, juntando o segundo elemento da lista original de todos os modos possíveis a cada uma das soluções da etapa anterior (linhas 7 a 12). Neste ficamos com as duas permutações de dois elementos. E assim sucessivamente, por cada etapa do ciclo, até termos usado todos os elementos da lista original. Vejamos dois exemplos:

>>> permuta_it([1,2,3])
[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
>>> permuta_it(['r','a','m','o'])
[['o', 'm', 'a', 'r'], ['m', 'o', 'a', 'r'], ['m', 'a', 'o', 'r'], ['m', 'a', 'r', 'o'], ['o', 'a', 'm', 'r'], ['a', 'o', 'm', 'r'], ['a', 'm', 'o', 'r'], ['a', 'm', 'r', 'o'], ['o', 'a', 'r', 'm'], ['a', 'o', 'r', 'm'], ['a', 'r', 'o', 'm'], ['a', 'r', 'm', 'o'], ['o', 'm', 'r', 'a'], ['m', 'o', 'r', 'a'], ['m', 'r', 'o', 'a'], ['m', 'r', 'a', 'o'], ['o', 'r', 'm', 'a'], ['r', 'o', 'm', 'a'], ['r', 'm', 'o', 'a'], ['r', 'm', 'a', 'o'], ['o', 'r', 'a', 'm'], ['r', 'o', 'a', 'm'], ['r', 'a', 'o', 'm'], ['r', 'a', 'm', 'o']]
>>> 

Problema 5.8

Este exercício obriga a conhecer o que nos permite o módulo random. Já sabemos: para o fazer temos que consultar a documentação ou usar o próprio sistema (comandos dir e help). Admitindo que sabemos que existe o método shuffle e o que faz, a solução é trivial. Também necessitamos saber como se pode fazer conversão de tipos entre listas (de caracteres) e cadeiras de caracteres.

import random

def baralha_palavra(palavra):
    baralhada=list(palavra[1:-1])
    random.shuffle(baralhada)
    return palavra[0]+"".join(baralhada)+palavra[-1:]

Na linha 4 retiramos o primeiro e último elemento da palavra. Depois transformamos o resultado numa lista. Agora já podemos baralhar os caracteres. Notar que o método shuffle opera sobre listas, baralha tudo sem usar cópia (in situ) e devolve como resultado o objecto None. É por isso que não vemos nenhuma atribuição! Finalmente, devolvemos a cadeia reconstruída: o primeiro caracter, seguido da parte que foi baralhada depois de convertida para cadeia de caracteres e seguida do último caracter. Atente-se no modo como o método join é usado: primeiro o separador (neste caso a cadeia vazia) seguido do ponto, seguido de join, seguido da lista de caracteres a unir, colocada entre parênteses.

Problema 5.6

Conhecemos o velho ditado: quem não tem cão caça com gato! Acontece o mesmo em programação: quem não conhece as potencialidades de uma linguagem ... inventa-as. É o que mostram as duas soluções apresentadas abaixo:

def multiplos_a(num1,num2):
    """ multiplos de num1 não inferiores ao segundo."""
    return range(num1,num2+1,num1)

def multiplos_b(num1,num2):
    """ multiplos de num1 não inferiores ao segundo."""
    mult = []
    num_teste = num1
    while num_teste <= num2:
 mult.append(num_teste)
 num_teste = num_teste + num1
    return mult

Moral da história. Pensar primeiro: se a linguagem tivesse o comando xpto era óptimo. Terá? Ter sempre o manual de referência da linguagem por perto ajuda a determinar a resposta.

Problema 5.4

Este problema aparece apenas para chamar a atenção para a formatação de saída envolvendo cadeias de caracteres. Vejamos quatro soluções possíveis para a questão.

def engarrafa_a(litros):
    return "Com " + str(litros) + " litros pode encher "\
           +str(int(litros/1.5))+" garrafas, restando "+str(litros%1.5)+" litros"

def engarrafa_b(litros):
    return "Com %d  litros pode encher %.0f garrafas, restando %.2f litros" % (litros,int(litros/1.5), litros%1.5)

def engarrafa_c(litros):
    garrafas = int(litros/1.5)
    resto = litros%1.5
    return "Com %d  litros pode encher %.0f garrafas, restando %.2f litros" % (litros,garrafas,resto)

def engarrafa_d(litros):
    garrafas = int(litros/1.5)
    resto = litros%1.5
    return "Com {0}  litros pode encher {1:.0f} garrafas, restando {2:.2f} litros".format(litros,garrafas,resto)

A solução a é a clássica, quando não se sabe muito sobre formatação de cadeias de caracteres. Usa a operação de concatenação (+), e obriga a muitas conversões de tipos decididas explicitamente pelo programador. A segunda, b, já avança um bom bocado, precisamente porque usa o operador de formatação %. Note-se que no interior da cadeia o sinal % é um sinal de formatação. Na alternativa c, limitamo-nos a tornar o código mais legível introduzindo as duas variáveis locais garrafas e resto. Finalmente, a solução d é a mais moderna do ponto de vista de Python, socorrendo-se do método format. Esta possibilidade existe a partir da versão 2.6 de Python e deve ser a preferida.

Problema 5.2

Os problemas desta secção da ficha são todos muito simples. Daí que os que forem apresentados se limitarem basicamente ao código. Neste caso para resolver apenas era necessário ter conhecimentos básicos de trignometria, já que os de informática são primitivos.

import math

def cartesiana_para_polar(x,y):
    """ converte de coordenadas cartesianas para polares."""
    r = sqrt(x**2 + y**2)
    theta = math.atan(float(x)/y)
    return r, theta

Coisas a notar. A necessidade importar o módulo math. A necessidade de forçar a conversão para float devido ao modo como a divisão funciona em Python 2.6. A possibilidade de devolver por returnmais do que um resultado, separados por vírgulas. Neste último caso, é de referir que na realidade o que é devolvido é um objecto do tipo tuplo, isto é, (r,theta).

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.