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

 

 


Tema destacado: Guía rápida para descarga de herramientas gratuitas de seguridad y desinfección


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Funcion palíndromo.
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 [2] 3 Ir Abajo Respuesta Imprimir
Autor Tema: Funcion palíndromo.  (Leído 22,451 veces)
-Ramc-


Desconectado Desconectado

Mensajes: 495



Ver Perfil
Re: Funcion palíndromo.
« Respuesta #10 en: 18 Septiembre 2008, 01:05 am »

Jejejeej, pero eso es C++, el mío es en C  :P
C++ ??? donde? Y aunque lo hubiera usado, como te darias cuenta???

Salu2, FreakMind
Geshi te lo esta coloreando como C++, aunque en este caso, no hay problema :P

Pones
Código:
 i <= len
no tendrias que usar otra variable ya que vas disminuyendo len, por lo que se afectaria la condición??


En línea


Shhh... be vewy, vewy, quiet!  I'm hunting wabbits...
LA PANDILLA MAS GRANDE DE MI CIUDAD, SE LLAMA POLICIA NACIONAL.
ҒrεακΠιи∂

Desconectado Desconectado

Mensajes: 184



Ver Perfil
Re: Funcion palíndromo.
« Respuesta #11 en: 18 Septiembre 2008, 01:27 am »

Pones
Código:
 i <= len
no tendrias que usar otra variable ya que vas disminuyendo len, por lo que se afectaria la condición??
No necesito otra variable, y si afecta la condicion (es lo que busco).


Salu2, FreakMind


En línea

Connoisseurs of C semantics find C++ inferior to ++C
Ragnarok
Colaborador
***
Desconectado Desconectado

Mensajes: 4.590


Shrödingerificado


Ver Perfil
Re: Funcion palíndromo.
« Respuesta #12 en: 21 Septiembre 2008, 14:21 pm »

PD: No se cual es el problema de poner int main(void) en lugar de int main()
No creo que eso optimice el código pero bueno...
Tampoco sé cual es el problema en que una función no devuelva nada, osea que sea tipo void, yo aprendí a programar así y no entiendo cual es el problema xD.

Los problemas son que la definición estándar de main es main() o main(char** argv, int argc), main(void) no es estándar y en algunos compiladores no compila.

Con respecto a los valores de retorno, son una buena práctica porque así siempre estás a tiempo de usar el valor de retorno para algo, si pones void y luego quieres usarlo vas a tener que cambiar la cabecera de la función. Eso en el peor de los casos, porque siempre hay algo más interesante que devolver, en el caso de introducir frase, que es un recubrimiento de gets un poco absurdo, deberías hacer como gets y devolver lo mismo. Mira a ver cuántas funciones de la librería estándar devuelven void.

Creo que para criticar, habria q criticar la actitud del que pidio el programa hecho...

Es que no había que haberle respondido, pero como cuando he llegado ya estaba puesta la respuesta simplemente he intentado que este hilo fuera un poco útil, ya le pillaré cuando le manden hacer otro ejercicio. Por cierto, muy ingeniosa tu respuesta, aunque tienes que restarle uno a la longitud al inicializar, si no estarás comparando el carácter de terminación del string en la primera comparación.
En línea

No olvidéis leer las normas generales, además de las específicas de cada tablón.sgae, ladrones
ҒrεακΠιи∂

Desconectado Desconectado

Mensajes: 184



Ver Perfil
Re: Funcion palíndromo.
« Respuesta #13 en: 21 Septiembre 2008, 15:20 pm »

Buenas

ya le pillaré cuando le manden hacer otro ejercicio.
Ya habia otro thread de el pidiendo que le hagan la tarea. Se llama "frecuencia de caracteres" o algo asi.

Por cierto, muy ingeniosa tu respuesta, aunque tienes que restarle uno a la longitud al inicializar, si no estarás comparando el carácter de terminación del string en la primera comparación.
No, no lo tengo que restar... fijate bien

Salu2, FreakMind
En línea

Connoisseurs of C semantics find C++ inferior to ++C
TheMaker


Desconectado Desconectado

Mensajes: 514



Ver Perfil
Re: Funcion palíndromo.
« Respuesta #14 en: 21 Septiembre 2008, 18:21 pm »

