Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

MANUAL TECNICO DE LAS TORRES DE HANOI

No description
by

Kevin Portilla

on 22 May 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of MANUAL TECNICO DE LAS TORRES DE HANOI

MANUAL TÉCNICO DE LAS TORRES DE HANOI
Resolución
El problema de las Torres de Hanói es curiosísimo porque su solución es muy rápida de calcular, pero el número de pasos para resolverlo crece exponencialmente conforme aumenta el número de discos. Existen algunas versiones del problema con un número diferente de varillas. Aunque se conocen algoritmos eficientes que resuelven el problema con 3 varillas de manera óptima, no se han encontrado aún sus contrapartidas para cualquier número (N igual o superior a 3) de ellas.
HISTORIA
Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas. Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
DESCRIPCIÓN

El juego, en su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes.
Solución simple
Una forma de resolver la colocación de la torre es fundamentándose en el disco más pequeño, en este caso el de hasta arriba. El movimiento inicial de este es hacia la varilla auxiliar. El disco número dos por regla, se debe mover a la varilla número tres. Luego el disco uno se mueve a la varilla tres para que quede sobre el disco dos. A continuación se mueve el disco que sigue de la varilla uno, en este caso el disco número tres, y se coloca en la varilla dos. Finalmente el disco número uno regresa de la varilla tres a la uno (sin pasar por la dos) y así sucesivamente. Es decir, el truco está en el disco más pequeño.
Mediante recursividad
Este problema se suele plantear a menudo en ámbitos de programación, especialmente para explicar la recursividad. Si numeramos los discos desde 1 hasta n, y llamamos X a la primera pila de discos (origen), Z a la tercera (destino) e Y a la intermedia (auxiliar) y a la función le llamaríamos hanoi (origen, auxiliar, destino), como parámetros, la función recibiría las pilas de discos. El algoritmo de la función sería el siguiente:

1. Si origen == {0}: mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino); terminar.
2. Si no: hanoi({0...n-1},destino, auxiliar) //mover todas las fichas menos la más grande (n) a la varilla auxiliar
3. mover disco n a destino //mover la ficha grande hasta la varilla final
4. hanoi (auxiliar, origen, destino) //mover todas las fichas restantes, {0...n-1}, encima de la ficha grande (n)
5. terminar
El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:

1. Sólo se puede mover un disco cada vez.
2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.

Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas.
Iterativa

Otra manera de resolver el problema, sin utilizar la recursividad, se basa en el hecho de que para obtener la solución más corta, es necesario mover el disco más pequeño en todos los pasos impares, mientras que en los pasos pares sólo existe un movimiento posible que no lo incluye. El problema se reduce a decidir en cada paso impar a cuál de las dos pilas posibles se desplazará el disco pequeño:


El algoritmo en cuestión depende del número de discos del problema.

* Si inicialmente se tiene un número impar de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila destino, y en cada paso impar se le mueve a la siguiente pila a su izquierda (o a la pila destino, si está en la pila origen).

La secuencia será DESTINO, AUXILIAR, ORIGEN, DESTINO, AUXILIAR, ORIGEN, etc.

* Si se tiene inicialmente un número par de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila auxiliar, y en cada paso impar se le mueve a la siguiente pila a su derecha (o a la pila origen, si está en la pila destino).

La secuencia será AUXILIAR, DESTINO, ORIGEN, AUXILIAR, DESTINO, ORIGEN

Una forma equivalente de resolverlo es la siguiente: coloreando los discos pares de un color y los impares de otro; se resuelve el problema añadiendo la siguiente regla: no colocar dos discos del mismo color juntos. De esta manera sólo queda un movimiento posible (además del de volver hacia atrás).
Curiosidades
A la hora de resolver matemáticamente el problema, nos encontramos con muchas curiosidades matemáticas respecto a la resolución. Son las siguientes:

* La ficha número n (siendo 1 la más pequeña) se mueve por primera vez en el paso número 2^(n-1), y después de ese primer movimiento, se moverá cada 2^n movimientos. De este modo, la ficha 1, se mueve en 1, 3, 5, 7, 9... etc. La ficha 3, se mueve en 4, 12, 20, 28, 32... etc
* El número de movimientos mínimo a realizar para resolver el problema es de (2^n)-1, siendo n el número de fichas.
* Todas las fichas impares (siendo 1 la más pequeña) se mueven siguiendo el mismo patrón. Asimismo, todas las fichas pares se mueven siguiendo el patrón inverso a las impares. Por ejemplo: si queremos mover un número impar de piezas desde la columna 1 hasta la 3, sucederá lo siguiente:

* Todas las fichas impares seguirán este patrón de movimiento: 1 -> 3 -> 2 -> 1 -> 3 -> 2 -> 1 -> 3 -> 2 -> 1.
* Todas las fichas pares seguirán este patrón de movimiento: 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3

Estos patrones dependen únicamente del número de piezas. Si el número de piezas es par, los patrones de las impares serán los de las pares, y viceversa.

* Uniendo la primera regla con la segunda, sabemos siempre qué pieza hay que mover y a qué columna hay que desplazarla, luego el problema está resuelto.
/*
{Pre: discos > 1 ^ discos = número de discos ^ ini,dest,aux = caracteres que identifiquen las torres}
{Post: Se escribe por el canal estándar de salida los movimientos a realizar, indicados a partir de
los caracteres que identifican las torres, para llevar todos los discos desde la torre inicial
a la de destino}
*/
void hanoi(int discos, char ini, char dest, char aux) {
if (discos == 1) cout << ini << " --> " << dest << endl;
else {
hanoi(discos - 1, ini, aux, dest);
cout << ini << " --> " << dest << endl;
hanoi(discos - 1, aux, dest, ini);
}
}

/*
Ejemplo de función que llama automáticamente a hanoi(int, char, char, char) solo dándole el número de discos
{Pre: discos > 1}
{Post: Se escribe por el canal estándar de salida los movimientos a realizar para llevar todos los discos
desde la torre de inicio hasta la de destino. Las torres serán identificadascomo A B C siendo la inicial A
y la de destino C}
*/
void hanoi(int discos) {
hanoi(discos, 'A', 'C', 'B');
}
%Hanoi usando recursividad en lenguaje Prolog

hanoi(N):- move(N,'A','C','B').

move(0,_,_,_):-!.

move(N, Src, Dest, Spare):- M is N-1, move(M, Src, Spare, Dest), primitive(Src, Dest), move(M, Spare, Dest, Src).

primitive(X, Y):- writelist([mueve, un, disco, desde, X, hasta, Y]), nl.

writelist([]).

writelist([H|T]):- write(H), write(' '), writelist(T).
Full transcript