Algoritmia III: divide y vencerás

Briefing: En estos días de confinamiento, me cuesta mucho sentarme y escribir algo para Tecnificados, entre unas cosas y otras no tengo tiempo, y el poco que me sobra estoy demasiado cansado como para redactar un artículo. En un ratillo, he conseguido escribir este, que es bastante sencillote...

Continuamos los diversos tipos de algoritmos, vamos a hablar de los famosos "divide y vencerás", su idea se basa en descomponer un problema en varios problemas más pequeños, resolver estos, y combinar sus soluciones. Normalmente, la recursividad nos acompañará en este tipo de soluciones.

Estos algoritmos se utilizan muchísimo en Big Data.

Este es el enunciado del problema que vamos a resolver usando este tipo de algoritmo:

   En el programa de la Casa de Empeños, hace unos días llevaron una bolsa de monedas de plata. Rápidamente llamaron a un experto, y este dijo que había una moneda falsa, pero para tasarla necesitaba saber si pesaba más o menos que las auténticas. En la oficina, solo tienen una balanza de dos pesas, para poder comparar el peso de una o varias monedas. 

  Vamos a diseñar un algoritmo y a implementar su solución, utilizando Divide y Vencerás. 

La solución en esta URL: La solución en nuestro repositorio: https://github.com/tecnificados/algoritmos/tree/master/divide

(Imagen Principal generada con https://es.cooltext.com/)

Algoritmia II: algoritmos voraces

Los algoritmos voraces son muy fáciles de entender y de implementar, por lo que se usan muy a menudo en programación.

Imaginaros un problema como este: en la mesa hay diez fragmentos de tarta de diferente grosor y peso, y un comensal quiere elegir los dos trozos que sean más grandes.

Al utilizar un algoritmo voraz, primero seleccionará el elemento de mayor peso y grosor, una vez seleccionado ya no puede volver a elegirlo, porque el algoritmo se lo ha "comido", de ahí su nombre.

Para solucionar el problema anterior mediante un algoritmo voraz podríamos realizar los siguientes pasos:

1. recorremos los diez fragmentos de tarta buscando el mas grande
2. escogemos el más grande
3. recorremos los nueve fragmentos restantes buscando el más grande
4. escogemos el más grande

Seguro que se os ocurren un par de formas de optimizarlo (como ordenar previamente los trozos).

Ahora vamos con un problema un poco más complejo:

En Tecnificados hemos organizado un festival de cine de terror. Durante 24 horas se proyectarán N películas diferentes en las 10 salas disponibles de cine de Metro City (cada película solo se proyectará una vez a lo largo del festival). En la programación aparecen todas las películas que se van a proyectar, junto con el título, duración de la película y otros datos, se indica la sala de proyección y la hora de comienzo.

Una persona desea planificar su maratón de cine, teniendo en cuenta que el único objetivo es ver el máximo número posible de películas. 

Debemos realizar un algoritmo voraz para realizar ese maratón.

La solución en nuestro repositorio: https://github.com/tecnificados/algoritmos/tree/master/voraz

(Imagen Principal generada con https://es.cooltext.com/)

Algoritmia: presentación

Para comenzar el año voy a iniciar una serie de artículos relacionados con los diferentes tipos de algoritmos.

Mi idea es comentar en cada artículo un diferente tipo de algoritmo (el primero será voraz), y mostrar una solución a un problema codificado en JAVA.

Se admiten sugerencias.

Imagen de cabecera obtenida de: https://es.wikipedia.org/wiki/Archivo:Algoritmo_de_Anillo.png