Home › Blogs › manueldavid's blog

Divide y vencerás

Sun, 2008-02-17 13:15 — manueldavid
Esta receta pretende dar a conocer al lector en qué consiste la técnica de diseño de algoritmos “divide y vencerás”. Para ello se incluyen a continuación unas breves nociones teóricas y un ejemplo práctico sencillo.

¿En qué consiste la técnica “divide y vencerás”?


En el mundo de las ciencias de la computación es una técnica de diseño de algoritmos que consiste en resolver un problema a partir de la solución de subproblemas del mismo tipo, pero de menor tamaño. Si los subproblemas son todavía relativamente grandes se aplicará de nuevo esta técnica hasta alcanzar subproblemas lo suficientemente pequeños para ser solucionados directamente. Por último, habrá que combinar las soluciones obtenidas en los subproblemas para obtener la solución del problema inicial.

Estructura del algoritmo en versión recursiva

El pseudocódigo del algoritmo Divide y Vencerás en versión recursiva es el siguiente:

    DYV{
         if(facil(tamaño))
             return (resolver(tamaño))
         else{
             dividir(tamaño)
             //Suponemos j divisiones
             return (combinar(DYV, …, DYV))
         }
      }

Estructura del algoritmo en versión iterativa

El pseudocódigo del algoritmo Divide y Vencerás en versión iterativa es el siguiente (yo personalmente he visto muchas más veces implementada la versión recursiva que esta iterativa):

    DYV{
         while(tamaño >= 1){
              for(i=1; i<=k; i++)
                   s[i] = resolver(ni);
              combinar(s);
              modificar(tamaño);
         }
    }

Ejemplo sencillo de la técnica “divide y vencerás” en C


Se trata de solucionar el siguiente problema:
Diseñe un algoritmo “Divide y Vencerás” que calcule xn (x elevado a n) con un coste O(n log n).

   int exponencial_n(int base, int exponente){
 
	int resultado_parcial;
	int exponente_actual;
 
	switch(exponente){
		case 0:
			return 1;
		break;
 
		case 1:
			return base;
		break;
 
		case 2:
			return (base * base);
		break;
 
		default:
			exponente_actual = exponente/2; /*Dividimos a la mitad*/
			resultado_parcial = exponencial_n(base, exponente_actual);
 
			if(exponente % 2 == 0)
				return resultado_parcial*resultado_parcial; /*si el exponente es par*/
			else
				return resultado_parcial*resultado_parcial*base; /*si es impar*/
	}
}

Bibliografía

  • “Divide y vencerás”, Ampliación de programación. ESI. Miguel Angel Redondo.
  • Divide y vencerás