Next: Troca Up: Enunciados Previous: Diamante
Considerem-se sequências de letras do alfabeto (i.e., de a até z) como entrada. Um exemplo poderá ser
xcaabaabaabccadadcaabaabaabccadady
Uma sequência pode ser compactada por um algoritmo muito simples, que substitui
n (digamos 7) ocurrências consecutivas de um símbolo (digamos p) pelo símbolo
seguido de n --no nosso exemplo, p7, e p7 é claramente mais curto que ppppppp. O
mesmo algoritmo de compactação pode ser também aplicado a subsequências. Por exemplo,
ababab pode ser compactado por (ab)3. Note que (ab)3 tem 5 caracteres.
Deste modo, a sequência dada acima pode ser comprimida, por exemplo, por
x(c(a2b)3c2(ad)2)2y
No entanto esta não é a compactação mais curta, por causa da ocorrência (ad)2:
(ad)2 usa mais um caracter do que adad. Resulta claro quando é que os
parêntesis são necessários e quando não. Uma vez que nem os dígitos nem os
parêntesis ocorrem na string de entrada, não existe qualquer tipo de ambiguidade.
Deverá desenvolver um predicado compacta/2, que recebe como entrada uma
sequência --representada como uma lista de letras-- e que retorna a lista compactada mais
curta, que lhe é equivalente. Para o exemplo apresentado, teremos:
?- compacta([x,c,a,a,b,a,a,b,a,a,b,c,c,a,d,a,d,c,a,a,b,a,a,b,a,a,b,c,c,a,d,a,d,y],L). L = [x,(,c,(,a,2,b,),3,c,2,a,d,a,d,),2,y]
embora também seja correcto
?- compacta([x,c,a,a,b,a,a,b,a,a,b,c,c,a,d,a,d,c,a,a,b,a,a,b,a,a,b,c,c,a,d,a,d,y],L). L = [x,(,c,(,a,a,b,),3,c,c,a,d,a,d,),2,y]
Next: Troca Up: Enunciados Previous: Diamante