• Lunes 27 de Mayo de 2024, 18:22

Autor Tema:  Función de Comparación  (Leído 1818 veces)

AdolfoC

  • Nuevo Miembro
  • *
  • Mensajes: 6
    • Ver Perfil
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;
}

jormar arellano

  • Nuevo Miembro
  • *
  • Mensajes: 10
  • Nacionalidad: ve
    • Ver Perfil
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++
  1.  
  2. int length2 = strlen(cad2);
  3. ...
  4. for ( i=0; i<length2 - 1; i++){ ... }
  5.  
  6.  

..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
    • Ver Perfil
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.