A continuación voy a exponer un ejercicio que hemos tenido que hacer recientemente en la facultad sobre programación dinámica usando C como lenguaje de programación.

El ejercicio en sí consiste en la transformación de cadenas, es decir, obtenemos 2 cadenas de caracteres y debemos averiguar cuantos pasos hay que dar para transformar la primera cadena en la segunda, pero no se cualquier forma, sino buscando la mejor solución para ello.

La definición de programación dinámica se podría decir que es buscar la mejor solución a un problema, no una buena solución, sino la mejor. Para ello nos vamos a basar en una tabla de resultados en las que iremos guardando resultados intermedios para así, no realizar un cálculo dos veces. Aunque el cometido de este post no es el de definir que es la programación dinámica, existen muchos libros y San Google para encontrar la definición de esto.

Pues bien, empecemos.

¿Cual es la idea?, la idea mencionada anteriormente es que tenemos dos adenas (de igual o distinto tamaño) y queremos transformar una en otra, como por ejemplo:

cortejo -> cortijo

Este es el ejemplo típico que suelen dar en todos los libros.

¿Que es lo que hacemos?, lo más fácil es ir recorriendo la primera cadena e ir comparándola con la segunda y realizar alguna de las siguientes operaciones:

  • Insertar un caracter.
  • Sustituir un caracter.
  • Borrar un caracter.

Hagámoslo con un ejemplo visto en varias biografías.

Tenemos dos cadenas de caracteres, siendo la primera ‘abbac’ y queremos pasarla a ‘abcbc’, para ello podemos hacer lo siguiente.

screenshot_03

Aunque estos cambios no conseguimos el principio de optimalidad, es decir, la solución más óptima, ya que los cambios para la solución más óptima son los siguientes.

screenshot_02¿Cual es la función de recurrencia?.

Tenemos una tabla de NxM tabla[N][M] dimensiones y tenemos los siguientes casos bases (siendo i y j los índices que usaremos para recorrer la matriz).

  • Para tabla[0][j], el valor que añadiremos será el de j, ya que los cambios que necesitemos para pasar de una cadena de tamaño cero a la que estemos construyendo, será el tamaño que vaya tomando la misma (j).
  • Para tabla[i][0], el valor que añadiremos será el de i, igual que en el caso anterior pero con i.
  • Para tabla[0][0] el valor será cero, ya que para pasar de una palabra de tamaño cero a otr de tamaño cero no hay que hacer nada.

screenshot_04

for(i=0;i<m;i++){
        tabla[i][0]=i;
        for(j=0;j<n;j++){
            tabla[0][j]=j;
        }
    }

El codigo anterior refleja los casos base mencionados con anterioridad.

El caso general es el siguiente.

screenshot_05En el caso general debemos buscar el mínimo de los pasos que hemos ido dando hasta ese momento, siendo estos el anterior (inserción), el anterior en la diagonal (sustitución) y el que tenemos inmediatamente encima (borrado), a este mínimo le sumamos uno que es la nueva operación que realizamos.

Una vez hecho esto, es decir, definida la función de recurrencia, lo que nos queda es desarrollar el código, el cual quedaría así.

for(i=1;i<n;i++){
        for(j=1;j<m;j++){
            if(u[i]==v[j]){
                tabla[i][j]=tabla[i-1][j-1];
            }else{
/*
La siguiente llamada
la pongo en dos veces
ya que entera
me descuadra el blog
*/
                tabla[i][j]=1+calculaMinimo
(tabla[i][j-1],tabla[i-1][j],tabla[i-1][j-1]);
            }
        }
    }

La función calculaMinimo es una simple función donde calculamos el mínimo entre 3 números dados (los que mencionamos anteriormente).

Para no dejar el post cojo, la función que utilizo para calcularlo es esta:

int calculaMinimo(int a, int b, int c){
    int aux;
    aux = a<b?a:b;
    return aux<c?aux:c;
}

Para compilar el código en Linux me encontré con un problema a la hora de declarar las cabeceras de las funciones, y es que como normalmente las declaro en Windows (que sí funciona), en Linux no funcionaba. En los dos sistemas he usado tanto la IDE codeblocks como el compilador GCC.

Así es como lo declaraba en Windows.

int transformaCadena(int [][], char [], char []);

Y así como se debe hacer en Linux para que compile.

int transformaCadena(int [][M], char [], char []);

Una vez hecho esto, el programa funciona perfectamente tal y como podemos ver en las siguientes capturas.

Ejemplo: ‘abbac’ y queremos pasarla a ‘abcbc’.
pantallazo-ventana-sin-titulo

Ejemplo: cortejo -> cortijo.
pantallazo-ventana-sin-titulo-1

Pues esto es todo hasta aquí, en otro post explicaré que es eso de Modificación 1 y 2.

Leave a Reply


   Beat diabetes   Diabetes diet