Page 42 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 42
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Hanói (N-1, Auxiliar, Destino, Origen) (Cairó y Guardati, 2000).
Y el código del algoritmo 1.11 se observa en lenguaje de programación C de la siguiente forma:
Algoritmo 1.11. Programación de las torres de Hanói
Siendo N el número de anillos y T el tiempo para colocar los N anillos de la espiga origen a la espiga
destino, se tiene:
T(N) = 2T(N-1) + 1
La estrategia es mover los N-1 discos de una espiga a otra (con un costo T(N-1)), con lo cual queda
en este momento el disco de mayor diámetro solo en una espiga, por lo que colocar tal disco a la
espiga sin discos tiene un costo de una unidad. Posteriormente, se tienen que colocar los N-1 discos
sobre el disco de mayor diámetro (con un costo T(N-1)) (ver figura 1.6). Por tanto, la condición de
paro en la recursividad será la siguiente:
T (1) =1.
De esta forma:
T(N) = 2T(N-1) + 1 = 2(2T(N-2) + 1) + 1 = 4T(N-2) + 2+ 1
T(N-2) = 2T(N-3) + 1
36
