Funcion palíndromo.

Iniciado por ollessor, 16 Septiembre 2008, 18:27 PM

0 Miembros y 2 Visitantes están viendo este tema.

-Ramc-

Cita de: ҒrεακΠιи∂ en 18 Septiembre 2008, 00:50 AM
Cita de: Spider-Net en 17 Septiembre 2008, 20:00 PM
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 i <= len
no tendrias que usar otra variable ya que vas disminuyendo len, por lo que se afectaria la condición??

Shhh... be vewy, vewy, quiet!  I'm hunting wabbits...
LA PANDILLA MAS GRANDE DE MI CIUDAD, SE LLAMA POLICIA NACIONAL.

ҒrεακΠιи∂

Cita de: -Plaga- en 18 Septiembre 2008, 01:05 AM
Pones 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
Connoisseurs of C semantics find C++ inferior to ++C

Ragnarok

Cita de: Spider-Net en 17 Septiembre 2008, 13:04 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.

Cita de: ҒrεακΠιи∂ en 17 Septiembre 2008, 19:14 PMCreo 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.
No olvidéis leer las normas generales, además de las específicas de cada tablón.sgae, ladrones

ҒrεακΠιи∂

Buenas

Cita de: Ragnarok en 21 Septiembre 2008, 14:21 PM
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.

Cita de: Ragnarok en 21 Septiembre 2008, 14:21 PM
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
Connoisseurs of C semantics find C++ inferior to ++C

TheMaker

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.
Gibe money please or I report you

ҒrεακΠιи∂

Cita de: TheMaker 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.
BINGO!

Salu2, FreakMind
Connoisseurs of C semantics find C++ inferior to ++C

jorge.helu

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.

dijsktra

#17
Cita de: Spider-Net en 17 Septiembre 2008, 01:43 AM
Esto es una tontería pero bueno...


....
int Comprobar_frase (char frase[])
{
int longitud=strlen(frase);
int i=0;
while (i<=longitud/2 && frase[i]==frase[longitud-1-i])
 {
 i++;
 }
if (i>longitud/2)
  return 1;
  else
  return 0;
}
...


Quizás no sea tan tontería, amigo mío... :D  El

(i<=longitud/2)


hay que cambiarlo por


(i<longitud/2)


y el epílogo de la rutina

(i>longitud/2)

por

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

#18
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:


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

dijsktra

#19
Cita de: NEBIRE 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...
De acuerdo. Una puntualización "pedantic" (perdón). Son los 'caracteres no válidos' los que delimitan las palabras dentro de una 'frase'

Cita de: NEBIRE en 22 Marzo 2018, 16:55 PM
Esto sería un sencillo algoritmo que recorre el array tomando caracteres válidos de ambos extremos y comparándolos:


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

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


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 (cpp) [Seleccionar]

#include <cstring> // strlen
#include <string>
#include <iostream>

using namespace std;

int palindrome(const char* W)
{
 int i,j;
 for(i=0,j=strlen(W); (i<j) && (W[i]==' ');i++);
 for( ; (i<j) && (W[j-1]==' ');j--);
 for( ; (j - i) > 1 && (W[i]==W[j-1]); )
   {
     for(i++; (i<j) && (W[i]==' ');i++);
     for(j--; (i< j) && (W[j-1]==' ');j--);
   }
 return ((j-i) <= 1 );
}



int main(int argc, char **args)
{
 string phrase;
 for (; getline(cin,phrase); )
   cout << palindrome(phrase.c_str()) << endl;
 return 0;
}


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.

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.



 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


 

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)