Miércoles 16 de Octubre de 2024, 09:42
SoloCodigo
Bienvenido(a),
Visitante
. Por favor,
ingresa
o
regístrate
.
¿Perdiste tu
email de activación?
Inicio
Foros
Chat
Ayuda
Buscar
Ingresar
Registrarse
SoloCodigo
»
Foros
»
Programación General
»
C/C++
(Moderador:
Eternal Idol
) »
Función de Comparación
« anterior
próximo »
Imprimir
Páginas: [
1
]
Autor
Tema: Función de Comparación (Leído 1889 veces)
AdolfoC
Nuevo Miembro
Mensajes: 6
Función de Comparación
«
en:
Domingo 14 de Marzo de 2010, 20:07 »
0
Hola a todos. Tengo implementada en un programa una sencilla función que comprueba dígito a dígito los componentes de una palabra o frase sin espacios para mostrar si la misma es palíndrome o no (si puede leerse igual en uno u otro sentido). En teoría es un algoritmo sencillo, sin embargo siempre obtengo resultado negativo, nunca "es palíndromo". Me ayudaría alguno/a a comprobar el código? No soy capaz de ver el error... Muchas gracias de antemano!!!
int esPalindrom(char cad[], char cad2[], char espai)
{
int i,j,r;
//Borramos los espacios de la cadena.
borraEspai(cad, cad2, espai);
//Aplicamos el algoritmo de comprobación de palíndromo.
//Asignamos como fija la posición ES palíndromo.
//Comparamos el primer dígito con el último.
r = 1;
for(i=0; i < strlen(cad2)-1; i++)
{
for(j=strlen(cad2)-1; j >= 0; j--)
{
//Si alguna posición es diferente el valor r cambia a '0'.
if (cad2
!= cad2[j])
{
r = 0;
}
}
}
return r;
}
Tweet
jormar arellano
Nuevo Miembro
Mensajes: 10
Nacionalidad:
Re: Función de Comparación
«
Respuesta #1 en:
Domingo 14 de Marzo de 2010, 21:18 »
0
Mi estimado, que te parece si hacemos una corrida en frío rápidamente?, probemos con la palabra "aba".
Una vez que entramos en el ciclo de comparación, tenemos:
( strlen("aba") = 3 )
i=0, ahora entramos en otro ciclo,
comparando cad2[0] con todas las demás letras de la palabra ( cad[j], pasando j por los valores 2,1,0)
.
i=0, j=2, cad2
== cad2[j] ('a' == 'a')
i=0, j=1, cad2
== cad2[j] ('a' == 'b')
(nota que seguimos parados en la primera 'a', pero ahora comparandola con la penultima letra)
--> r = 0
(pero el rollo no termina alli, según el algoritmo que implementaste, debo terminar de comparar TODAS las letras que quedan, a pesar de saber que ya no son palíndromes las palabras)
i=0, j=0, cad2
== cad2[j] ('a' == 'a').
i=1, j=2, cad2
== cad2[j] ('b' == 'a') (en ese punto ya debes saber que anda mal... pero, por si acaso, nota como comparas la letra del medio con la ultima)
--> r = 0
i=1, j=1, cad2
== cad2[j] ('b' == 'b').
i=1, j=0, cad2
== cad2[j] ('b' == 'a').
--> r = 0
...etc etc.
Como recomendación adicional, calcula el largo de la palabra una sola vez:
Código: C++
int
length2
=
strlen
(
cad2
)
;
...
for
(
i
=
0
;
i
<
length2
-
1
;
i
++
)
{
...
}
..esto por razones de eficiencia, ya que la función strlen se ve obligada a recorrer toda la palabra para saber cual es su largo. Si además de eso, tu iteras sobre la palabra (para ir comparando letra por letra), tendrías que, por cada letra que tu comparas, obligas a recorrer toda la palabra de nuevo para saber su largo (en la condición de parada del ciclo). Has unas cuentas:
Si la palabra tiene 10 letras: tu te paras en cada una de las 10 letras y, en cada ciclo, obligas a calcular el largo de la palabra (10 iteraciones más); total: 100 itteraciones.
Si la palabra tiene 25 letras: 25 x 20 = 500 iteraciones!!!
(En computación, se dice que tienes un rendimiento de orden O(n^2))
En cambio, Calculando el largo de la palabra al principio, tendrías, para una palabra de 20 letras: 25 iteraciones iniciales para saber su largo (guardandolo en una variable) + 20 iteraciones tuyas (para tus comparaciones) = 45 iteraciones.
AdolfoC
Nuevo Miembro
Mensajes: 6
Re: Función de Comparación
«
Respuesta #2 en:
Lunes 15 de Marzo de 2010, 00:01 »
0
Hola Jormar. Te agradezco enormemente que hayas comentado tan correctamente el funcionamiento del código y la forma de iteración del mismo, no era capaz de verlo. Ahora tengo muy claro el funcionamiento y lo arreglaré según explicas.
Muchas gracias.
Imprimir
Páginas: [
1
]
« anterior
próximo »
SoloCodigo
»
Foros
»
Programación General
»
C/C++
(Moderador:
Eternal Idol
) »
Función de Comparación