elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


 


Tema destacado: [Aporte] Mejores practicas en Java


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ejercicios
| | | |-+  necesito ayuda para resolver este algoritmo
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: necesito ayuda para resolver este algoritmo  (Leído 993 veces)
arapisa

Desconectado Desconectado

Mensajes: 1


Ver Perfil
necesito ayuda para resolver este algoritmo
« en: 16 Marzo 2018, 17:27 »

necesito un algoritmo con vectores que determine si una palabra es un palindromo
 se tiene que resolver con pseudocodigo


En línea

engel lex
CoAdmin
***
Desconectado Desconectado

Mensajes: 15.347



Ver Perfil
Re: necesito ayuda para resolver este algoritmo
« Respuesta #1 en: 16 Marzo 2018, 18:50 »

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


En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
dijsktra

Desconectado Desconectado

Mensajes: 100


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: necesito ayuda para resolver este algoritmo (palindromo en pseudocodigo)
« Respuesta #2 en: 17 Marzo 2018, 23:49 »

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
« Última modificación: 18 Marzo 2018, 11:06 por dijsktra » En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines