Programación: Todas las noticias

19 septiembre 2006

Torres de Hanoi

Alfonso Jiménez

“Al crear el mundo, Dios situó sobre la Tierra tres varillas de diamante y 64 discos de oro. Los discos son todos de diferente tamaño e inicialmente fueron colocados en orden decreciente de diámetros sobre la primera de las varillas. También creó Dios un monasterio cuyos monjes tienen la tarea de trasladar todos los discos desde la primera varilla a la tercera. La única operación permitida es mover un disco de una varilla a otra cualquiera, pero con la condición de que no se puede situar encima de un disco otro de diámetro mayor. La leyenda dice también que cuando los monjes terminen su tarea, el mundo se acabará”.

El otro día alguien preguntó para qué servían los números de Mersenne. El número mínimo de movimientos para resolver el juego de las Torres de Hanoi viene dado por los números de Mersenne (M=2ⁿ-1 con n primo), siendo el n el número de discos a trasladar. Por lo tanto, los monjes hubiesen necesitado 2⁶⁴-1 = 18446744073709551615 movimientos para resolver el juego con 64 discos. Si suponemos que los monjes realizan un movimiento por segundo tardarían 58454204609 siglos y 6 años en completar el traslado, contando con que no descansen ni un solo segundo en ese tiempo ni que cometan ningún fallo, pues el tiempo que hemos calculado ha sido el mínimo número de movimientos, es decir, hemos excluido los posibles fallos. Lógicamente si resolvemos este problema para 64 discos el mundo no se acaba Existe un algoritmo recursivo donde podemos ver una sencilla solución al problema:

hanoi(n, Orig, Aux, Dst)
si (N>0) hacer
hanoi(n-1, Orig, Dst, Aux)
escribir(Movemos Orig a Dst)
hanoi(n-1, Aux, Orig, Dst)

Continuar leyendo...

Más noticias sobre:  Matemáticas, Programación
Comentarios (5)

13 septiembre 2006

Algoritmos Voraces: Problema del viajante con prisa

Alfonso Jiménez

Seguimos con problemas que se pueden resolver mediante algoritmos voraces. Vamos imaginar que tenemos a una persona que desea viajar en coche desde un punto A hasta otro punto B (n kilómetros). El viajante dispone de un mapa de carretera que indica la distancia entre las gasolineras que están situadas en el trayecto que va a realizar. En el punto de origen, el tanque del coche se encuentra lleno. Conocemos un máximo de kilómetros que el coche puede realizar sin la necesidad de repostar (x kilómetros / xsu objetivo es pararse a repostar el menor número de veces posibles. El algoritmo voraz nos determinará en qué gasolineras el viajante tiene que parar a repostar.

Continuar leyendo...

Más noticias sobre:  Matemáticas, Programación
Comentarios (6)

06 septiembre 2006

Algoritmos Voraces: Problema del cambio de monedas

Alfonso Jiménez

Los algoritmos voraces (greedy algorithms en inglés) son unas rutinas muy eficientes (O(n), O(n²)) aunque no suelen proporcionar la mejor solución a un problema. Existen algoritmos voraces muy conocidos, como el Algoritmo de Dijkstra o el Algoritmo de Kruskal. Vamos a resolver mediante un algoritmo voraz el conocido Problema del cambio de monedas. El problema se presenta de la siguiente forma: Dado un sistema monetario S de longitud K y una cantidad de cambio C, devolver una solución (si existe) que nos indique el número de monedas de S equivalente a C, es decir, que nos muestre el cambio para C a partir de monedas de S. Veamos un ejemplo:

En este ejemplo nos proporcionan un sistema monetario que contiene monedas de valor 10, 6, 5 y 1. La cantidad que debemos cambiar es C=12. El algoritmo voraz siempre intentará realizar el cambio mediante monedas del mayor valor posible. Si en algún paso C es menor estricto que S[t] (t≤K), se incrementará t y repetiremos el mismo paso para la siguiente moneda de S. Al finalizar, el algoritmo voraz nos indica que el cambio resultante para 12 son dos monedas de 1 y una de 10. Cómo he comentado al principio los algoritmos voraces en muchas ocasiones no presentan la mejor solución, pues en éste ejemplo sería mejor cambiar 12 por dos monedas de 6, entendiendo por mejor solución devolver el menor número de monedas posibles.

Continuar leyendo...

Más noticias sobre:  Matemáticas, Programación
Comentarios (7)

« Página anterior