Ir al contenido principal

Algoritmia II: algoritmos voraces

Imagen
De

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/)
Etiquetas:

Entradas populares de este blog

Spring Boot: Página inicial con Bootstrap

De
  Este es el segundo artículo de la serie sobre Spring Boot que comenzamos hace dos semanas, si quieres ver el primero puedes acceder pulsando aquí . En el primer artículo vimos cómo descargar nuestro proyecto configurado para nuestros intereses y listo para ser importado en nuestro IDE (nosotros usaremos Eclipse ). Lo primero que vamos a hacer es importar el proyecto: File -> Import Existing Maven Projects Seleccionamos el fichero pom.xml en la carpeta donde lo hemos descomprimido y esperamos unos segundos Cuando acabe la importación, esta es la estructura que nos aparecerá: Con Spring Boot no necesitamos configurar el servidor, ya se encarga él de facilitarnos la vida. Lo único que tenemos que hacer es arrancar la clase BootApplication.java , que se encargará de arrancar Tomcat y dejar nuestra aplicación funcionando en el puerto 8080.  Y si todo fuera bien, podríamos acceder a través de la URL:  http://localhost:8080/ Pero ahora mismo tenemos un error de conexión c...
Leer más

Redirección de puertos en Virtual Box

De
Continuando con mis anteriores "posts", vamos a terminar nuestro entorno de pruebas redirigiendo los puertos que nos interesan de la máquina virtual a nuestro PC. Con Virtual Box podemos configurar la red de diversas formas, una de ellas es redireccionar los puertos de la máquina virtual a la nuestra. Es bastante fácil y rápido de configurar, y lo que hace es que tengamos unos puertos destinados al entorno de desarrollo y otros para el entorno de pruebas. Ejemplo de uso:  - podemos usar el puerto 8080 para desarrollar en eclipse en nuestro entorno de desarrollo con Tomcat. - usaremos el puerto 80 para el Tomcat del entorno de pruebas Más adelante veremos cómo configurar las redes de virtual box para que sean máquinas independientes conectadas a nuestra red y más opciones. Vamos a hacer la redirección del puerto 22 para poder acceder a nuestra máquina virtual a través de uno de los clientes ssh más extendidos (y con nombre controvertido): ...
Leer más

Un bot con Telegram en Termux

De
En las últimas semanas he retomado un par de ideas que tuve hace algunos años: por un lado la idea de hacer un Bot con el que hacer operaciones a través de comandos específicos. En concreto me gustaría hacer poder realizar comandos de inversión en bolsa (de manera ficticia) por otro lado desplegar la aplicación en un móvil con Termux (emulador de Linux para Android) Así que os cuento los pasos que he hecho para realizar estas tareas. Creación de Bot con Telegram Busca el contacto @BotFather (es el bot oficial de Telegram para crear otros Bots). Pulsa en Iniciar o escribe /start para comenzar. Escribe el comando: /newbot BotFather te pedirá que le pongas un nombre visible a tu Bot. Ejemplo: Nombre: MiBotJava Luego te pedirá un username único que termine en Bot. Ejemplo: Username: MiBotJava_bot Si el nombre de usuario está disponible, te dará un mensaje de éxito. Obtén el token Después de crear el Bot, BotFather te dará un mensaje como este: Done! Congratulations on your new bot. You wil...
Leer más