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!