domingo, 11 de outubro de 2009

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!

9 comentários:

  1. Professor desculpa que diga mas existe uma solução muito mais simples para a resolução deste problema.
    "
    import string
    def espacos(d):
    for q in range(i):
    c = d.replace("(espaço 3 vezes)", " ")
    a = c.replace("(espaço 2 vezes)", " ")
    d = a
    (fim de ciclo)
    print a
    "

    penso que isto é um programa muito mais simples de resolver o problema.

    Cumprimentos,
    Tiago Simões

    ResponderEliminar
  2. Tiago,

    Simples era ... mas não funciona! Desde logo qual o valor de i que usa no cabeçalho do ciclo for??

    Por outro lado, e esta é a crítica maior, a solução não é geral: e se tiver 6 espaços, e 20, e 8 e....

    O melhor que podia fazer era algo do tipo.

    -------------------------------
    def espaco(cadeia):
    for i in range(2,10):
    sub = ' '*i
    cadeia = cadeia.replace(sub, '')
    return cadeia
    ---------------------------------

    Mas repare que só funciona entre 2 e 20 espaços. Acresce que, mesmo assim é pouco eficiente pois vai andar a testar coisas que não existem.

    ResponderEliminar
  3. Peço desculpa pelo lapso, mas como não da para copiar directamente do python para o blog, eu não passei algumas coisas, dentro das quais o valor de i.

    O valor de i = c.count(' ')

    Por isso o programa vai fazer aquele ciclo o número de vezes que o espaço existe.
    A responder a outra questão do professor, o meu programa já fez testes com o número de espaços de: 109, 59, 100, 80, etc. Sem o mesmo ter dado problema.

    Cumprimentos,
    Tiago Simões

    ResponderEliminar
  4. Professor, esta solução é válida para todos os casos?

    n=raw_input("insira a cadeia de caracteres:")
    string = ""
    for i in range (len (n)):
    if n[i] == " ":
    if i>0:
    if n[i-1] == " ":
    continue
    string = string + n[i]
    print string

    ResponderEliminar
  5. É ainda possível tornar os 3 ifs num só através de if n[i] == " " and i>0 and n[i-1] == " ".

    Diga-me se estou a cometer algum erro.

    ResponderEliminar
  6. Depois de ler melhor o seu exemplo acabei por verificar que o meu só tem a diferença de não necessitar da existência de uma variável "anterior", pois referencia o caractere anterior pelo índice. De qualquer das formas fica aqui o código, ainda que não acrescente nada ao que o professor disse.

    Cumprimentos

    ResponderEliminar
  7. Tiago,

    Ok. Funciona! Mas muito ineficiente. Se o i é o número total de espaços, e se no interior ou tira 2 ou 3 em cada etapa do ciclo, vai andar às voltas muitas vezes quando já não há espaços nenhuns na cadeia. É bom que apareçam várias alternativas ao programas para que pensemos sobre a melhor (ou menos má) opção. Mas não esquecer umsa coisa: a programação tem que combinar eficiência ee elegância.

    ResponderEliminar
  8. João,

    Como não vejo a indentação do código não se lhe dizer ao certo se funciona. Admito que sim, caso de o continue ser o corpo do if, e a instrução de atribuição estar fora desse mesmo if.
    Como já disse a programação tem várias variantes. Devemos procurar o equilíbrio entre elegância, eficiência, legibilidade, etc. Claro que no final cada pessoa tem o seu próprio estilo e anda sempre à procura de soluções diferentes, o que eu acho bem!

    ResponderEliminar
  9. n=raw_input("insira a cadeia de caracteres:")
    string = ""
    for i in range (len (n)):
    ____if n[i] == " " and i>0 and n[i-1] == " ":
    ________continue
    ____string = string + n[i]
    print string

    Versão final (_ = espaço).

    ResponderEliminar