Entero i
Para i empezando en 0 y terminando en largo_palabra/2:
Si palabra en i != palabra en largo_palabra - i:
Imprimir no es palíndromo
Terminar
Fin Si
Fin Para
Imprimir palabra es palíndromo
Creo que la solución aportada está mal. Si empezamos a numerar las posiciones de una palabra en 0, como es normal en a mayoría de los lenguajes, W[0..N), con una palabra de longitud N=2, la expresión
palabra en largo_palabra - i:
compara los caracteres W[0] y W[2-0], estando el segundo fuera de rango...
Es un problema sencillito, que todos hemos intentado siempre de memoria, pero del que se puede aprender mucho meditando...
Propongo dos ideas, las dos en complejidad O(n), aunque en términos absolutos, la segunda es el doble de rápida que la primera...
Primera, sin tener en cuenta la propia simetría del problema, en un bucle de N veces...
Es un problema de decisión y se trata de devolver el menor indice n que no cumpla la condición de palíndromo con su homólogo N-n-1 o en su defecto, N, si todos lo cumplen. Formalmente
P : N >= 0
Q : N==min i: 0<=i and (N=i or V[i]!=V[N-i-1]):i
0 1 n=2 N-2 N-1 N
+-----+-----+-----+-...-+-----+-----+-----+
| A | B | | | | B | A |
+-----+-----+-----+-...-+-----+-----+-----+
I : \forall i : 0 <= i < n : V[i] == V[N-i-1]
and
0 <= n <= N
B : (n < N) and (V[n]==V[N-n-1])
init : n = 0
Restore: skip
C(N,n) : N-n >= 0
Step : n = n + 1
O(n)
Y este es el código
Pseudocode
------------
n=0
while n<N and V[n]==V[N-n-1]
n = n +1
done
return n==N
Como habréis notado, una vez se pasa de la mitad, resulta innecesario seguir procesando.
Esa es la idea que quiso desarrollar
engel lex. De trivial no tiene nada.
Se trata de buscar el intervalo de longitud máxima menor que N y de la forma [i..N-i) tal que sus extremos i e N-i-1 no cumplan la condición de palindromo, o el intervalo vacío o de un elemento si todos lo cumplen. Si este intervalo es menor o igual que 1, la palabra es palindromo. La idea formal, ilustrada con un dibujo, puede ser esta
i N-i
....
3 N-3
------------
2 N-2
------------------------
1 N-1
------------------------------------
0 N
-------------------------------------------------
0 1 2 3 N-3 N-2 N-1 N
+-----+-----+-----+-...-+-...-+-----+-----+-----+
| A | B | C | | | C | B | A |
+-----+-----+-----+-...-+-...-+-----+-----+-----+
Key : Think on [i..N-i) intevals and distances: (N-i)-i
P : N >= 0
Q : 0=max i:(N>=(N-i)-i)and ((N-i)-i=0 or V[i]!=V[N-i-1]):N-i-i
I : N>=N-n-n>=0 and
\forall i : N>= N-i-i > (N-n-n) : V[i]=V[N-i-1]
B : N-n-n > 1 and V[n]==V[N-n-1]
init n=0
Restore: skip
C(N,n) : N-n-n >= 0
Step : n = n + 1 (decreases on two!)
y este es el código. Como vemos, no inspecciona todas las casillas dos veces, como el anterior. Notablemente es más difícil, claro, aunque igual de complejidad temporal O(n)
Pseudocode
------------
n=0
while (((N-n)-n) > 1) and V[i]==V[N-i-1]
n = n +1
done
return (((N-n)-n) <= 1)
Notese que la expresión
es equivalente, -en este caso- a la que persguía
engel lex,
pero nosotros, tardando un poco más
hemos llegado a ella razonadamente, completando la intuición que todos hemos tenido de siempre de este algoritmo y que, como es el caso, podría llevarnos a errores.
Me he permitido pasarlo a python, para tener alguna "experiencia real" del algoritmo.
def palyndrome(V):
n = 0
while ((len(V)-n)-n > 1) and V[n]==V[-n-1]:
n+=1
return ((len(V)-n)-n <= 1)
Con estos resultados.
>>> palyndrome("abccba")
True
>>> palyndrome("abcba")
True
>>> palyndrome("abcca")
False
>>> palyndrome("aaabbb")
False
>>> palyndrome("aaabbbaa")
False
>>> palyndrome("aaabbbaaa")
True
>>> palyndrome("123454321")
True
>>> palyndrome("123454322")
False
>>> palyndrome("")
True
>>> palyndrome("1")
True
>>> palyndrome("12")
False
>>> palyndrome("11")
True
Autor
En línea