Exacto, hace --len, que primero quita uno y luego evalua. --len no es lo mismo q len--. O por lo menos eso tengo entendido, q alguién verifique.
En línea

Gibe money please or I report you
ҒrεακΠιи∂

Desconectado Desconectado

Mensajes: 184



Ver Perfil
Re: Funcion palíndromo.
« Respuesta #15 en: 21 Septiembre 2008, 19:05 pm »

Exacto, hace --len, que primero quita uno y luego evalua. --len no es lo mismo q len--. O por lo menos eso tengo entendido, q alguién verifique.
BINGO!

Salu2, FreakMind
En línea

Connoisseurs of C semantics find C++ inferior to ++C
jorge.helu

Desconectado Desconectado

Mensajes: 2


Ver Perfil
Re: Funcion palíndromo.
« Respuesta #16 en: 22 Marzo 2018, 05:17 am »

Oigan chicos pero como se le puede hacer para que no detecte los espacios
ya que por ejemplo si escribes:
"anita lava la tina"
se supone que si es palíndroma pero como esta estructurado el programa no lo reconoce.
En línea

dijsktra

Desconectado Desconectado

Mensajes: 110


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Funcion palíndromo.
« Respuesta #17 en: 22 Marzo 2018, 10:49 am »

Esto es una tontería pero bueno...

Código
  1. ....
  2. int Comprobar_frase (char frase[])
  3. {
  4. int longitud=strlen(frase);
  5. int i=0;
  6. while (i<=longitud/2 && frase[i]==frase[longitud-1-i])
  7.  {
  8.  i++;
  9.  }
  10. if (i>longitud/2)
  11.   return 1;
  12.   else
  13.   return 0;
  14. }
  15. ...
  16.  

Quizás no sea tan tontería, amigo mío... :D  El
Código:
(i<=longitud/2) 

hay que cambiarlo por

Código:
(i<longitud/2) 

y el epílogo de la rutina

Código:
(i>longitud/2)

por

Código:
(i>=longitud/2)


EXPLICACION:
--------------
 el programa es incorrecto si la palabra de entrada es vacía... ya que se accede a la posición [-1]. Y es claro que la palabra vacía es palíndromo.

"La palabra vacía no tiene ningún caracter. Por eso todos sus caracteres (es decir, ninguno, notese la paradoja) cumplen que son simétricos"

En lo de la forma de programar C, no me meto... Pero en general hay que usar con precaución el operador / de division entera...

Aquí teneis la solución que se pedía en pseudocódigo (luego lo hice en python)

https://foro.elhacker.net/ejercicios/necesito_ayuda_para_resolver_este_algoritmo-t481597.0.html;msg2157302#new
« Última modificación: 22 Marzo 2018, 10:51 am 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)
Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.391


Ver Perfil
Re: Funcion palíndromo.
« Respuesta #18 en: 22 Marzo 2018, 16:55 pm »

Un palíndromo es una palabra que se 'lee' igual al derecho que al revés...

