Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar iterativamente a solução da torre de Hanoii usando pilhas.

0 votos
36 visitas
perguntada Jul 8, 2018 em Ciência da Computação por rcthiago (11 pontos)  

Implemente iterativamente a solução da torre de Hanoii usando pilhas.

Compartilhe

1 Resposta

0 votos
respondida Dez 20, 2018 por rcthiago (11 pontos)  

Resolver o problema da torre de hanoi de forma interativa é um pouco mais complexo do que resolver de forma recursiva.

Uma das formas de executar o algoritmo é fazer movimentos entre as torres, contudo, esses movimentos variam de acordo com a quantidade de pinos iniciais. Abaixo temos o pseudo-código principal que é dividido da seguinte forma:

Se a torre tiver uma quantidade impar de blocos, faça:
1º - um movimento entre as torres 1 e 3
2º - um movimento entre as torres 1 e 2
3º - um movimento entre as torres 2 e 3

Observe que o movimento pode ser em qualquer sentido, desde que seja válido.

Se a torre tiver uma quantidade par de blocos, faça:
1º - um movimento entre as torres 1 e 2
2º - um movimento entre as torres 1 e 3
3º - um movimento entre as torres 2 e 3

Mais uma vez o movimento pode ser em qualquer sentido, desde que seja válido. O código abaixo está devidamente comentado. Nele, é possível encontrar a solução para o problema de 10 discos na pilha inicial

def hanoiinterativo(torre1, torre2, torre3):
    temp = torre1.copy();
    while (temp != torre3):
        if(len(temp)%2 == 1): #impar/odd
            torreBlocosImpares(temp, torre1, torre2, torre3)
        else: #par/even
            torreBlocosPares(temp, torre1, torre2, torre3)


def torreBlocosPares(temp, torre1, torre2, torre3):
    if (not move(torre1, torre2) and temp != torre3):
        move(torre2, torre1)
    if (not move(torre1, torre3) and temp != torre3):
        move(torre3, torre1)
    if (not move(torre2, torre3) and temp != torre3):
        move(torre3, torre2)


def torreBlocosImpares(temp, torre1, torre2, torre3):
    if (not move(torre1, torre3) and temp != torre3):
        move(torre3, torre1)
    if (not move(torre1, torre2) and temp != torre3):
        move(torre2, torre1)
    if (not move(torre2, torre3)) and temp != torre3:
        move(torre3, torre2)


def top(torre):
    if(len(torre) != 0):
        return torre[len(torre)-1]
    else:
        return 10000

# esse método valida os movimentos padrões entre duas
# torres.
def move(origem, destino):
    #verifica se a torres de origem possui algum elemento.
    if(len(origem) != 0):
        #verifica se o destino possui algum elemento
        if(len(destino) == 0):
            #caso não tenha efetua a transferencia
            destino.append(origem.pop())
            return (True)
        # caso exista alguma elemento, é necessário validar
        # se número do bloco de origem é menor do que o bloco
        # da torre de destino.
        else:
            if(top(origem)<top(destino)):
                destino.append(origem.pop())
                return (True)
    return (False)

# esse métodos serve para testar o código acima.
# veja que o método funciona para torres com quantidade
# de blocos pares e impares.
def main():
    torre1 = [10,9,8,7,6,5,4,3,2,1]
    torre2 = []
    torre3 = []
    hanoiinterativo(torre1, torre2, torre3)
    print(torre1)
    print(torre2)
    print(torre3)

main()
...