Page 41 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 41
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Así, queda un algoritmo de tiempo constante:
T(n) O (1).
ejeMplo 3. torreS de HaNóI
El juego de las torres de Hanói involucra tres postes y n discos de diámetros 1, 2, 3,…, n. El juego
inicia con todos los discos apilados sobre uno de los postes en orden creciente de la parte superior
hacia abajo. El juego consiste en colocar todos los discos en otro poste obedeciendo las siguientes
reglas:
1. Mover solo un disco a la vez.
2. Nunca colocar un disco sobre un disco de menor diámetro.
El origen del juego y la siguiente leyenda (quizá con alguna reserva) se atribuye a escritor inglés en
matemáticas recreativas W. Rousse-Ball.
Cuenta la leyenda que en el gran templo de Benarés, bajo la cúpula que señala el centro del mundo,
reposa una bandeja de cobre en la que están plantadas tres agujas cuyo diámetro es más fino que el
aguijón de una abeja. En el momento de la creación, Dios colocó en una de las agujas 64 discos de
oro puro ordenados por tamaño: desde el mayor que rebosa sobre la bandeja hasta el más pequeño,
en lo más alto del montículo. Es la torre de Brahma. Incansablemente, día tras día, los sacerdotes
del templo mueven los discos haciéndoles pasar de una aguja a otra, de acuerdo con las leyes fijas e
inmutables de Brahma, las cuales evitan que el sacerdote en ejercicio mueva más de un disco al día
o lo sitúe encima de un disco de menor tamaño. El día en que los 64 discos hayan sido trasladados
desde la aguja en que Dios los puso al crear el mundo a cualquiera de las otras dos, ese día la torre,
el templo y, con gran estruendo, el mundo desaparecerán (Dewdney, 1989).
Opción A: Solución recursiva
El pseudocódigo es el siguiente:
Hanói (N, Origen, Destino, Auxiliar)
Si N = 1
imprime “Mover disco de” Origen “a” Destino; si no
Hanói (N-1, Origen, Auxiliar, Destino)
imprime “Mover disco de” Origen “a” Destino
35
