Tarea #2 Divide y vencerás

Divide y vencerás

La técnica consiste en dividir un problema en almenos 2 partes (instancias) del problema, resolver (vencer) estas instancias y obtener una solución general del problema, combinando las soluciones de los sub problemas.

Pseudocódigo:

funcion divide&venceras(problema)

{

Si problema es suficientemente pequeño o sencillo:

return (solucion tradicional del problema)

descomponer el problema en n subproblemas más pequeños;

para i=1 hasta n hacer

resolver el subproblema k

combinar las n soluciones

}

Problemas en los que se utiliza:

• Torres de Hanói
• Serie de Fibonacci
• Recursión
• Multiplicación rápida de enteros largos
• Multiplicación rápida de matrices
• Algoritmo de búsqueda binaria.
• Algoritmos de ordenación ( Algoritmos de ordenación (Mergesort Mergesort, Quicksort Quicksort)..
• Problema de la selección (p.ej. mediana)
• Exponenciación rápida.
• Subsecuencia de suma máxima.
• Par de puntos más cercano.
• Eliminación de superficies ocultas.

• Número de inversiones (rankings).
• FFT: Transformada Rápida de Fourier (convoluciones)
• Interacciones entre n partículas

 Cuando conviene utilizarlo:

Existen condiciones por las cuales de antemano podemos determinar si conviene utilizatrlos.

• Debe ser posible descomponer el problema en subproblemas.
• Debe ser posible recomponer las soluciones de una manera eficiente.
• Los subproblemas deben ser, en lo posible, del mismo tamaño.

Cuando NO conviene utilizarlo:

Por otra parte hay otras condiciones que nos ayudan a determinar si no es posible o cuándo no utilizar el algoritmos de DyV.

• Si el tamaño de los subproblemas es casi del mismo tamaño que el original.
• Si la cantidad de subproblemas es casi la misma que el tamaño del problema.
• Cuando no se puede aplicar recursión

Aplicación de Búsqueda Binaria en Java:

Descargar aquí:
https://dl.dropboxusercontent.com/u/41478854/Bin.java

Código:

public class Bin{

    private static int valorBuscado;
    private static int longitud;
    private static int[] lista;
    private static int punto;
    private static int cont;

    public static int binary(int izq, int der, int valor, int lista[]){
 punto = (izq+der)/2;
 if(lista[punto] < valor){
     cont += 1; //cada vez que sea menor aumentar el contador
     // si resulta que es mayor a 2 veces
     if(cont > 2) return 404; //404 entonces no lo encontro
     binary(punto,der,valor,lista);
 }
 if(lista[punto]>valor){
     binary(izq,punto,valor,lista);
 }
 if(lista[punto] == valor){
     return punto; //retornar el indice
 }
 
 return 404;//no lo encontro
    }

    public static void rellenar(){
 int con = 0;
 for(int i=0;i<longitud;i++){
     lista[i] = con;
     con += 2;
 }

    }
    public static void imprimir(){
 for(int i=0;i<longitud;i++){
     System.out.printf(" %d ",lista[i]);
 }
 
    }

    public static void main(String args[]){
 //recibimos argumentos
 valorBuscado= Integer.parseInt(args[0]);
 longitud= Integer.parseInt(args[1]);
 lista = new int[longitud];
 //En un principio siempre inicia desde 0 el valor izquierdo
 int izq = 0;
 System.out.println("valor buscado: "+valorBuscado);
 //rellena la matriz
 rellenar();
 //imprime la matriz
 imprimir();
 //Imprime el indice donde se encuentra el valor buscado
 System.out.println("\nINDICE: "+binary(izq,longitud,valorBuscado,lista));

    }

}

Necesita 2 argumentos, el primero es para el número a buscar y el segundo es para indicar la longitud de la lista.

En caso de que el número solicitado lo encuentre en la lista nos indicará el indice en donde se localiza:

En caso de que el número solicitado NO lo encuentre en la lista nos indicará indice: 404, es decir no encontrado:

Referencias:

Introduction to algorithms 3rd Edition, MIT, 2009, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest Clifford Stein.

http://elvex.ugr.es/decsai/algorithms/slides/3%20DV.pdf
http://www.algoritmia.net/articles.php?id=34
http://ce.azc.uam.mx/profesores/franz/omi/recursion3.html

http://www.cs.us.es/~jalonso/cursos/i1m-12/temas/tema-23t.pdf

http://revistas.ua.pt/index.php/ID/article/view/1240/1134

http://web.eecs.umich.edu/~aprakash/eecs282/lectures/11-recursion.pdf