INSTITUTO UNIVERSITARIO POLITECNICO “SANTIAGO MARIÑO”

EXTENSION CARACAS

LAS TORRES DE HANÓI

NOMBRE:CARLOS UGARTE

CEDULA:23.685.437

INTRODUCCIÓNAl igual que con programación dinámica y algoritmos ávidos, se busca resolver un problema a través de sus partes. La idea básica es ir dividiendo el problema en partes (generalmente dos) e intentar resolverlas. Si las partes son todavía demasiado complejas, se vuelven a partir. Se repite esto recursivamente hasta que pueda resolverse los problemas de manera directa. Una vez que se tienen estas respuestas, se juntan para obtener la solución general. Por otra parte, analizar y diseñar algoritmos de Divide y Vencerás son tareas que lleva tiempo dominar. Al igual que en la inducción, a veces es necesario sustituir el problema original por uno más complejo para conseguir realizar la recursión, y no hay un método sistemático de generalización. El nombre divide y vencerás también se aplica a veces a algoritmos que reducen cada problema a un único problema, como la búsqueda binaria para encontrar un elemento en una lista ordenada (o su equivalente en computación numérica, el algoritmo de bisección para búsqueda de raíces).

RESEÑA HISTORICA Se cuenta que en un templo de Benarés (Uttar Pradesh, India) se encontraba una cúpula

que señalaba el centro del mundo. Allí estaba una bandeja sobre la que existían tres agujas de diamante. En una mañana lluviosa, un rey mandó a poner 64 discos de oro ordenados por tamaño: el mayor, en la base de la bandeja, y el menor, arriba de todos los discos. Tras su colocación, los sacerdotes del templo intentaron mover los discos entre las agujas, según las leyes que se les habían entregado: «El sacerdote de turno no debe mover más de un disco a la vez, y no puede situar ningún disco encima de otro de menor diámetro». Hoy no existe tal templo, pero el juego aún perdura en el tiempo.

Otra leyenda cuenta que Dios, al crear el mundo, colocó tres varillas de diamante con 64 discos en la primera. También creó un monasterio con monjes, quienes tenían la tarea de resolver esta Torre de Hanói divina. El día que estos monjes consiguieran terminar el juego, el mundo acabaría. Sin embargo, esta leyenda resultó ser un invento publicitario del creador del juego, el matemático francés E. Lucas (En aquella época, era muy común encontrar matemáticos ganándose la vida de forma itinerante con juegos de su invención, de la misma forma que los juglares lo hacían con su música. No obstante, la falacia resultó ser tan efectista y tan bonita que ha perdurado hasta nuestros días. Además, invita a realizarse la pregunta: Si la leyenda fuera cierta, ¿cuándo sería el fin del mundo?)

EXPLICACIÓN DEL JUEGOEl objetivo del juego consiste en pasar los discos de un extremo al otro pero no de cualquier forma sino siguiendo unas precisas y sencillas normas que son las que dictó Brahma y que dictaremos a continuación: En cada movimiento solo podrán llevar un disco.El trabajo hay que hacerlo en el menor número de movimientos posibles.No se puede colocar nunca un disco mayor sobre otro menor.

SOLUCIÓN ALGORITMICA APLICANDO EL MÉTODO DIVIDE Y VENCERÁS

Para aplicar una estrategia divide y vencerás al problema sería necesario que los subproblemas tuvieran un tamaño aproximadamente mitad, es decir, debemos expresar la solución en función de mover n/2 discos.

El mover los n/2 discos superiores no plantea dificultades, ya que se dispone de cuatro postes accesibles. Sin embargo, al mover los n/2 discos inferiores sólo disponemos de tres postes, ya que uno no es accesible al contener la subtorre con los n/2 discos superiores.

Una forma de afrontar el problema es mover los n/2 discos inferiores utilizando el algoritmo de las torres de Hanói con tres postes. De esa forma, el algoritmo utilizado sería el que se muestra en la animación:

Este algoritmo se podría implementar de la siguiente forma:procedure Hanoi4( N: integer; Orig, Dest, Aux1, Aux2: char); var M : integer; begin if N = 0 then { En este caso base no se hace nada } else if N = 1 then writeln(output,Orig,' -> ',Dest) else begin M := N div 2; Hanoi4(N-M,Orig,Aux1,Dest,Aux2); Hanoi3(M,Orig,Dest,Aux2); Hanoi4(N-M,Aux1,Dest,Orig,Aux2) End end; La relación de recurrencia que se obtiene ahora es:T(0) = 0 T(1) = 1 T(n) = 2·T(n/2) + Q(2n)

ENLACE DEL JUEGO

http://www.uterra.com/juegos/torre_hanoi.php

CONCLUSIÓN

Este juego como mucho otros tiene la mejor manera de que el ser humano desarrolle virtudes con juegos de puzzle, además esta clase de juego nos convierten en personas estrategas. Además es un juego que puede ser jugado por niños, adolecentes y adultos.Esta clase de ejercicios mentales lo puedes hacer manualmente o descargarlo a tu PC para divertirte con este juego.

Además aplicando estos algoritmo presentados que un programador solo puede reconocer nos incita a entrar y profundizarnos en el área de la informática, computación, sistema y aprender mas para ser una persona eficaz y resolviendo cada problema que se le presente a su mejor manera.