PDF de programación - Las torres de Hanoi

Imágen de pdf Las torres de Hanoi

Las torres de Hanoigráfica de visualizaciones

Publicado el 14 de Enero del 2017
320 visualizaciones desde el 14 de Enero del 2017
325,7 KB
57 paginas
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.
  • Links de descarga
http://lwp-l.com/pdf822

Comentarios de: Las torres de Hanoi (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad