Funcion palíndromo.

[-Ramc-]

Jejejeej, pero eso es C++, el mío es en C 

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

Pones

Código [Seleccionar] Expandir

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

[ҒrεακΠιи∂]

Pones

Código [Seleccionar] Expandir

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

[Ragnarok]

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.

[ҒrεακΠιи∂]

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

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

[ҒrεακΠιи∂]

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

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

Esto es una tontería pero bueno...

Código (c) [Seleccionar] Expandir


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

Código [Seleccionar] Expandir


(i<=longitud/2)

hay que cambiarlo por

Código [Seleccionar] Expandir


(i<longitud/2)

y el epílogo de la rutina

Código [Seleccionar] Expandir

(i>longitud/2)

por

Código [Seleccionar] Expandir

(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

[Serapis]

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 [Seleccionar] Expandir


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]

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 [Seleccionar] Expandir


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 [Seleccionar] Expandir


 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 [Seleccionar] Expandir


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


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

Código [Seleccionar] Expandir

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 [Seleccionar] Expandir


 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