PDF de programación - Las torres de Hanoi

Las torres de Hanoi
Informática - Hoja de Ejercicios 6

Posición inicial

1
2
3
4
A

B

C

Objetivo

Mover todos los discos desde la aguja A a la
aguja C

A

B

1
2
3
4
C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

1
2
3
4
A

B

C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

1
2
3
4
A

B

C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

2
3
4
A

1
B

C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

2
3
4
A

1
B

C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

3
4
A

2
1
B

C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

3
4
A

2
1
B

C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

2
3
4
A

1
B

C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

2
3
4
A

1
B

C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

3
4
A

1
B

2
C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

3
4
A

B

1
2
C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

4
A

3
B

1
2
C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

1
4
A

3
B

2
C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

1
4
A

2
3
B

C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

4
A

1
2
3
B

C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

A

1
2
3
B

4
C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

A

2
3
B

1
4
C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

2
A

3
B

1
4
C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

1
2
A

3
B

4
C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

1
2
A

B

3
4
C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

2
A

1
B

3
4
C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

A

1
B

2
3
4
C

Normas

1. Sólo se puede mover un disco a la vez de una

2. No se puede colocar un disco encima de otro

aguja a otra.

de menor tamaño.

A

B

1
2
3
4
C

Procedimiento general

Queremos mover 4 discos desde A hasta C,
utilizando, B como aguja auxiliar.

1
2
3
4
A

B

C

Procedimiento general

Paso 1: Mover 3 discos de A a B, utilizando C
como aguja auxiliar.

(Se hace en varios pasos)

Mismo problema,
pero de tamaño
menor.

1
2
3
4
A

B

C

Procedimiento general

Paso 1: Mover 3 discos de A a B, utilizando C
como aguja auxiliar.

(Se hace en varios pasos)

4
A

1
2
3
B

C

Procedimiento general

Paso 2: Mover un disco de A a C.

(Un único paso)

4
A

1
2
3
B

C

Procedimiento general

Paso 2: Mover un disco de A a C.

(Un único paso)

A

1
2
3
B

4
C

Procedimiento general

Paso 3: Mover 3 discos de B a C, utilizando A
como aguja auxiliar.



1
2
3
B

4
C

A

Procedimiento general

Paso 3: Mover 3 discos de B a C, utilizando A
como aguja auxiliar.



B

1
2
3
4
C

A

Resumen

auxiliar.

auxiliar.

Queremos mover 4 discos de A a C, utilizando B
como auxiliar:
1. Mover 3 discos de A a B, utilizando C como

2. Mover directamente el disco 4 (el más

grande), de A a C.

3. Mover 3 discos de B a C, utilizando A como

Generalización

Queremos mover n discos de A a C, utilizando B
como auxiliar:
1. Mover n-1 discos de A a B, utilizando C como

2. Mover directamente el disco n (el más

grande), de A a C.

3. Mover n-1 discos de B a C, utilizando A como

auxiliar.

auxiliar.

Objetivo

● Realizar un programa, que partiendo de una

posición inicial con n discos en la aguja A,
llegue a la posición en la que los n discos
estén en la aguja C.


● El programa debe escribir en un archivo la

representación de las sucesivas
configuraciones por las que van pasando las
agujas.

Ejemplo

Configuración 0:
-----------------

11
2222
333333
44444444
--------
Torre 1

--------
Torre 2

--------
Torre 3



Configuración 1:
-----------------

2222
333333
44444444
--------
Torre 1

11
--------
Torre 2

--------
Torre 3



Configuración 2:
-----------------

333333
44444444
--------
Torre 1

11
--------
Torre 2

2222
--------
Torre 3



Representación de las torres

Columna A: [4, 3, 2]

2
3
4
A

Representación de las
configuraciones

1
2
0

1

3
4
2

[ [2, 1], [ ], [4, 3] ]

Representación de las
configuraciones

1
2
0

1

3
4
2

[ [2, 1], [ ], [4, 3] ]

Representación de las
configuraciones

2
0

1

[ [2], [ ], [4, 3, 1] ]

1
3
4
2

Representación de las
configuraciones

1
3
4
2

2
0

1

[ [2], [ ], [4, 3, 1] ]

Configuración

Paso 1

Crear una función para mover fichas de una
columna a otra.

