necesito ayuda para resolver este algoritmo

Cita de: engel lex en 16 Marzo 2018, 18:50 pm

Código:

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

Código:

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

Código:

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

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

Código:

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)

Código:

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

Código:

(((N-n)-n) > 1)

es equivalente, -en este caso- a la que persguía engel lex,

Código:

n<N/2

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.

Código:

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.

Código:

>>> 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