1

Eu escrevi este codigo recursivo da torre de hanoi e estava a tentar implementar uma secção que me dissesse o número mínimo de jogadas necessárias e em que jogada estavamos ( acrescentar uma jogada sempre que esta mudasse).

Por exemplo se houvessem 3 discos:

Primeira jogada: Tower 1 --> Tower 2
etc...
Número minimo de jogadas: 7

Como é que poderia implementar isto? Recursivamente? Com iteração e ciclos? Já tentei recursivamente mas perdi-me no meu raciocínio e não consegui resolver o problema sem reformular tudo.

def hanoi():

    def mova(n, origem, destino, aux):
        
        def mova_disco(de, para):
            print("Tower", de, "-->", "Tower", para, "\n\n")


        if n == 1:
            mova_disco(origem, destino)

        else:
            mova(n - 1, origem, aux, destino)
            mova_disco(origem, destino)
            mova(n - 1, aux, destino, origem)

    n = eval(input("Quantos discos deseja considerar? \n -->"))
    print("Solução do puzzle: \n")
    mova(n, "1", "3", "2")

#Running the code

hanoi()
5
  • 1
    Em português, por favor, já que estamos no Stack Overflow em Português
    – Woss
    Commented 16/09/2020 às 16:50
  • E ao traduzir, poderia explicar o motivo de ter utilizado o eval na entrada do usuário?
    – Woss
    Commented 16/09/2020 às 16:51
  • @Woss já traduzi. Usei o evalei como usaria o "int(input)", só por habito e porque eles usam no livro que estou a ler. Mas funcionam de modo parecido penso eu. Commented 16/09/2020 às 17:11
  • eval não é a mesma coisa que int. A diferença é que int converte para número e dá erro se tiver qualquer coisa que não for um número, enquanto eval aceita qualquer comando válido, podendo inclusive ser perigoso, veja aqui um exemplo - se o livro diz pra usar eval e não alerta para esses problemas, eu já olharia com desconfiança...
    – hkotsubo
    Commented 16/09/2020 às 17:15
  • Ok, entendi. Obrigado. Vou ter isso em conta nas próximas vezes antes de usar eval :) Em relação ao problema do algoritmo tem ideia de como é que poderia resolver? Commented 16/09/2020 às 17:34

1 Resposta 1

0

Você pode fazer com que as funções recebam o número da jogada atual, e retornem esse número atualizado.

E como o total de jogadas para N discos sempre é 2N - 1, você pode imprimir esse valor diretamente:

def hanoi():
    def mova(n, origem, destino, aux, jogada):
        def mova_disco(de, para, jogada):
            print(f"Jogada {jogada:>3}: Tower {de} --> Tower {para}")
            return jogada + 1 # atualiza para a próxima jogada

        if n == 1:
            jogada = mova_disco(origem, destino, jogada)
        else:
            jogada = mova(n - 1, origem, aux, destino, jogada)
            jogada = mova_disco(origem, destino, jogada)
            jogada = mova(n - 1, aux, destino, origem, jogada)

        return jogada

    n = int(input("Quantos discos deseja considerar? \n -->"))
    print(f"Solução do puzzle ({2 ** n - 1} jogadas): \n")
    mova(n, "1", "3", "2", 1)

hanoi()

Ou seja, quando eu mover o disco, eu imprimo a jogada atual e retorno a jogada seguinte. E a cada movimento eu pego esse retorno e passo para o movimento seguinte.

Repare também que usei f-string (disponíveis a partir do Python 3.6) para imprimir as mensagens. No caso da jogada, também usei as opções de formatação (no caso, >3 para alinhar os números à direita, ocupando 3 posições).

E troquei eval por int, já que int converte o que for digitado para número (e dá erro se não for um número), enquanto eval executa qualquer coisa que for digitada, inclusive comandos potencialmente perigosos (veja aqui para mais detalhes).


Outra solução (pior, leia aqui e aqui para mais detalhes) é ter uma variável global como contador de jogadas:

jogada = 1 # variável global
def hanoi():
    def mova(n, origem, destino, aux):
        def mova_disco(de, para):
            global jogada # referenciar a variável global
            print(f"Jogada {jogada:>3}: Tower {de} --> Tower {para}")
            jogada += 1 # atualizar o contador

        if n == 1:
            mova_disco(origem, destino)
        else:
            mova(n - 1, origem, aux, destino)
            mova_disco(origem, destino)
            mova(n - 1, aux, destino, origem)

    n = int(input("Quantos discos deseja considerar? \n -->"))
    print(f"Solução do puzzle ({2 ** n - 1} jogadas): \n")
    mova(n, "1", "3", "2")

hanoi()

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .