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

Explicite em uma implementação computacional a sequência de chamadas recursivas que são realizadas na solução convencional do problema da Torre de Hanoii usando uma pilha.

0 votos
54 visitas
perguntada Jun 8, 2018 em Ciência da Computação por Pedro Henrique T (16 pontos)  

[Resumindo: (a) Crie uma função que
represente cada chamada das funções usando uma string. (b) Crie
uma pilha de strings. (c) Toda vez que uma das funções é
chamada, a chamada da função (representada por uma string) é
adicionada a pilha. (d) Toda vez que a função retorna o elemento,
a função (a string que representa a função) é removida da pilha.
(e) Use vários prints da pilha para ficar explícito o exercício.]

Compartilhe

1 Resposta

0 votos
respondida Jun 8, 2018 por Pedro Henrique T (16 pontos)  

A implementação computacional para explicitar a sequência de chamadas recursivas é disponibilizada a seguir:

def move_tower_PILHA(n,begin,end,aux,lista=["primeira chamada omitida"]):


if(n==1):
     print(lista)
     lista.append("move_disk("+str(begin)+","+str(end)+")")
     print(lista)
     lista.pop()
     print(lista)
     lista.pop()
     print(lista)

else:
    print(lista)
    lista.append("move_tower("+str(n-1)+","+str(begin)+","+str(aux)+","+str(end)+")")
    move_tower_PILHA(n-1,begin,aux,end,lista)        
    lista.append("move_disk("+str(begin)+","+str(end)+")")
    print(lista)
    lista.pop()
    print(lista)
    lista.append("move_tower("+str(n-1)+","+str(aux)+","+str(end)+","+str(begin)+")")
    move_tower_PILHA(n-1,aux,end,begin,lista)
    lista.pop()
    print(lista)

A ideia básica da programação é adicionar à pilha a string que informa a chamada da função imediatamente antes desta função ser chamada na recursão.

Como a função move_disk() é a função base da recursão da Torre de Hanoii e como a ideia do exercício é apenas explicitar a sequência de chamadas das funções, eu optei por não chamar de fato esta função, ou seja, eu apenas adiciono a string que representa a chamada de move_disk(). Sendo a função base da recursão, sempre que a string referente a esta função é adicionada à pilha, ela deve ser removida da pilha logo em seguida.

As funções move_tower_PILHA() vão se acumulando na pilha e são removidas apenas quando todas as outras funções que são chamadas dentro delas são resolvidas.

Os prints foram colocados em locais estratégicos da programação com a finalidade de deixar bem evidente o passo a passo envolvendo a pilha.

Perceba que a função move_tower_PILHA() possui um parâmetro chamado lista, que nada mais é do que a nossa pilha. Esse parâmetro deve ser inicializado com uma string referente à primeira chamada da recursão, que vai ser composta pelo n e pelos rótulos das três torres. Caso o usuário não inicialize este parâmetro, o programa atribui a primeira string da lista como sendo "primeira chamada omitida" .

A critério de exemplo, a função foi rodada para n=3. A seguir tem-se o código e os prints resultantes:

n=3
lista=["move_tower("+str(n)+","+"B"+","+"E"+","+"A"+")"]
move_tower_PILHA(n,'B','E','A',lista)


['move_tower(3,B,E,A)']
['move_tower(3,B,E,A)', 'move_tower(2,B,A,E)']
['move_tower(3,B,E,A)', 'move_tower(2,B,A,E)', 'move_tower(1,B,E,A)']
['move_tower(3,B,E,A)', 'move_tower(2,B,A,E)', 'move_tower(1,B,E,A)', 'move_disk(B,E)']
['move_tower(3,B,E,A)', 'move_tower(2,B,A,E)', 'move_tower(1,B,E,A)']
['move_tower(3,B,E,A)', 'move_tower(2,B,A,E)']
['move_tower(3,B,E,A)', 'move_tower(2,B,A,E)', 'move_disk(B,A)']
['move_tower(3,B,E,A)', 'move_tower(2,B,A,E)']
['move_tower(3,B,E,A)', 'move_tower(2,B,A,E)', 'move_tower(1,E,A,B)']
['move_tower(3,B,E,A)', 'move_tower(2,B,A,E)', 'move_tower(1,E,A,B)', 'move_disk(E,A)']
['move_tower(3,B,E,A)', 'move_tower(2,B,A,E)', 'move_tower(1,E,A,B)']
['move_tower(3,B,E,A)', 'move_tower(2,B,A,E)']
['move_tower(3,B,E,A)']
['move_tower(3,B,E,A)', 'move_disk(B,E)']
['move_tower(3,B,E,A)']
['move_tower(3,B,E,A)', 'move_tower(2,A,E,B)']
['move_tower(3,B,E,A)', 'move_tower(2,A,E,B)', 'move_tower(1,A,B,E)']
['move_tower(3,B,E,A)', 'move_tower(2,A,E,B)', 'move_tower(1,A,B,E)', 'move_disk(A,B)']
['move_tower(3,B,E,A)', 'move_tower(2,A,E,B)', 'move_tower(1,A,B,E)']
['move_tower(3,B,E,A)', 'move_tower(2,A,E,B)']
['move_tower(3,B,E,A)', 'move_tower(2,A,E,B)', 'move_disk(A,E)']
['move_tower(3,B,E,A)', 'move_tower(2,A,E,B)']
['move_tower(3,B,E,A)', 'move_tower(2,A,E,B)', 'move_tower(1,B,E,A)']
['move_tower(3,B,E,A)', 'move_tower(2,A,E,B)', 'move_tower(1,B,E,A)', 'move_disk(B,E)']
['move_tower(3,B,E,A)', 'move_tower(2,A,E,B)', 'move_tower(1,B,E,A)']
['move_tower(3,B,E,A)', 'move_tower(2,A,E,B)']
['move_tower(3,B,E,A)']
[]
comentou Jul 6, 2018 por Pedro Campelo (46 pontos)  
editado Jul 8, 2018 por Pedro Campelo
Pedro, muito boa implementação.  

Por curiosidade tb fiz um programa da torre de hanoi parecida com a feita na sala de aula:

    def hanoi (n, de, aux, para):
        if n > 0:
            hanoi (n-1, de, para, aux)
            print ("Move de %i para %i" % (de, para))
            hanoi (n-1, aux, de, para)

    if __name__ == '__main__':
        print(hanoi(3, 1, 2, 3))

Move de 1 para 3
Move de 1 para 2
Move de 3 para 2
Move de 1 para 3
Move de 2 para 1
Move de 2 para 3
Move de 1 para 3
...