Luego, si yace en un array, básicamente se trata de comparar el primer 'carácter válido', con el último 'carácter válido', el segundo 'caracter válido', con el penultimo 'caracter válido' hasta llegar aunirse (que será o no el centor 'geométrico'.

Nota que la cuestión para no cometer errores, radica en: es 'carácter válido', lo mismo que en la descripción he marcado 'leer' entre comillas simples, para hacer notarlo...

Esto sería un sencillo algoritmo que recorre el array tomando caracteres válidos de ambos extremos y comparándolos:

Código:
buleano = funcion Espalindromo(array bytes B() )
    entero j,k, n

    j= b.length -1 // tamaño del array
    Hacer mientras (k<j)
        hacer mientras b(k) sea espacio   // buscar siguiente 'carácter válido'
            k +=1
        repetir
    
        hacer mientras b(j) sea espacio   // buscar anterior 'carácter válido'
            j -=1
        repetir

        Si b(k) es distinto de b(j) devolver false
 
        k +=1
        j -=1
    repetir

    devolver true
fin funcion

Nota que además de espacio, podría haber tabuladores, y otros signos de puntuación, como comas ',' '; ':', etc... si se da el caso, mejor crear una función que busque el siguiente carácter válido, rechanzando todos los no aceptables... para rechazar solo uno o dos, basta hacerlo 'in situ'.
« Última modificación: 22 Marzo 2018, 16:58 pm por NEBIRE » En línea

dijsktra

Desconectado Desconectado

Mensajes: 110


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Funcion palíndromo.
« Respuesta #19 en: 4 Abril 2018, 17:48 pm »

Un palíndromo es una palabra que se 'lee' igual al derecho que al revés...

Luego, si yace en un array, básicamente se trata de comparar el primer 'carácter válido', con el último 'carácter válido', el segundo 'caracter válido', con el penultimo 'caracter válido' hasta llegar aunirse (que será o no el centor 'geométrico'.

Nota que la cuestión para no cometer errores, radica en: es 'carácter válido', lo mismo que en la descripción he marcado 'leer' entre comillas simples, para hacer notarlo...
De acuerdo. Una puntualización "pedantic" (perdón). Son los 'caracteres no válidos' los que delimitan las palabras dentro de una 'frase'

Esto sería un sencillo algoritmo que recorre el array tomando caracteres válidos de ambos extremos y comparándolos:

Código:
buleano = funcion Espalindromo(array bytes B() )
    entero j,k, n

    j= b.length -1 // tamaño del array
    Hacer mientras (k<j)
        hacer mientras b(k) sea espacio   // buscar siguiente 'carácter válido'
            k +=1
        repetir
    
        hacer mientras b(j) sea espacio   // buscar anterior 'carácter válido'
            j -=1
        repetir

        Si b(k) es distinto de b(j) devolver false
 
        k +=1
        j -=1
    repetir

    devolver true
fin funcion

Nota que además de espacio, podría haber tabuladores, y otros signos de puntuación, como comas ',' '; ':', etc... si se da el caso, mejor crear una función que busque el siguiente carácter válido, rechanzando todos los no aceptables... para rechazar solo uno o dos, basta hacerlo 'in situ'.

Hay una errata (no un error) , por dejar la variable k sin inicializar, (k=0). Pero 'entre humanos', no entre compiladores, eso es una errata.

Sin embargo, si tengo dos objeciones 'entre humanos' con este algoritmo:

  • la primera, importante, de corrección,. supongamos la entrada de una frase de 420 espacios ... Entonces el primer bucle anidado progresa indefinidamente más allá de los límites permitidos...Lo que invalida el cómputo
  • La segunda, no tan importante, de complejidad temporal (en constante). Supongamos una frase de 420 caracteres, el primero y el ultimo distintos de espacio e iguales entre si, y el resto, entre medias espacios. Por ejemplo A....418 espacios...A.  Entonces, el algoritmo recorre cada casilla es recorrida 2 veces (420), cuando se puede hacer en una vez.  Repito, es una diferencia de constante, O(2n), vs O(n) en el caso peor. No es tan grave.


Aqui propongo, en primera instancia, el pseudocodigo que propongo
Código:
  Pseudocode:
  -----------

 P:
  n,m=0,N
  while (n<m) and V[n]==' ')
    n=n+1
  while (n<m) and V[m-1]==' ')
    m = m - 1
 I:
  while (m -n > 1 ) and (V[n]==V[m-1] )
     n=n+1
     while (n<m) and V[n]==' ')
       n=n+1
     m = m - 1
     while (n<m) and V[m-1]==' ')
       m = m - 1
  done
  Q:
  return (m-n)<=1

Notemos que en el caso peor, cada casilla se recorre exactamente una vez. Que no nos lie el anidamiento de bucles.... (Se puede hacer sin anidamientos también, pero NEBIRE empezó asi la buena idea...) ::) Quizás una forma "repeat until" sería de lectura más fácil,  pero lo dejo así, por ser la forma canónica de la derivación dijkstra...

Código:
 init,
 while b do
   restore
   step
 done

Aquí va la implementación en C/C++, que aporto, puesto que estamos en la sección de C/C++.


