INSTITUTO POLITÉCNICO NACIONAL

ESCUELA SUPERIOR DE INGENIERÍA MECÁNICA Y ELÉCTRICA

ESIME CULHUACÁN

PROBLEMA DE LAS TORRES DE HANOI

LÓPEZ BALDERAS JAVIER EDGARD

ESTRUCTURAS DE DATOS

MARTÍNEZ PIRO IXCHEL

3CV2

FECHA: 27/AGOSTO/2013

Las torres de Hanoi son un juego que se inventó en 1883 por un matemático francés.

Es un juego solitario, consiste en 8 discos de radios crecientes, que se deben apilar en una de las tres estacas del tablero de juego. El objetivo del juego es acomodar esa misma pila inicial en otra de las estacas siguiendo ciertas reglas, este juego es muy común en las ciencias de la computación y aparece en muchos libros como una introducción a la teoría de algoritmos.

El tablero tradicional consiste en una base horizontal con tres estacas posicionadas verticalmente en la base y separadas una de otra.

En una de las estacas se apilan los discos duelen ser de madera, el número de discos determina la complejidad de la solución, como regla general se consideran ocho discos, los cuales se apilan en una de las estacas en tamaño decreciente, no hay discos del mismo tamaño, todos ellos están apilados de mayor a menor radio en una de las estacas, quedando las otras dos estacas vacías.

Este juego consiste en pasar todos los discos de la estaca inicial a una de las otras considerando las tres siguientes reglas:

1. Se puede mover solo una pieza por turno.2. Un disco mayor no puede quedar en ningún momento sobre uno más pequeño que él.3. Solo se puede mover el disco que esté hasta arriba de la pila que se forme en cada estaca.

La historia cuenta que en un templo de la India los monjes tenían que resolver este problema pero con 64 discos, la leyenda dice que antes de que eso pasara el templo se haría cenizas y sacando los cálculos es seguro que así sería ya que con ese número de fichas se tendrían que hacer 1 movimiento por segundo en miles de millones de años.

La resolución del juego es muy sencilla, pero por cada disco más en la torre los pasos para resolver el problema crece en forma exponencial.

1

Una de las formas de resolver el problema se basa en el disco más pequeño, el movimiento inicial de este es hacia la estaca auxiliar, el disco dos se debe mover por regla a la estaca final, luego en disco número uno se mueve al final, el disco tres se coloca en la estaca auxiliar, finalmente el disco uno regresa a la estaca inicial, etc. La clave es mover el disco más pequeño.

Este problema se suele plantear en cursos de computación, principalmente en programación para explicar la recursividad. Se numeran los discos de uno hasta n, se le llama origen a la primera pila de discos, auxiliar a la de en medio y destino a la que sigue; se hace una función que se llame hanoi con origen, auxiliar y destino como parámetros.

Algoritmo de la función:

Inicio:

Entran datos: 3 Discos, Estaca inicial.

Salida: Estaca de destino.

1. Si origen es igual a A entonces:1.1. Mover disco 1 de A a Destino1.2. Terminar

2. Si no2.1 hanoi ({1,…,n-1},destino,auxiliar) mover todas las fichas menos la más grande (n) a la estaca auxiliar.

3. Mover disco (n) a destino.

4. hanoi(auxiliar,origen,destino) mover todas las fichas restantes 1…n-1, encima de la ficha grande.

5. terminar.

Con este algoritmo también se pueden calcular el número de movimientos mínimos a realizar para resolver el problema: 2n – 1, siendo n el número de discos.

Utilizando la herramienta de Borland C, y este algoritmo se tratará de dar una solución en una secuencia de pasos, todo usando la recursión en programación (funciones recursivas).

Los algoritmos son conjuntos ordenados y finitos de operaciones que permiten hallar la solución de algún problema, se pueden clasificar de muchas maneras de acuerdo a su estructura, construcción, etc.

La recursión como la iteración buscan que el algoritmo se ejecute en forma secuencial y consecutiva en un cierto número de veces. La diferencia entre estas es que la iteración ejecuta el algoritmo completamente antes de volverlo a llamar, mientras que la recursión llama al mismo algoritmo para poder resolverlo.

2

#include <iostream>#include <conio.h>#include <math.h>void hanoi(int iNumeroDiscos,char A,char C,char B){

if(iNumeroDiscos==1) { cout<<"Mover el disco "<<iNumeroDiscos<<" de "<<A<<" hasta "<<C<<endl; } else { hanoi(iNumeroDiscos-1,A,B,C);

cout<<"Mover el disco "<<iNumeroDiscos<<" de "<<A<<" hasta "<<C<<endl;

hanoi(iNumeroDiscos-1,B,C,A); }}main(){

int iDiscos, iSalir; char A,B,C; do { cout<<"ESTE PROGRAMA RESUELVE EL PROBLEMA DE LAS TORRES DE HANOI USANDO 3 ESTACAS"<<endl; cout<<"\n\n\nIngrese el numero de discos con los que va a jugar y presione [ENTER]: "; cin>>iDiscos; cout<<"\n\n\nEl problema con "<<iDiscos<<" discos, se resuelve minimo en "<<pow(2,iDiscos)-1<<" movimientos. \n\n\n"<<endl; hanoi(iDiscos,'A','C','B'); cout<<"\n\nEl pograma ha terminado presione 1 para continuar o 2 para salir: "; cin>>iSalir; cout<<"\n\n\n"; clrscr(); }while(iSalir==1); cout<<"\n\t ESCUELA SUPERIOR DE INGENIERIA MECANICA Y ELECTRICA \n\n"<<endl; cout<<"\t\t Alumno: LOPEZ BALDERAS JAVIER EDGARD \n\n"<<endl; cout<<"\t\t Materia: ESTRUCTURA DE DATOS \n\n"<<endl; cout<<"\t\t Profesora: MARTINEZ PIRO IXCHEL \n\n"<<endl; cout<<"\t\t Grupo: 3CV2 \n\n"<<endl;getch();}

Conclusiones personales:

Al comparar los códigos de este mismo problema pero iterativos se puede observar que un algoritmo recursivo es más simple (requieren menos líneas de código) que los iterativos, pero toman más tiempo de computación

Bibliografía:

Estructura de datos 3ra edición, McGrawHill Osvaldo Cairó, Silvia Guardati, www.Wikipedia.com.

3