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
27 visitas
perguntada Jun 8 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 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 por Pedro Campelo (31 pontos)  
editado Jul 8 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
...