def mover(Configuracion, ColOrigen, ColDestino):

donde:
● Configuracion contiene la información de las tres

agujas.

● ColOrigen contiene el índice de la aguja que contiene el

disco que queremos sacar.

● ColDestino contiene el índice de la aguja donde

queremos meter el disco.



Paso 1

1
2
0

1

3
4
2

Si C = [ [2, 1], [ ], [4, 3] ]



mover(C, 0, 2)

Paso 2

Esqueleto del programa:

def hanoi(n, Configuracion, Inicio, Fin, Aux):

donde:
● n es el número de discos
● Configuración es la configuración inicial.
● Inicio es el número de columna que contiene

inicialmente los discos.

● Fin es el número de columna donde colocar los discos.
● Aux es el número de columna que utilizaremos como

auxiliar.



Paso 2

1
2
3
4
0

1

2

Llamada inicial:

C = [ [4, 3, 2, 1], [], [] ]
hanoi(4, C, 0, 2, 1)

Caso base

1
0

1

2

if n == 1:

mover(Configuracion, Inicio, Fin)
# Imprimir configuración

Caso recursivo

else: # si n > 1

hanoi(n-1, Configuracion, Inicio, Aux,

1

2

1
2
3
4
0

Fin)

Inicio)



mover(Configuracion, Inicio, Fin)
# ..Imprimir configuración...
hanoi(n-1, Configuracion, Aux, Fin,

Caso recursivo

else: # si n > 1

hanoi(n-1, Configuracion, Inicio, Aux,

1

2

1
2
3
4
0

Fin)

Inicio)



mover(Configuracion, Inicio, Fin)
# ..Imprimir configuración...
hanoi(n-1, Configuracion, Aux, Fin,

Caso recursivo

1
2
3
1

2

4
0

Fin)

Inicio)



else: # si n > 1

hanoi(n-1, Configuracion, Inicio, Aux,

mover(Configuracion, Inicio, Fin)
# ..Imprimir configuración...
hanoi(n-1, Configuracion, Aux, Fin,

Caso recursivo

1
2
3
1

2

4
0

Fin)

Inicio)



else: # si n > 1

hanoi(n-1, Configuracion, Inicio, Aux,

mover(Configuracion, Inicio, Fin)
# ..Imprimir configuración...
hanoi(n-1, Configuracion, Aux, Fin,

Caso recursivo

1
2
3
1

4
2

0

Fin)

Inicio)



else: # si n > 1

hanoi(n-1, Configuracion, Inicio, Aux,

mover(Configuracion, Inicio, Fin)
# ..Imprimir configuración...
hanoi(n-1, Configuracion, Aux, Fin,

Caso recursivo

1
2
3
1

4
2

0

Fin)

Inicio)



else: # si n > 1

hanoi(n-1, Configuracion, Inicio, Aux,

mover(Configuracion, Inicio, Fin)
# ..Imprimir configuración...
hanoi(n-1, Configuracion, Aux, Fin,

Caso recursivo

0

Fin)

Inicio)



1
2
3
4
2

1

else: # si n > 1

hanoi(n-1, Configuracion, Inicio, Aux,

mover(Configuracion, Inicio, Fin)
# ..Imprimir configuración...
hanoi(n-1, Configuracion, Aux, Fin,

Paso 3

Configuración 0:
-----------------

11
2222
333333
44444444
--------
Torre 1

--------
Torre 2

--------
Torre 3



Configuración 1:
-----------------

2222
333333
44444444
--------
Torre 1

11
--------
Torre 2

--------
Torre 3


Configuración 2:
-----------------

333333
44444444
--------
Torre 1

11
--------
Torre 2

2222
--------
Torre 3


Mantener un contador

de configuraciones



Paso 3

1
3
2
4
0
2
[ [2], [ ], [4, 3, 1], 23]

1

Número de configuración

Paso 3

Modificar la función:

def mover(Configuracion, ColOrigen, ColDestino):

para que, además de mover los discos de
ColOrigen a ColDestino, aumente el contador
contenido en Configuracion.


Paso 4

Escritura en el fichero de salida:

def hanoi(f, n, Configuracion, Inicio, Fin,
Aux):



Identificador del fichero en
el que escribir el resultado.