Código
  1. #include <cstring> // strlen
  2. #include <string>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. int palindrome(const char* W)
  8. {
  9.  int i,j;
  10.  for(i=0,j=strlen(W); (i<j) && (W[i]==' ');i++);
  11.  for( ; (i<j) && (W[j-1]==' ');j--);
  12.  for( ; (j - i) > 1 && (W[i]==W[j-1]); )
  13.    {
  14.      for(i++; (i<j) && (W[i]==' ');i++);
  15.      for(j--; (i< j) && (W[j-1]==' ');j--);
  16.    }
  17.  return ((j-i) <= 1 );
  18. }
  19.  
  20.  
  21.  
  22. int main(int argc, char **args)
  23. {
  24.  string phrase;
  25.  for (; getline(cin,phrase); )
  26.    cout << palindrome(phrase.c_str()) << endl;
  27.  return 0;
  28. }

Estos son unos casos de prueba, donde 1 marca "true", y 0 "false". En el último caso, la linea solo contiene espacios, y como se ´lee igual' al derecho que al revés, da 1.

Código:
dabale arroz a la zorra el              abad
1
dabale arroz a                   la zorra el abad
1
dabale arroz al zorro el abad
0
                                                                                    
1


Y la guinda, (solo para aficionados al calculo Hoare y derivación Disjkstra). La justificación formal de su corrección.


Código:
  Palindrome on a given phrase, length(N) >= 0

  As a problem decission, we model it as an optimization problem

  P : W[N], N>= 0
  Q : 1 >= max i,j : 0 <=i <=j <= N and
                 (j>i) ->
                 ( V[i]!=' ' and V[j-1]!=' ' and
                   #k:0<=k<=i:V[k]!=' ' == #k:j<=k<=N:V[k-1]!=' ' and
                   V[i]!=V[j-1] )  
                   : j-i

i.e., the greatest segment not fullfilling palindrome conditions,
      1 or 0 if all of them fullfill.
      (see picture below)

                             (true)
                             15-16
                          ..........
              7----------------------------------24
          5----------------------------------------25
        4---------------------------------------------27
      3-------------------------------------------------28
    2-----------------------------------------------------29
  1---------------------------------------------------------30
0-------------------------------------------------------------31

0                                                               N=32
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|d|a|b|a|l|e| |a|r|r|o|z| |a| |l|a| |z|o|r|r|a| |e|l| |a|b|a|d| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


  (Long step strategy)

  B : (m-n) > 1 and V[n]==V[m-1]
  I :  0 <= n <= m <= N and
       (m-n> 1) -> (V[n]!=' ' and V[m-1]!=' ') and
       \forall i,j : 0 <= i < n and m<j<=N and
                     V[i]!=' ' and V[j-1]!=' ' and
    #k:0<=k<=i:V[k]!=' ' == #k:j<=k<=N:V[k-1]!=' '
                   :
                   V[i]==V[j-1] )
  
  C(m,n) = m -n >= 0
  Step: (At least decreases on 2, since B: m-n > 1 )
      n, m = n + (a-n), m-(m-b)
      where
         a = max i : n < i < m and AllessBl(V,n+1,i):i
         b = min i : a <= i < m and AllessBl(V,i,m-1):i


      
  O(n), despite the nested loops

 Pseudocode
  -----------

 P:
  n,m=0,N
  while (n<m-1) and V[n]==' ')
    n=n+1
  while (n<m) and V[m-1]==' ')
    m = m - 1
 I:
  while (m -n > 1 ) and (V[n]==V[m-1] )
     n=n+1
     while (n<m-1) and V[n]==' ')
       n=n+1
     m = m - 1
     while (n<m) and V[m-1]==' ')
       m = m - 1
  done
  Q:
  return (m-n)<=1


  
« Última modificación: 18 Abril 2018, 15:37 pm 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 [2] 3 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Palindromo con Pilas
Programación C/C++
Muffin 1 14,905 Último mensaje 28 Enero 2011, 02:32 am
por ricardo_b
Duda funcion palindromo
Programación C/C++
cazagavilan 2 3,040 Último mensaje 9 Abril 2012, 16:07 pm
por cazagavilan
palindromo « 1 2 »
Programación C/C++
ALONSOQ 16 12,808 Último mensaje 7 Agosto 2012, 17:52 pm
por X3R4CK3R
Palindromo C++ « 1 2 »
Programación C/C++
Bob1098 11 10,608 Último mensaje 23 Agosto 2014, 22:45 pm
por leosansan
Palindromo
Java
vhh70 7 5,195 Último mensaje 9 Junio 2016, 20:54 pm
por DIANA KARINA HM
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines