terça-feira, 29 de dezembro de 2009

Errar é humano...

Um aluno de IPRP estava com dificuldades num problema que saiu no exame de 2006 e pediu-me ajuda. O problema era o seguinte:

Suponha que tem uma cadeia de caracteres com um dado comprimento e a pretende dividir em n partes iguais. Implemente em Python o respectivo programa não se esquecendo de prever o caso de o comprimento da cadeia não ser múltiplo de n.

Enviou-me a sua tentativa de solução que não funcionava:

def divide(f, p):
aux=[]
a=len(f)
lpp=(len(f)-1)/p
dif=0
x=lpp
faux=''
n=0
while(n < p):
faux=f[dif:lpp+1]
aux.append(faux)
dif=(dif+lpp)+1
lpp=(lpp+x)
n=n+1
return aux

Qual é a lógica desta solução? Bem andar a partir a frase em pedaços todos do mesmo comprimento. Calcula-se esse comprimento na linha 4. Usam-se duas marcas (dif e lpp) para determinar os limites de cada pedaço, que vão sendo guardados em aux, a capa passagem pelo ciclo while. A ideia faz sentido.


Vamos ver alguns dos seus problemas. Começo pelo código inútil:

a = len(f), não está lá a fazer nada, nunca sendo usado.
faux = '' : esta inicialização não é preciso para nada

Agora os erros:

lpp = (len(f) - 1) / p: não se deve retirar um ao comprimento, dado o modo como a divisão funciona.
faux[f[dif:lpp+1]: errado devido à soma de 1.
dif = dif + lpp +1: aqui talvez o erro maior! Em cada etapa dif deve avançar para o valor de lpp.

Posto tudo isto uma solução usando esta ideia seria (notem que uso x no lugar de lpp, por uma questão de clareza):

def divide_corrigido(f, p):
   aux=[]
   lpp=len(f)/p
   dif=0
   x = lpp
   n=0
   while(n < p):
       faux=f[dif:x]
       aux.append(faux)
       dif=x
       x = x + lpp
       n=n+1
   aux.append(f[dif:])
   return aux

Mas não estou satisfeito, pois podemos encontrar uma solução mais elegante, tendo por base o mesmo princípio: duas marcas que vão avançando a cada passagem pelo ciclo. Mas para tal podemos usar uma combinação de um ciclo for com a operação range:

def divide_ec(frase,n):
   """divide a frase em n pedaços iguais."""
   # número de caracteres em cada parte
   num_car = len(frase)/n
   # calcula e guarda em aux
   aux = []
   for i in range(0,len(frase),num_car):
       aux.append(frase[i:i+num_car])
   return aux

O trabalho de fazer avançar a marca correctamente é assegurado pelo modo de funcionar do range comn três argumentos. Concordarão que este programa é mais claro do que o proposto! E prevê o caso de a frase ter um comprimento que não é múltiplo de n!

Se gostarem de listas por compreensão podem ainda prescindir de aux.:

def divide_ec_2(frase,n):
   num_car = len(frase)/n
   return [frase[i:i+num_car] for i in range(0,len(frase),num_car)]


Mas voltemos ao enunciado, que nos fala em n partes iguais. Se corrermos o programa, verificamos que nos casos em que não é múltiplo existem n+1 partes! Como corrigir este aspecto? Uma solução será esticar a cadeia e passar a ter cadeias todas do mesmo tamanho, menos a última. Esta era, aliás, a interpretação correcta do enunciado...


def divide_ec_3(frase,n):
"""divide uma sequência frase em n partes.
A última pode ser menor."""
parte=(len(frase) + n - 1)/n
aux = []
for i in range(0,n):
aux.append(frase[parte*i:parte*(i+1)])
return aux


E até nos podemos dar ao luxo de ter uma solução recursiva!!

def divide_ec_4(frase,n):
if n == 0:
return []
else:
return [frase[:len(frase)/n]] + divide_ec_4(frase[len(frase)/n:],n-1)


E assim terminamos este exercício. aprendemos muito com os nossos erros ... e com os erros dos outros!!

1 comentário:

  1. Bom post. Pessoalmente tb gosto de analisar código usando diversos algoritmos e até paradigmas diferentes. Muitas vezes acabamos melhorando bastante o processo com isso.
    Só uma correção, na chamada recursiva de divide() no return deve ser divide_ec_4().
    Abraço.

    ResponderEliminar