No se como implementar una función que que me detecte si un array de caracteres es palindromo. ¿Sabe alguien como puedo hacerlo?
Gracias. ;D
busca que ya se hablo justo de esto.
Crea un array auxiliar, inserta el original en el auxiliar empezando por el final, con esto el auxiliar tendra el original pero "dado la vuelta", comprueba si original y auxiliar son iguales, si lo son, entonces es palindromo.
Tmb puedes pasar de crear un nuevo array, compara posicion 0 con posicion n-1, 1 con n-2, 2 con n-3 .... siendo n el numero total de caracteres, si todos son iguales entonces palindromo
Esto es una tontería pero bueno...
#include <stdio.h>
#include <string.h>
#define TAMANIO 81
//Declaracion de Funciones***************************************************
void Introducir_frase (char frase[])
{
printf ("introducir una frase: ");
gets (frase); fflush (stdin);
}
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;
}
//F.Ppal*********************************************************************
int main (void)
{
char palindroma[81];
Introducir_frase (palindroma);
if (Comprobar_frase (palindroma))
printf ("Dicha frase es palindroma.");
else
printf ("Dicha frase no es palindroma.");
getchar();
return 0;
}
Buenas
Particularmente prefiero la respuesta de Spider a la de TheMaker (aunque tambien es valida) con algunas pequeñisimas modificaciones
Salu2, FreakMind
Cita de: Spider-Net en 17 Septiembre 2008, 01:43 AM
Esto es una tontería pero bueno...
Si es una tontería al menos hazlo un poco bonito, aunque para gustos los colores, pero por ejemplo habría que cambiar el void como argumento (no se pone) y el if innecesario, es como poner if i<j then return true else return false, se pone return i<j y listo. También el for está para algo, si tiene inicialización, comprobación y modificación de las variables inicializadas lo suyo es usar un for.
No es buena práctica que las funciones devuelvan void, pero tengo un poco de prisa, lo demás puedes verlo por ti mismo.
#include <stdio.h>
#include <string.h>
#define TAMANIO 81
//Declaracion de Funciones***************************************************
void Introducir_frase (char frase[]) {
printf ("introducir una frase: ");
gets (frase); fflush (stdin);
}
int Comprobar_frase (char frase[]){
int i, l;
for (i = 0, l=strlen(frase); i<=l/2 && frase[i]==frase[l-1-i]; i++);
return i>l/2;
}
//F.Ppal*********************************************************************
int main (){
char palindroma[81];
Introducir_frase (palindroma);
printf ("Dicha frase %s es palindroma.", Comprobar_frase(palindroma)?"":"no");
getchar();
return 0;
}
Cita de: Ragnarok en 17 Septiembre 2008, 11:50 AM
Cita de: Spider-Net en 17 Septiembre 2008, 01:43 AM
Esto es una tontería pero bueno...
Si es una tontería al menos hazlo un poco bonito, aunque para gustos los colores, pero por ejemplo habría que cambiar el void como argumento (no se pone) y el if innecesario, es como poner if i<j then return true else return false, se pone return i<j y listo. También el for está para algo, si tiene inicialización, comprobación y modificación de las variables inicializadas lo suyo es usar un for.
No es buena práctica que las funciones devuelvan void, pero tengo un poco de prisa, lo demás puedes verlo por ti mismo.
Es una tontería, y ese código lo tengo desde que empecé a estudiar programación. Estudio administración de sistemas y esto era uno de los primeros ejercicios que hicimos, así que simplemente lo busqué y lo colgué para ayudar a este compañero. Pero la verdad es que ni lo leí, seguramente se pueda mejorar sí.
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.
Pero bueno como tú has dicho, para gustos, los colores...
Saludos!
Buenas
Creo que para criticar, habria q criticar la actitud del que pidio el programa hecho...
Con respecto a si hay que poner o no void, es cuestion de gustos. Yo personalmente me parece que es mejor aclarar que esa funcion no lleva parametros utilizando void
Con el tema de usar o no void para el valor de retorno estoy entre el si y el no (un depende..). Si bien a veces es muy conveniente, otras no es necesario. Por ejemplo, si en la funcion tirara una excepcion, habria que ver si devolver algun valor es util.
Pero bueno, ya que dejaron el codigo... ahi va el mio XD
int isPalindromo(char *str)
{
int i = 0, len = strlen(str);
while( i <= len && tolower(str[i++]) == tolower(str[--len]) );
return i > len;
}
Jejejeej, pero eso es C++, el mío es en C :P
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
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 <= lenno tendrias que usar otra variable ya que vas disminuyendo len, por lo que se afectaria la condición??
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
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.
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
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.
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
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.
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
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'.
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)<=1Notemos 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++.
#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
Cita de: dijsktra en 4 Abril 2018, 17:48 PM
...
Sin embargo, si tengo dos objecciones 'entre humanos' con este algoritmo:
...
...por poner quejas, en la solución que propuse tampoco puse distinción de mayúsculas respecto de minúsculas, se da por sobreentendido... ya que esa no es la raíz del problema que requiere aclaración...
El objetivo del pseudocódigo, es abstraerse de tonterías como la inicialización de variables y cuestiones específicas de tal o cual lenguaje y centrarse en el problema de verdad... se inicializa exclusivamente las variables que sea precisas con el valor que toque, cuando sea distinto del valor por defecto para el tipo de datos...
Hay soluciones para ejercicios, y soluciones, profesionales. Creo que la cuestión tratada, entra en el de 'ejercicio de clase', que típicamente cada año, pondrán algunos profesores a sus alumnos. Si a un alumno, le presentan un problema y le dan un plazo de 2-4 días para entregarlo, carece de sentido que pierda el tiempo tratando de resolver todos los posibles problemas del mundo que se le presenten, porque entonces le faltaría tiempo... (yo le dediqué el tiempo que traté en escribirlo... 5 minutos o así y luego lo repasé levemente...
Se supone que al alumno, se le darán varias frases y deberá demostrar cuantas y cuales son palíndromas, y me temo que no le van a reclamar que el algoritmo solvente el problema en cualquier circunstancia posible (no habrá un botón nuclear que se active si falla) y en la realidad, no existen frases en ningún libro con 420 espacios (ni muchos menos) seguidos tal que deba comprobarse que sea palíndroma y desborde un bucle...
De todas maneras, si se trata de ser quisquilloso, mira como son las cosas... tu algoritmo fallará, con el siguiente palíndromo:
"Es Adán, ya ve yo soy Eva y nada se"Por qué, por que por lo mismo que tu te sacas de la manga los 420 espacios (que no figuran en ninguna frase razonable), yo me saco de la manga otros signos de puntuación que no son expresamente espacios, como la coma del ejemplo, un punto, un guión, dos puntos, un tabulador en vez de un espacio, etc... y que para el caso tampoco deben contar al considerar un palíndromo.... pero a diferencia de tus quejas, esto si es razonable que se dé en las frases...
p.d.: Tambén me resulta graciosa, esta frase:
Cita de: dijsktra en 4 Abril 2018, 17:48 PMDe acuerdo. Una puntualización "pedantic" (perdón). Son los 'caracteres no válidos' los que delimitan las palabras dentro de una 'frase'
Yo también estoy de acuerdo...
Cuando creo una función que deba aceptar o rechazar ciertos caracteres, típicamente la llamaré:
EsCaracterValido(...) ó
EsCaracterInvalido(...)
Pero
no tengo ninguna objección a que tu en tus códigos la llames:
EsCaracterQueDelimitaLasPalabrasDentroDeUnaFrase(...)
Perdón, tengo una
objeción contra mis "
objecciones".
En nuestra querida lengua,
objeción es con una c. Y
objección es un arcaísmo.
Mi latín me ha fallado (otras lenguas lo conservan, como el inglés,
object,
objection). Quien sabe... A lo mejor dentro de 500 años, los internautas vean que
objeción y
objeto, son arcaísmos, y mandan poner
ojeto y
ojeción, como ahora con
sujeto y
sujeción.
Cita de: dijsktra en 4 Abril 2018, 17:48 PM
Sin embargo, si tengo dos objecciones 'entre humanos' con este algoritmo:
Ya lo he cambiado allí.