 Autor
|
Tema: Funcion palíndromo. (Leído 22,334 veces)
|
-Ramc-
 Desconectado
Mensajes: 495
|
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 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
Mensajes: 184
|
Pones 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
|
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
|
|
|
|
ҒrεακΠιи∂
Desconectado
Mensajes: 184
|
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
Mensajes: 514
|
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
Mensajes: 184
|
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
Mensajes: 2
|
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
Mensajes: 110
Mr Edsger Dijsktra (Tribute to)
|
Esto es una tontería pero bueno... .... int Comprobar_frase (char 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 hay que cambiarlo por y el epílogo de la rutina por 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
|
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'. |
|
|
|
« Última modificación: 22 Marzo 2018, 16:58 pm por NEBIRE »
|
En línea
|
|
|
|
dijsktra
Desconectado
Mensajes: 110
Mr Edsger Dijsktra (Tribute to)
|
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: 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++. #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
|
|
|
|
« Ú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)
|
|
|
|
| Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
Palindromo con Pilas
Programación C/C++
|
Muffin
|
1
|
14,867
|
28 Enero 2011, 02:32 am
por ricardo_b
|
|
|
|
Duda funcion palindromo
Programación C/C++
|
cazagavilan
|
2
|
3,004
|
9 Abril 2012, 16:07 pm
por cazagavilan
|
|
|
|
palindromo
« 1 2 »
Programación C/C++
|
ALONSOQ
|
16
|
12,690
|
7 Agosto 2012, 17:52 pm
por X3R4CK3R
|
|
|
Palindromo C++
« 1 2 »
Programación C/C++
|
Bob1098
|
11
|
10,495
|
23 Agosto 2014, 22:45 pm
por leosansan
|
|
|
|
Palindromo
Java
|
vhh70
|
7
|
5,091
|
9 Junio 2016, 20:54 pm
por DIANA KARINA HM
|
 |
