• Author / Uploaded
• Dogezo

Citation preview

Torre Hanoi Nuestro primer algoritmo en Ciencias de la Computación. Resolver la torre de Hanoi.

1. Seleccionar disco 1 2 3 4 5 6 7 8 9 10 11 12

def seleccione_disco(NUM_DIS,paso): # Para cada disco en orden inverso for disco in range(NUM_DIS,-1,-1): # Calculamos masa masa = 2 ** disco # Si el paso deja mover la masa, retorne ese disco if paso % masa == 0: return disco # Prueba # se espera que en el paso 4 se seleccione el disco 2 assert(seleccione_disco(3, 4) == 2)

2. Ubicar desde 1 def disco_en_barra(NUM_DIS, masa_barra,disco): 2 3 masa_barra_binario=format(masa_barra, '#0' +str(NUM_DIS+1)+'b') 4 masa_barra_binario_rev =masa_barra_binario [:-(NUM_DIS)-1:-1] 5 return int(masa_barra_binario_rev[disco]) 6 7

1 2 3 4 5 6 7 8 9 10 11 12 13 14

def ubique_disco(NUM_DIS,masa_barras, disco): # Por cada barra for barra in [0,1,2]: # Convierta en binario para saber la ubicacion de cada disco # Si el disco es encontrado retorne esa barra if disco_en_barra(NUM_DIS,masa_barras[barra],disco): return barra

# Prueba: # Cuando las masas estan repartidas como [1,4,2] el disco 1 se encuentra en la # barra 2

3. Ubicar hacia donde 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

def ubique_hacia_donde(NUM_DIS,masa_barras, disco, desde): hacia_der = (desde + 1) % 3 hacia_izq = (desde - 1) % 3 masa_disco = 2**disco # Para todos los disco que estan debajo: for disco in range(disco): # Si aquel disco esta en la barra derecha if disco_en_barra(NUM_DIS,masa_barras[hacia_der],disco): #Entonces; muevase mejor hacia la izquierda return hacia_izq return hacia_der # Prueba # Si la masa de las barras es [0,4,3] y quiero mover el disco 0 que se encuentra # en la barra 2, se espera que se mueva a la barra 0 # Prueba Jeisson: # Para 4 discos, si la msa de las barras es [11,4,0] y quiero mover # el disco 1 que se encuentra en la barra 2, se espera que se mueva a la barra 1

4. Mover disco 1 def muevase(masa_barras, disco, desde, hacia): 2 masa_disco = 2**disco 3 for barra in [0,1,2]:

4 if barra == desde: 5 masa_barras[barra] -= masa_disco 6 if barra == hacia: 7 masa_barras[barra] += masa_disco 8 9 return masa_barras 10 11 # Prueba 12 # Cuando las masa de las barras es [1,4,2] y se mueve el disco 1 desde 13 # la barra 2 hacia la barra 1, se espera que la nueva masa sea [1,6,0] 14

ALGORITMO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

print("Digite los discos que va a usar: ") NUM_DIS=int(input()) masa_inicial = 2**NUM_DIS - 1 masa_barras_inicial = [masa_inicial,0,0] masa_barras = masa_barras_inicial # Para cada paso for paso in range(1, masa_inicial+1): # 1. Seleccionar disco disco = seleccione_disco(NUM_DIS,paso) # 2. Ubique disco barra_desde = ubique_disco(NUM_DIS,masa_barras, disco) # 3. Ubicar hacia donde barra_hacia = ubique_hacia_donde(NUM_DIS,masa_barras, disco, barra_desde) # 4. Mover disco y actualizar masa masa_barras = muevase(masa_barras, disco, barra_desde, barra_hacia) print('paso', paso, 'disco:', disco, 'desde:', barra_desde, 'hacia:', barra_hacia, 'masa:', masa_barras)

Digite 3 paso 1 paso 2 paso 3 paso 4 paso 5 paso 6 paso 7

los discos que va a usar: disco: disco: disco: disco: disco: disco: disco:

0 1 0 2 0 1 0

desde: desde: desde: desde: desde: desde: desde:

0 0 1 0 2 2 0

hacia: hacia: hacia: hacia: hacia: hacia: hacia:

1 2 2 1 0 1 1

masa: masa: masa: masa: masa: masa: masa:

[6, [4, [4, [0, [1, [1, [0,

1, 1, 0, 4, 4, 6, 7,

0] 2] 3] 3] 2] 0] 0]